1 Quantum Parallelism
Quantum circuit can compute a Boolean function for all possible arguments in one-shot.
Example 1 Let f(a,b) = ab. We can use the circuit shown on Fig. 1 to compute this function for all four possible choices of the arguments.
Figure 1: Simulation of AND gate
Copyright By PowCoder代写 加微信 powcoder
To achieve this goal we prepare first two qubits in the input joint state: 12 (|00⟩ + |01⟩ + |10⟩ + |11⟩)|0⟩
=21(|000⟩ + |010⟩ + |100⟩ + |110⟩).
It is easy to see that at the output we obtain the following output joint
21 (|000⟩ + |010⟩ + |100⟩ + |111⟩).
One can see that the each term in the above expression has the form |a b ab⟩. The problem is, however, that we do not have an access to the individual terms. We can make only measurements of these three qubits (we can also make measurement of any single qubit or any two qubits, but it does not look useful here). As a result of such measurement, we get
Classical Output Probability
000 1/4 010 1/4 100 1/4 111 1/4
In general if we have a boolean function with n arguments f(x1,…,xn), we can construct a quantum circuit shown on Fig. 2.
Figure 2: Quantum parallelism
If we prepare the first n qubits in input joint state: 111
… |x1…xn⟩|y⟩, x1 =0 xn =0
then at the output we will get output joint state: 111
… |x1…xn y ⊕ f(x1…xn)⟩. x1 =0 xn =0
So, if we use y = 0, then we obtain |x1…xn f(x1…xn)⟩ for all possible argu- ments in one shot.
However, we still have the problem that we do not have an access to f(x1, …, xn) for needed x1, …, xn. When we make a measurement, we will get at the classical outputs: x1,…,xn, f(x1,…,xn) for random x1,…,xn with probability 1/2n.
2 Shor’s Fast Factoring Algorithm
Assume we have an integer n = p1p2 that is a product of two large primes p1 and p2. Our goal is to find these primes.
Shor’s algorithm consists of three parts: Discrete Fourier Transform, Phase Estimation, and Order Finding. Order Finding leads to fast factoring. Below we consider all these parts.
2.1 Discrete Fourier Transform
Recall that complex numbers of the form ω = e2πi/N are called N-th roots of
unity. According to Euler’s formula we have
e2πi/N =cos(2π/N)+isin(2π/N), i=√−1. (1)
From this we have that e2πi = 1 and further
e2πi·m = (e2πi)m = 1m = 1, for any interger m. (2)
DFT matrix F is the N× N unitary matrix
1 1 1 ··· 1
2.N−1 11ω ω . ω
F = √ 1 ω2 ω4 . ω2(N−1) , where ω = e2πi/N. N. . . . .
. . . . . 1 ωN−1 ω(N−1)2 · · · ω(N−1)(N−1)
So the j-th column of F is fj = 1 ωj ωj·2 · · · ωj(N−1)T. Note that the j-th row of F is fjT . Note also that F is unitary since it is not difficult to check that FF† = IN.
DFTofvectorx∈CN isdefinedbyy=Fx. Example 2 Let N = 22. Then ω = e2πi/4 = i and
1111 F=1=1 i−1−i.
DFT of vector x ∈ C4 is
2 1 − 1 1 − 1 1 −i −1 i
y0 x0 y1 = F x1.
y2 y3
x2 x3
Remark 1 Recall that in Dirac notation the state |j⟩ means the j-th vector (in decimal representation) in an orthonormal basis of C2n . Typically we use binary representation, but decimal one works equally well. If, for example, n = 2 then |2⟩ means the same as |10⟩, and we can write a generic quantum state as
or equivalently as
α00|00⟩ + α01|01⟩ + α10|10⟩ + α11|11⟩, α00|0⟩ + α01|1⟩ + α10|2⟩ + α11|3⟩.
In what follows we assume that N = 2n.
Let we have n qubits in a state |j⟩, j = 0,…,N − 1¿ Let us further assume that we constructed a quantum circuit that conducts the unitary transform
1 N−1 1 N−1
|j⟩→√ ωjk|k⟩=√ e2πijk/N|k⟩, j=0,…,N−1. (3)
N k=0 N k=0
Then if we submit to the input of this circuit n qubits in the state
xj|j⟩, (4)
then, according to (3), the circuit will transform this state into the output
N−1 1 N−1 N−1 1 N−1 N−1 N−1 xj √ ωjk|k⟩ = |k⟩√ xjωjk = |k⟩ fkTx = yk|k⟩,
j=0 N k=0 k=0 N j=0 k=0 k=0 yk
where coefficients xj and yk are connected by the DFT: y0 x0
y1 x1 . =F . .
. . yN −1 xN −1
Thus, the circuit that conducts (3) will also conduct DFT for a general quantum state (4). Therefore we proceed with construction of a quantum
circuit that conducts the mapping:
|j⟩→ 1 e2πijk/2n|k⟩= α (5)
We represent integer k by its binary expansion:
k=k12n−1 +k22n−2 +···+kn20, ks =0,1.
(For example 5 = 1 · 22 + 0 · 21 + 1 · 20. ) Then 11
α = 1 2n/2
. . . e2πij(k12n−1+k22n−2+···+kn20)/2n |k1 · · · kn⟩ k1 =0 kn =0
. . . e2πij(k1/2+k2/4+···+kn/2n)|k1 · · · kn⟩
k1 =0 kn =0 11
. . . e2πijk1/2|k1⟩ ⊗ e2πijk2/4|k2⟩ ⊗ · · · ⊗ e2πijkn/2n |kn⟩ = β k1 =0 kn =0
We note that the following sums of products are equal to the products of sums:
a0b0 +a0b1 +a1b0 +a1b1 = (a0 +a1)(b0 +b1), and
a0b0c0 + a0b0c1 + a0b1c0 + a0b1c1 + a1b0c0 + a1b0c1 + a1b1c0 + a1b1c1 =(a0 + a1)(b0 + b1)(c0 + c1)
We note that (6) is also a sum of products with a0,a1,b0,b1, and so on, defined as
k1 = 0, a0 = e2πij·0/2|0⟩ = |0⟩ = 1, a1 = e2πij·1/2|1⟩
k2 = 0, b0 = e2πij·0/4|0⟩ = |0⟩ = 1, b1 = e2πij·1/4|1⟩
Hence (6) can be written in the form:
β = 1 (|0⟩ + e2πij·1/2l |1⟩) = γ (7)
Now we represent j via its binary expansion:
j = j12n−1 + j22n−2 + · · · + jn20, js = 0, 1,
and taking into account (2), we simplify the the second terms of the factors of (7) as follows:
l = 1 : e2πi(j12n−1+j22n−2+···+jn−1·2+jn)/2
=e2πij12(n−1)/2·e2πij22(n−2)/2·…·e2πijn−1 ·e2πijn/2
111 = e2πijn/2
l = 2 : e2πi(j12n−1+j22n−2+···+jn−12+jn)/4
= e2πij12n−1/4 · . . . · e2πijn−2 ·e2πijn−1/2 · e2πijn/4
11 =e2πijn−1/2 · e2πijn/4,
Using these expresssions, we get
γ = 1 (|0⟩ + e2πijn/2|1⟩) ⊗ (|0⟩ + e2πi(jn−1/2+jn/4)|1⟩) 2n/2
⊗ · · · ⊗ (|0⟩ + e2πi(j1/2+j2/4+···+jn/2n)|1⟩). (8) Summarizing the above arguments and derivations, we conclude that our
goal is to construct a quantum circuit that conducts the transform |j⟩ → 1 (|0⟩ + e2πijn/2|1⟩) ⊗ (|0⟩ + e2πi(jn−1/2+jn/4)|1⟩)
⊗ · · · ⊗ (|0⟩ + e2πi(j1/2+j2/4+···+jn/2n)|1⟩) (9)
Now we will construct a circuit that would produce (8). We will use the following unitary rotations:
1 0 1 0 1 0 Rk = 0 e2πi/2k , whichfork=2becomesR2 = 0 e2πi/4 = 0 i
1 1 0 1 1
|0⟩= 0 → 0e2πi/2k 0 1 0
The beginning of quantum circuit for DFT (the part for 1-st qubit):
0 = 0 =|0⟩
0 2πi/2k 0 2πi/2k
|1⟩= 1 → 0 e2πi/2k
Remind the action of the Hadamard gate H = √2 1 −1 and Controlled
1 =e 1 =e |1⟩ 1 1 1
In the very beginning we have |ψ0⟩ = |j1 . . . jn⟩. Next |ψ1⟩ = √1 (|0⟩ + e2πij1/2|1⟩)|j2j3 · · · jn⟩
If j1 = 0 : √1 (|0⟩ + e2πi·0/2|1⟩)|j2j3 · · · jn⟩ 2
= √1 (|0⟩+|1⟩)|j2j3 ···jn⟩ 2
Ifj1 =1:√1 (|0⟩+e2πi·1/21|1⟩)|j2j3···jn⟩ 2
= √1 (|0⟩−|1⟩)|j2j3 ···jn⟩
|ψ2⟩ :j2 = 0 : (|0⟩ + e2πij1/2|1⟩)|0⟩|j3 · · · jn⟩
j2 = 1 : (|0⟩ + e2πij1/2 · e2πi·1/4|1⟩)|1⟩|j3 · · · jn⟩
We note that the state of the 1-st qubit in this expression is the same as the last factor in (8). Using the same type of gate connection and similar arguments, we obtain the circuit in which all n qubits will have the states corresponding to the factors of (8) taken in the reverse order:
|ψ2⟩ = √1 (|0⟩ + e2πi(j1/2+j2/4)|1⟩)|j2⟩|j2 · · · jn⟩ 2
and continuing in this way we obtain:
|ψ3⟩ = √1 (|0⟩ + e2πi(j1/2+j2/4+···+jn−1/2n−1+jn/2n)|1⟩)|j2 · · · jn⟩ 2
The states of the qubits are
|u1⟩ = √1 (|0⟩ + e2πi(j1/2+j2/4+···+jn−2/2n−1+jn/2n)|1⟩) 2
|u2⟩ = √1 (|0⟩ + e2πi(j2/2+···+jn/2n−1)|1⟩) 2
|un−1⟩ = √1 (|0⟩ + e2πi(jn−1/2+jn/24)|1⟩) 2
|un⟩ = √1 (|0⟩ + e2πjn/2|1⟩) 2
The joint state at the output of the circuit is |u1 u2 . . . un⟩. Note that this state has the reverse order of multiplication compared with the needed state (8). To correct this we will use the swapping circuit.
2.1.1 Swapping Circuit
The following circuit swaps 1-st and 2-nd qubits.
|ψ0⟩ = αγ|00⟩ + αδ|01⟩ + βγ|10⟩ + βδ|11⟩
|ψ1⟩ = αγ|00⟩ + αδ|01⟩ + βγ|11⟩ + βδ|10⟩
|ψ2⟩ = αγ|00⟩ + αδ|11⟩ + βγ|01⟩ + βδ|10⟩
|ψ3⟩ = αγ|00⟩ + αδ|10⟩ + βγ|01⟩ + βδ|11⟩
= (γ|0⟩ + δ|1⟩)(α|0⟩ + β|1⟩)
F=√1 ω2 ω4 ω6 1 ω2 ω4 ω6 81 ω3 ω6 ω ω4 ω7 ω2 ω5
··· ··· ··· ··· ··· ··· ··· ···
1 0 1 0 1 0 R2= 0 e2πi/22 = 0 eπi/2 = 0 i =S
1 0 1 0 R3= 0 e2πi/8 = 0 eπi/4 =T
The DFT circuit is shown on the next page.
11111111 11 ω ω2 ω3 ω4 ω5 ω6 ω7
2.1.2 Complexity of Quantum DFT
1. Qubit 1: H gate +(n − 1) rotations ⇒ n gates
2. Qubit 2: H gate +(n−2) rotations ⇒ n−1 gates
n. Qubit n: H gate ⇒ 1 gate
Total: n(n + 1)/2 gates (n ≈ log2 N )
The classical complexity is Θ(n2n). Exponential speed up!!
Can we use quantum DFT to get all elements of vector y = F x? No!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com