Basics of Quantum Computing
1. Quantum Information and Qubit States
In quantum computing, information is stored as a quantum state or a qubit state. A 1-qubit state is represented as a state vector with amplitudes over the computational basis |0⟩ and |1⟩. The operation applied to a state is a quantum gate. A gate changes the state by applying a unitary matrix to the state vector. At the end, measurement is performed. After measurement, instead of a state vector, we obtain a classical outcome. For 1 qubit, it is 0 or 1. For multiple qubits, it is a classical bit string such as 00 or 01.
In a classical computer, 1 bit is 0 or 1. A bit is an abstract information unit in the computational model. Its actual physical implementation can vary, such as voltage, charge, or magnetic state. A quantum circuit is also designed first with abstract qubits and gates. It is then converted into hardware qubits and native gates.
A qubit is measured as 0 or 1 like a classical bit. Before measurement, it can be represented as a superposition of the two basis states.
|ψ⟩ = α|0⟩ + β|1⟩
α and β are complex amplitudes. α is the amplitude toward |0⟩, and β is the amplitude toward |1⟩. An amplitude has magnitude and phase. Measurement probability is the likelihood that the corresponding basis state appears as the actual measurement result. By the Born rule, the probability of obtaining |0⟩ is |α|², and the probability of obtaining |1⟩ is |β|². A complex number itself cannot be used as a probability value, so the squared absolute value is used.
|α|² + |β|² = 1
The Bloch sphere is a visualization that represents a 1-qubit pure state as a point on the surface of a sphere. A pure state is a state represented by a single state vector |ψ⟩. The top corresponds to |0⟩, and the bottom corresponds to |1⟩. Other points on the sphere represent superposition states of |0⟩ and |1⟩.
For example, the table below assumes all phases are 0.
2. Hilbert Space and Qubits
The Bloch sphere is defined in Hilbert space. Hilbert space is a space that handles complex vectors. A 1-qubit state can be written as a 2-dimensional complex vector.
The inner product is computed by taking the complex conjugate of the components of the vector in front and multiplying.
⟨φ|ψ⟩ = γ*α + δ*β
If the order of the inner product is reversed, it becomes the complex conjugate.
⟨ψ|φ⟩ = ⟨φ|ψ⟩*
The 1-qubit computational basis is |0⟩ and |1⟩.
An arbitrary 1-qubit state is written as follows.
|ψ⟩ = α|0⟩ + β|1⟩
Each component of the state vector is the amplitude of a basis state. When reading the measurement result as 0 or 1, the default reference is the computational basis in the z-axis direction.
Multiple-qubit states are made with the tensor product. For example, the 2-qubit basis |00⟩ in the order q₁, q₀ is as follows.
The tensor product of matrices A and B is a way of making a block matrix by multiplying each element of A by B.
If the basis order is set as q₁, q₀, then the indices of the state vector are also read in the order |00⟩, |01⟩, |10⟩, |11⟩.
3. Phase, Interference, and Quantum Gates
Each component of the state vector is an amplitude. An amplitude can be negative or complex. The sign and phase difference of amplitudes create interference. Amplitudes that lead to the same final state are added first. Then the squared absolute value becomes the probability. If the phases are the same, the amplitude grows. If the phases are opposite, the amplitudes cancel.
Applying the Hadamard gate shows this structure.
H(α|0⟩ + β|1⟩) = ((α+β)|0⟩ + (α−β)|1⟩)/√2
If α=β, the amplitude of |1⟩ becomes 0. If α=-β, the amplitude of |0⟩ becomes 0. The global phase is not directly visible in measurement probabilities. The relative phase changes interference.
Quantum operations are represented by matrices. Representative 1-qubit gates are X, Y, and H. The X gate flips 0 and 1.
X|0⟩ = |1⟩
X|1⟩ = |0⟩
The Y gate also flips 0 and 1. At the same time, it attaches a ±i phase.
Y|0⟩ = i|1⟩
Y|1⟩ = −i|0⟩
An example is as follows.
The H gate changes the computational basis into superposition states.
H|0⟩ = (|0⟩ + |1⟩)/√2
H|1⟩ = (|0⟩ − |1⟩)/√2
A superposition state is a state in which the amplitudes of multiple basis states are nonzero at the same time. It means that the state before measurement is represented as a linear combination of multiple possibilities.
CNOT is a 2-qubit gate. The control qubit is the qubit that checks the condition, and the target qubit is the qubit to which X is actually applied. If the control is |1⟩, the target is flipped. If the control is |0⟩, the target remains unchanged.
If q₁ is the control and q₀ is the target, it is as follows.
|00⟩ → |00⟩
|01⟩ → |01⟩
|10⟩ → |11⟩
|11⟩ → |10⟩
Using the basis |00⟩, |01⟩, |10⟩, |11⟩ in the order q₁, q₀, the CNOT matrix is as follows.
4. Linearity, Unitary Operations, and Reversible Computation
Quantum operations are linear. When a quantum gate is applied to a superposition state, the same gate is applied to each component of the superposition.
U(α|0⟩ + β|1⟩) = αU|0⟩ + βU|1⟩
A nonlinear operation such as a square function does not satisfy this condition. The time evolution of a closed quantum system is unitary, and a unitary operation is linear. Time evolution is the process in which a quantum state changes over time. In the circuit model, this change is represented as an ordered sequence of gates.
A unitary matrix is a matrix that has an inverse operation.
U†U = UU† = I
When matrix A is as follows,
A† is the matrix obtained by applying transpose and complex conjugation together.
If A†=A⁻¹, then A is unitary.
In classical logic, irreversible operations are also possible. For example, AND sends 00, 01, and 10 all to 0. The input cannot be recovered from the output alone. Operations in a closed quantum system are represented as unitary operations that do not lose information.
The inputs of a classical half adder are two bits, A and B. The outputs are the lower bit of the sum S and the carry bit C.
S = A ⊕ B
C = A ∧ B
For example, if A=1 and B=1, then S=0 and C=1. The lower bit of 1+1 is 0, and the carry is 1.
If we only look at the output of a classical half adder, input information can disappear. For example, (A,B)=(0,1) and (A,B)=(1,0) both produce (S,C)=(1,0). The original input cannot be uniquely recovered from the output.
Get sjs’s stories in your inbox
Join Medium for free to get updates from this writer.
Reversible means that the input can be uniquely recovered from the output. In a quantum circuit, the input qubits A and B are kept unchanged, and the computation result is recorded in auxiliary qubits SUM and CARRY. The whole transformation is constructed reversibly so that input information is not lost.
5. Grover Algorithm
Grover algorithm deals with unstructured search problems. It assumes that the data has no special ordering or structure. The goal is to find the answer w by calling a function f.
f(x) = 0 (x ≠ w), f(x) = 1 (x = w), N = 2ⁿ
If there are n qubits, there are 2ⁿ computational basis states. The state space is N=2ⁿ-dimensional. Here, N is the number of candidates and also the number of bases in Hilbert space.
Classically, since there is no information about the answer location, O(N) function evaluations are needed. Grover algorithm reduces this to O(√N) in terms of oracle queries.
At first, all candidate states are prepared with the same amplitude.
The answer state |w⟩ is the marked basis state where f(w)=1. Non-answer states are the remaining basis states where f(x)=0. |s′⟩ is the direction obtained by normalizing and summing all non-answer states.
The whole N-dimensional space can be reduced to a 2-dimensional plane formed by the |w⟩ direction and the |s′⟩ direction.
|s⟩ = sinθ|w⟩ + cosθ|s′⟩
sinθ = 1/√N
The algorithm does not know the answer amplitude from the beginning. The oracle marks only the answer state with a phase flip through f(x). It acts on the entire superposition at once, but measurement produces only one result.
Oracle reflection flips only the sign of the amplitude of the answer and leaves the other states unchanged.
If x is the answer, then f(x)=1, so the sign of the amplitude changes. If it is not the answer, then f(x)=0, so it remains unchanged.
|φ₁⟩ = V_f|s⟩ = −sinθ|w⟩ + cosθ|s′⟩
Diffuser reflection reflects the current state about the initial uniform superposition |s⟩.
D_s = 2|s⟩⟨s| − I
From the amplitude perspective, this can be seen as reflecting the new amplitudes around the average. The sign difference created by the oracle is converted here into probability amplification.
|ψ₁⟩ = D_sV_f|s⟩ = sin3θ|w⟩ + cos3θ|s′⟩
Applying the oracle and diffuser once each is one Grover iteration. Applying the two reflections in sequence changes the direction of the state vector in the 2-dimensional plane formed by |w⟩ and |s′⟩. This is interpreted as rotation.
After k Grover iterations, the state is as follows.
|ψₖ⟩ = sinφₖ|w⟩ + cosφₖ|s′⟩
φₖ = (2k+1)θ
The answer amplitude is sinφₖ, and the answer probability is sin²φₖ. As k increases, the angle increases as θ, 3θ, 5θ.
For the answer probability to be maximized, (2k+1)θ should be close to π/2.
If there is one answer, then θ=arcsin(1/√N). For large N, it is viewed as follows.
k_max ≈ (π/4)√N
If the iteration is repeated too many times, it passes the answer direction. Since the answer probability is sin²φₖ, it increases until φₖ gets close to 90°. After passing 90°, it decreases again. Grover algorithm should not be seen as a pump that keeps raising the amplitude. It is a process that rotates the state vector.
The example is the case where N=8 and there is one answer.
If the input space has 2ⁿ elements, the query complexity of Grover algorithm is as follows.
In actual hardware, the oracle circuit, diffuser circuit, gate depth, noise, and error correction cost must also be considered together.
6. Order Finding, QPE, and Shor Algorithm
The goal of order finding is to find a repeating interval. It is different from a search problem that finds a single answer. Suppose two integers a and N are coprime. If a is repeatedly exponentiated and the remainder modulo N is observed, it eventually becomes 1 again. The smallest positive integer that makes it become 1 for the first time is called the order r.
aʳ ≡ 1 (mod N)
The function f(x)=aˣ mod N repeats the same value every r steps.
f(x) = aˣ mod N
For example, if a=19 and N=21, then r=6. The values of 19ˣ mod 21 return to the same pattern whenever x increases by 6.
1⁹⁶ ≡ 1 (mod 21)
In Shor algorithm, factorization is transformed into order finding. To factor N, first choose a suitable a. If gcd(a,N) is not 1, then that value is already a factor of N. If gcd(a,N)=1, the quantum part is used to find r.
If r is even, aʳ−1 can be split into two parts.
The statement that aʳ is 1 modulo N means that aʳ−1 is divisible by N. Therefore, a factor of N may be caught in one of the two parentheses. Computing the following values can produce a factor.
If r is odd, this procedure is hard to use directly. It can also fail under the following condition.
In this case, a is chosen again.
For example, N=21 and a=19. Since gcd(19,21)=1, a factor does not appear from the beginning. If order finding gives r=6, then 1⁹³ is used.
1⁹³ + 1 = 6860, gcd(6860,21) = 7
Therefore, 21 is factored into 7 and 3. In this example, the gcd computation is not hard. The hard part is finding r. The tool for finding this r is QPE.
QPE is an algorithm that reads the rotation ratio of the phase produced when a unitary U is applied. There are cases where, when U is applied to some state |ψ⟩, the direction of the state is maintained and only a complex coefficient is attached in front.
In this case, |ψ⟩ is called an eigenstate, and the preceding e²πiθ is called an eigenvalue. The eigenvalue of a unitary has magnitude 1. It does not increase or decrease the state and only rotates the phase. If θ=1/4, it rotates by 1/4 of a full turn, that is, 90 degrees.
QPE approximates θ with the measurement value x.
x/2ᵗ ≈ θ
Here, t is the number of evaluation qubits. QPE reads what fraction of a full turn the phase rotates when U is applied once.
In order finding, the following unitary is used.
Uₐ,ₙ|x⟩ = |ax mod N⟩
For example, if a=7 and N=15, then 7×8 mod 15=11.
U₇,₁₅|8⟩ = |11⟩
If a and N are coprime, multiplication can be reversed. Two inputs do not merge into one output, and only the positions of the numbers are rearranged. This kind of rearrangement operation can be written as unitary.
When Uₐ,ₙ is repeatedly applied, the numbers cycle. If a value returns to the original value after r applications, that repeating interval is the order r. An eigenstate is a state that represents this cycle as a phase change. Since applying it r times must return it to the original state, the accumulated phase after r applications must also become an integer multiple of a full turn. The possible phases per application are 0, 1/r, 2/r, …, (r−1)/r.
Therefore, some eigenstate |uₛ⟩ satisfies the following.
0 ≤ s < r
When U is applied once, |uₛ⟩ itself is maintained and only the phase rotates by s/r. QPE gives an approximation of this s/r.
x/2ᵗ ≈ s/r
The desired value is the denominator r. s is the value measured along with it. Therefore, a fraction close to x/2ᵗ is found, and its denominator is treated as a candidate for r.
In practice, it is difficult to directly prepare |uₛ⟩. Instead, a basis state such as |1⟩ is inserted. |1⟩ behaves like a state in which several phase candidates are mixed. When QPE is applied, one of those phases is selected, and the result is an approximation of some s/r.
For example, suppose there are 11 evaluation qubits and the measurement value x is 1708.
x/2ᵗ = 1708/2048 ≈ 0.833984
This value is close to 5/6.
1708/2048 ≈ 5/6
Therefore, we regard s/r as 5/6 and obtain r=6 as a candidate. Continued fraction is a procedure for finding a fraction with a small denominator that is close to a decimal value. The reason for placing a limit on the denominator is that r is smaller than N.
