Introduction to Quantum Computing

Introduction to Quantum Computing Walid Gomaa Department of Computer Science and Engineering, Egypt Japan University of Science and Technology Walid Gomaa Quantum Computing August 15, 2025 Overview 1Introduction 2Quantum State 3The Four Postulates of Quantum Mechanics 4The Gate Model 5Quantum Evolution 6Quantum Circuits as Computational Model 7Quantum Algorithmic Characteristics Walid Gomaa Quantum Computing August 15, 2025 Introduction Introduction Introduction Walid Gomaa Quantum Computing August 15, 2025 Introduction Introduction to Quantum Computation Revolutionizing Computation: Quantum computation harnesses the principles of quantum mechanics to process information in fundamentally new ways. Beyond Classical Limits: By leveraging quantum phenomena such as superposition , interference , and entanglement , quantum computers can explore vast computational landscapes simultaneously. Qubits as Building Blocks: Unlike classical bits, qubits can exist in multiple states at once, forming the foundation for powerful parallel processing capabilities. Transformative Potential: The field promises revolutionary advancements in problem-solving, with implications for cryptography, optimization, and beyond. The Quantum Frontier: As we venture further into this realm, we open the door to new paradigms of understanding and technological innovation. Walid Gomaa Quantum Computing August 15, 2025 Introduction General Quantum Computer Architecture Walid Gomaa Quantum Computing August 15, 2025 Introduction Classical Information (Deterministic) Consider a physical system that stores information: let us call it X. Assume Xcan be in one of a finite number of classical states at each moment. Denote this classical state set by Σ. Examples If Xis a bit, then its classical state set is Σ = {0,1}. If Xis a six-sided die, then Σ = {1,2,3,4,5,6}. If Xis a switch on a standard electric fan, then Σ = {high,medium,low,off}. Walid Gomaa Quantum Computing August 15, 2025 Introduction Classical Information (Probabilistic) There may be uncertainty about the classical state of a system. For example, if Xis a bit, then perhaps it is in the classical state 0 with probability 3/4 and in the classical state 1 with probability 1/4. This is a probabilistic state of X. Pr(X= 0) = 3 4and Pr(X= 1) = 1 4 This probabilistic state can be represented by a column vector: 3/4 1/4←entry corresponding to 0 ←entry corresponding to 1 This vector is a probability vector: All entries are nonnegative real numbers. The sum of the entries is 1. Walid Gomaa Quantum Computing August 15, 2025 Introduction Dirac Notation Let Σ be any classical state set. Assume the elements of Σ have been placed in correspondence with integers 1,...,|Σ|. We denote by |α⟩the column vector having a 1 in the entry corresponding to α∈Σ, with 0 for all other entries. Vectors of this form are called standard basis vectors . Every vector can be expressed uniquely as a linear combination of standard basis vectors. Example 3/4 1/4=3 41 0+1 40 1=3 4|0⟩+1 4|1⟩ Walid Gomaa Quantum Computing August 15, 2025 Introduction Measuring Probabilistic States What happens if we measure a system Xwhile it is in some probabilistic state? We see a classical state, chosen at random according to the probabilities. Suppose we see the classical state α∈Σ. This changes the probabilistic state of X(from our viewpoint): having recognized that X is in the classical state α, we now have Pr(X=α)=1 This probabilistic state is represented by the vector |α⟩. Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Qubit State c0 c1=c01 0+c10 1 =c0|0⟩+c1|1⟩ |c0|2+|c1|2= 1 a0eiϕ0 a1eiϕ1a0,a1∈R,a2 0+a2 1= 1 cos(θ 2)eiϕ0 sin(θ 2)eiϕ1 eiϕ0cos(θ 2) sin(θ 2)ei(ϕ1−ϕ0) cos(θ 2) sin(θ 2)eiϕ 2(N-1) = 2 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 Quantum State Bloch Sphere Representation |ψ⟩= cos θ 2|0⟩+ sin θ 2eiϕ|1⟩ ψ: azimuthal angle or phase angle. θ: polar angle or inclination angle. φ θ x y z=|0⟩ −z=|1⟩ |ψ⟩ 1 √21 1 1 √21 eiπ/2 =1 √21 i 1 0 Walid Gomaa Quantum Computing August 15, 2025 Quantum State Highlights Machine state Qubit: quantum unit of information – superposition of classical states |0⟩and |1⟩. State of n qubits is N = 2n-dimensional complex vector (Hilbert space). 2 constraints: unit length,unobservable global phase. 2N−2 = 2(N−1) degrees of freedom. Superposition of Nbasis (classical) states. Evolution Rotation and/or reflection of state vector. N×Nmatrix multiply. Quantum parallelism (operating on superposition state). Observation Squared magnitude of vector component is probability of observing the corresponding basis state. Walid Gomaa Quantum Computing August 15, 2025 Quantum State Two Qubits Considered Separately |ψα⟩=α0 α1 2 degrees of freedom |ψβ⟩=β0 β1 2 degrees of freedom Considered Together |ψc⟩=    c00 c01 c10 c11     6 degrees of freedom Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Qubit: Quantum Bit The state of a quantum bit, called a qubit, can be described by a unit vector in a 2-dimensional state space: |ψ⟩=α|0⟩+β|1⟩ αand βare complex coefficients called the amplitudes of the computational basis states. |0⟩= (1,0) and |1⟩= (0,1) and |α|2+|β|2= 1. |ψ⟩is said to be in a superposition of |0⟩and |1⟩. Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Postulate 2: Time Evolution The evolution of the state of a closed quantum system from one time to another can be described by a unitary operator. A matrix Uis unitary if UU†=Iwhere Iis the identity (U†: conjugate-transpose). |ψ⟩UU|ψ⟩ state of the system at time t1 state of the system at time t2 Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Single-Qubit Hadamard Operator The Hadamard operator has the matrix representation: H=1 √21 1 1−1 Hmaps the basis states as follows: H|0⟩=1 √2(|0⟩+|1⟩) = |+⟩H|1⟩=1 √2(|0⟩−|1⟩) = |−⟩ Note that HH =I⇒Hermitian matrix/operator. Algorithmic pre-processing for uniform superposition over all input qubits. Perfect random number generator. Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Two-Qubit CNOT Operator The two-qubit CNOT (controlled-NOT) operator has the matrix representation on the right. CNOT flips the target qubit tiff the control qubit chas the value 1. The CNOT gate maps: |00⟩→|00⟩,|01⟩→|01⟩ |10⟩→|11⟩,|11⟩→|10⟩ |xy⟩denotes the tensor product |x⟩⊗|y⟩.     1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0     |q0⟩•|q0⟩ |q1⟩ |q1⊕q0⟩ CNOT gate Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Postulate 3: Measurements To get information from a closed quantum system, measurements need be applied to the system. A measurement returns an outcome with some probability. The sum of the probabilities of all possible outcomes is 1. A measurement collapses the state of a quantum system. Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Measurement of a Single Qubit Consider the measurement of a qubit in the state: |ψ⟩=α|0⟩+β|1⟩ in the computational basis. The output of the measurement is a classical bit. The probability of getting 0 is |α|2and the probability of getting 1 is |β|2. Note that |α|2+|β|2= 1. If the outcome is 0, the state after measurement is |0⟩; if the outcome is 1, the state after measurement is |1⟩. |ψ⟩ qubit quantum state Mclassical bit quantum state has collapsed Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Measuring Quantum States In most cases we restrict our attention to standard basis measurements: The possible outcomes are the classical states. The probability for each classical state to be the outcome is the absolute value squared of the corresponding quantum state vector entry. Example 1 Measuring the quantum state |+⟩=1 √2|0⟩+1 √2|1⟩ yields an outcome as follows: Pr(outcome is 0) =  1 √2 2=1 2Pr(outcome is 1) =  1 √2 2=1 2 Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Measuring Quantum States Example 2 Measuring the quantum state: |+⟩=1 √2|0⟩− 1 √2|1⟩ yields an outcome as follows: Pr(outcome is 0) =  1 √2 2=1 2Pr(outcome is 1) = −1 √2 2=1 2 Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Measuring Quantum States Example 3 Measuring the quantum state 1+2i 3|0⟩− 2 3|1⟩ yields an outcome as follows: Pr(outcome is 0) =  1+2i 3 2 =5 9Pr(outcome is 1) = −2 3 2 =4 9 Walid Gomaa Quantum Computing August 15, 2025 The Four Postulates of Quantum Mechanics Postulate 4: Composite Systems The state space of a composite physical system is the tensor product space of the state spaces of its component subsystems. Example Example: If A= (a1,a2), B= (b1,b2), C= (c1,c2), then A⊗Bis the vector (a1b1,a1b2,a2b1,a2b2); A⊗B⊗Cis the vector (a1b1c1,a1b1c2,a1b2c1,a1b2c2,a2b1c1,a2b1c2,a2b2c1,a2b2c2) Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Logical OR (B,A)7→ (B,A∨B) OR |BA⟩=|BF⟩,F=A∨B OR |00⟩=|00⟩=⇒    1000 0100 0000 0011        1 0 0 0     =    1 0 0 0     OR |10⟩=|11⟩=⇒    1000 0100 0000 0011        0 0 1 0     =    0 0 0 1     OR |01⟩=|01⟩=⇒    1000 0100 0000 0011        0 1 0 0     =    0 1 0 0     Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Logical OR (B,A)7→ (B,A∨B) OR |BA⟩=|BF⟩,F=A∨B OR |00⟩=|00⟩=⇒    1000 0100 0000 0011        1 0 0 0     =    1 0 0 0     OR |10⟩=|11⟩=⇒    1000 0100 0000 0011        0 0 1 0     =    0 0 0 1     OR |01⟩=|01⟩=⇒    1000 0100 0000 0011        0 1 0 0     =    0 1 0 0     OR |11⟩=|11⟩=⇒    1000 0100 0000 0011        0 0 0 1     =    0 0 0 1     Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Universal Computation? Reversible Logical NOT, XOR (realized as CNOT) SWAP Irreversible Logical AND, OR Multiplication Sort Assignment, copy Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Universal Combinatorial Logic f(x) is any Boolean function of n Boolean variables xi x0 x1 . . . xn−1 y x0 x1 . . . xn−1 y⊕f(x) This circuit is a unitary operation and so can always be realized. Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Unitary Logical OR x0 x1 y x0 x1 y⊕(x0∨x1)            10000000 0000010 0 00000010 00000001 0 0 0 0 10 0 0 010 0 0 0 0 0 0 0 100000 0 0 0 10 0 0 0                       c000 c001 c010 c011 c100 c101 c110 c111            =            c000 c101 c110 c111 c100 c001 c010 c011            Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Single-Qubit Pauli Gates X=0 1 1 0Xa b=b a⇒NOT + Y=0−i i0Ya b=−ib ia ⇒NOT+ phase change Y Z=1 0 0−1Za b=a −b⇒phase flip Z φ θ x y z=|0⟩ −z=|1⟩ |ψ⟩ 1 √21 1 1 √21 eiπ/2 =1 √21 i 1 0 Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Pauli Gates NOT :X=0 1 1 0Xcos(θ 2) sin(θ 2)eiϕ=sin(θ 2) cos(θ 2)e−iϕ NOT +Phase change :Y=0−i i0Ycos(θ 2) sin(θ 2)eiϕ=sin(θ 2) cos(θ 2)ei(π−ϕ) Phase flip :Z=1 0 0−1Zcos(θ 2) sin(θ 2)eiϕ=cos(θ 2) sin(θ 2)ei(π+ϕ) Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Hadamard Gate Put classical inputs in uniform superposition. H H=1 √21 1 1−1 H1 0=1 √21 1=1 √2|0⟩+1 √2|1⟩=|+⟩H|0⟩=|+⟩ H0 1=1 √21 −1=1 √2|0⟩− 1 √2|1⟩=|−⟩ H|1⟩=|−⟩ Walid Gomaa Quantum Computing August 15, 2025 The Gate Model Phase Operations A phase operation is one described by the matrix Pθ=1 0 0eiθ for any choice of a real number θ. The operations S=Pπ/2=1 0 0iand T=Pπ/4= 1 0 01+i √2! are important examples. Walid Gomaa Quantum Computing August 15, 2025 The Gate Model CONTROLLED-NOT x x yx⊕y x•x yx⊕y     1 0 0 0 0001 0 0 1 0 010 0        c00 c01 c10 c11     =    c00 c11 c10 c01     CNOT |yx⟩=|x⊕y,x⟩ Walid Gomaa Quantum Computing August 15, 2025 Quantum Evolution Inner Product Function of two vectors that is: scalar-valued linear independent of basis Defines geometry of space: length angle distance a†b=⟨a||b⟩=⟨a|b⟩=X i ¯aibi Length: cos(θ 2) sin(θ 2)e−iϕ cos(θ 2) sin(θ 2)eiϕ = cos2(θ 2) + sin2(θ 2) = 1 Walid Gomaa Quantum Computing August 15, 2025 Quantum Evolution Inner Product Function of two vectors that is: scalar-valued linear independent of basis Defines geometry of space: length angle distance a†b=⟨a||b⟩=⟨a|b⟩=X i ¯aibi Length: cos(θ 2) sin(θ 2)e−iϕ cos(θ 2) sin(θ 2)eiϕ = cos2(θ 2) + sin2(θ 2) = 1 Walid Gomaa Quantum Computing August 15, 2025 Quantum Evolution Inner Product Function of two vectors that is: scalar-valued linear independent of basis Defines geometry of space: length angle distance a†b=⟨a||b⟩=⟨a|b⟩=X i ¯aibi Length: cos(θ 2) sin(θ 2)e−iϕ cos(θ 2) sin(θ 2)eiϕ = cos2(θ 2) + sin2(θ 2) = 1 Walid Gomaa Quantum Computing August 15, 2025 Quantum Evolution Quantum Evolution Rules Rotation/reflection of state vector. Unitary operator U:UU†=U†U=I Preserves geometry of complex vector space: ⟨Uψ1|Uψ2⟩= (Uψ1)†(Uψ2) =ψ† 1U†Uψ2 =ψ† 1(U†U)ψ2 =ψ† 1ψ2=⟨ψ1|ψ2⟩ Walid Gomaa Quantum Computing August 15, 2025 Quantum Circuits as Computational Model Quantum Circuits as Computational Model Quantum Circuits as Computational Model Walid Gomaa Quantum Computing August 15, 2025 Quantum Circuits as Computational Model Quantum Circuit Abstraction A quantum circuit is an acyclic graph consisting of lines, quantum gates, and measurement gates. No fan-in: logical OR is not a unitary operation. No fan-out: in quantum mechanics, it is not possible to make a copy of an unknown quantum state (the no-cloning theorem). Walid Gomaa Quantum Computing August 15, 2025 Quantum Circuits as Computational Model Bell State q0 |0⟩=1 0H |+⟩=1 √21 1• 1 √2    11 1 01 1    =1 √2    1 1 0 0     1 √2    1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0        1 1 0 0     =1 √2    1 0 0 1     q1 |0⟩=1 0|0⟩⊗|+⟩=|0+⟩ entangled state Walid Gomaa Quantum Computing August 15, 2025 Quantum Circuits as Computational Model Quantum Circuit for EPR States Quantum circuit to generate Einstein-Podolsky-Rosen states, also known as Bell states : xH• y Circuit maps |00⟩ 7→ |00⟩+|11⟩ √2= Φ+,|01⟩ 7→ |01⟩+|10⟩ √2= Ψ+, |10⟩ 7→ |00⟩−|11⟩ √2= Φ−,|11⟩ 7→ |01⟩−|10⟩ √2= Ψ− Each output is an entangled state, one that cannot be written in a product form. Walid Gomaa Quantum Computing August 15, 2025 Quantum Circuits as Computational Model Quantum Teleportation |ψ⟩=|q0⟩•H• |0⟩=|q1⟩H• • |0⟩=|q2⟩X Z |ψ⟩ 1OO3,4OO5OO 1Alice and Bob generate an EPR pair Φ+by entangling |q1⟩and |q2⟩. 2Alice takes one half of the pair; Bob the other half. Bob moves far away taking his qubit with him. 3Alice gets her secret qubit |ψ⟩, interacts it with her EPR-half with a CNOT and Hadamard gate, and then measures the two output qubits. 4Alice sends the two resulting classical measurement bits to Bob. 5Using the classical measurement bits sent by Alice, Bob interacts his half of the EPR pair with a classically controlled CNOT gate and a classically controlled Pauli-Z gate to recreate |ψ⟩. Walid Gomaa Quantum Computing August 15, 2025 Quantum Circuits as Computational Model Prime Factorization: Classical vs Quantum Problem Given a composite n-bit integer, find a prime factor. Best-known deterministic algorithm on a classical computer has time complexity exp(O(n1/3log2/3n)) A hybrid classical-computer, quantum-computer can solve this problem in O(n2log nlog log n) Peter Shor Algorithms for Quantum Computation: Discrete Logarithms and Factoring Proc. 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124-134 Walid Gomaa Quantum Computing August 15, 2025 Quantum Algorithmic Characteristics Phase Oracle =(|−⟩|x⟩f(x) = 0 −|−⟩|x⟩f(x) = 1 = (−1)f(x)|−⟩|x⟩ Uf|−⟩|x⟩= (−1)f(x)|−⟩|x⟩ Walid Gomaa Quantum Computing August 15, 2025 Quantum Algorithmic Characteristics Entanglement H |ψ0⟩=|00⟩ |ψ1⟩=1 √2(|0⟩+|1⟩)⊗|0⟩=1 √2(|00⟩+|10⟩) |ψ3⟩=1 √2(|00⟩+|11⟩)every qubit is fully dependent on the other Walid Gomaa Quantum Computing August 15, 2025 Quantum Algorithmic Characteristics Phase Kickback |v⟩is an eigenvector of U=⇒U|v⟩=eiθ|v⟩ |ψ1⟩=|+⟩|v⟩=1 √2(|0⟩+|1⟩)|v⟩=1 √2(|0⟩|v⟩+|1⟩|v⟩) |ψ2⟩=1 √2(CU |0⟩|v⟩+CU |1⟩|v⟩) = 1 √2(|0⟩|v⟩+|1⟩CU |v⟩) =1 √2|0⟩|v⟩+|1⟩eiθ|v⟩=1 √2|0⟩|v⟩+eiθ|1⟩|v⟩ =1 √2|0⟩+eiθ|1⟩|v⟩phase is kicked onto the control qubit, target qubit is left unchanged Walid Gomaa Quantum Computing August 15, 2025 Thank You! Questions or comments are welcome. Presented by Walid Gomaa Email: [email protected]