Quantum Programming Foundations: Quantum Circuits
Jan 13, 2022
Quantum Programming, by Outline Foundations: quantum circuits; 100 minutes; Jan 13, 2022
Copyright By PowCoder代写 加微信 powcoder
Hook: The machine model of quantum computing is a quantum circuit. A quantum circuit can be drawn as a diagram, which shows which qubits we work with, which matrices we apply, and when. All this is just as simple as it sounds, but the things we can do with quantum circuits are amazing.
Purpose: Persuade you that quantum circuits are both simple and expressive.
1. Diagram notation for quantum circuits.
2. Superdense coding, teleportation, and no-cloning. 3. Universal sets of operations.
Transition to Body: Let us first look at how to draw a quantum circuit.
Main Point 1: Diagram notation for quantum circuits. [Input qubits]
[Unitary matrices] [Measurement]
Transition to MP2: Now let us look at what we can and cannot do with quantum circuits.
Main Point 2: Superdense coding, teleportation, and no-cloning. [Superdense coding]
[Teleportation] [No-cloning]
Transition to MP3: What is the machine language of quantum circuits?
Main Point 3: Universal sets of operations. [Universal sets exists]
[Universal sets can be quite different]
[Different quantum computers support different sets of matrices]
Transition to Close: So there you have it.
Review: We can draw circuit diagrams and do amazing little tasks, and we can talk about
universal sets of operations.
Strong finish: Now we are ready to study quantum algorithms, which we will express as quantum circuits.
Call to action: Play around with the quantum circuit simulator that we linked online.
Detailed presentation
Hook: The machine model of quantum computing is a quantum circuit. A quantum circuit can be drawn as a diagram, which shows which qubits we work with, which matrices we apply, and when. All this is just as simple as it sounds, but the things we can do with quantum circuits are amazing.
Purpose: Persuade you that quantum circuits are both simple and expressive.
1. Diagram notation for quantum circuits.
2. Superdense coding, teleportation, and no-cloning. 3. Universal sets of operations.
Transition to Body: Let us first look at how to draw a quantum circuit. Main Point 1: Diagram notation for quantum circuits.
[Input qubits]
The input qubits appear on the left. Each qubit has its own line that shows what happens to it as time moves from left to right.
[Unitary matrices]
Since quantum gates needs to be reversible, quantum gates must have the same number of inputs and outputs, unlike classical gates. Examples:
Note that the CNOT gate has the control bit on top (the filled circle) and the target bit on the bottom (the empty circle).
Let us apply a one-qubit matrix to two qubits.
Now let us use one qubit to control the application of a matrix U to another qubit.
General idea of a circuit:
We can map |0⟩ ⊗ |0⟩ to the Bell state √1 (|00⟩ + |11⟩) with the following circuit that uses an 2
Hadamard and a CNOT.
Let us check the math. The first application of H to the first qubit of |0⟩ ⊗ |0⟩ gives us |+⟩⊗|0⟩ = √1 |00⟩+√1 |10⟩
and now we can apply CNOT and get
The four Bell states are:
√1 |00⟩ + √1 |11⟩ 22
|Φ+⟩ = |Φ−⟩ = |Ψ+⟩ = |Ψ−⟩ =
√1 (|00⟩ + |11⟩) 2
√1 (|00⟩ − |11⟩) 2
√1 (|01⟩ + |10⟩) 2
√1 (|01⟩ − |10⟩) 2
Exercise: show how to generate the other three Bell states by circuits.
Exercise: show that the four Bell states form an orthonormal basis.
For example, we could devise a quantum circuit that carries out Shor’s algorithm: it takes as
input an n-bit integer, uses roughly n2 CCNOT and H gates, and has the property that when you measure the final output qubits, they give (with probability at least 99%) the binary encoding of the prime factorization of the input integer (plus some garbage bits).
[Measurement] Example:
The initial state is |00⟩.
After the first Hadamard gate, the state is
After the CNOT, the state is
√1 |00⟩ + √1 |10⟩ 22
√1 |00⟩ + √1 |11⟩ 22
After the final Hadamard gate, the state is:
√1 (√1 |00⟩+ √1 |10⟩)+ √1 (√1 |01⟩− √1 |11⟩) = 1|00⟩+ 1|01⟩+ 1|10⟩− 1|11⟩ 2222222222
So we get each of the four outcomes with probability 14 . 5
Transition to MP2: Now let us look at what we can and cannot do with quantum circuits. Main Point 2: Superdense coding, teleportation, and no-cloning.
[Superdense coding]
Suppose we have n qubits. How many classical bits is that? Holevo’s theorem (1973) gives the answer: n bits.
What are the consequences of Holevo’s theorem? Example: suppose Alice is trying to encode two bits as a single qubit. Holevo’s theorem says that this is impossible: if you have a single qubit, it boils down to a single bit.
However, Alice still wants to send two bits ab to Bob, by sending qubits. Does Alice have to send two qubits? Here is a different idea, called superdense coding, in which Alice sends a single qubit to Bob. The idea is that first Bob sends a qubit to Alice; perhaps way ahead of time.
1. Bob creates the state √1 (|00⟩ + |11⟩) and sends the first qubit A of that state to Alice but 2
keeps the second qubit B.
2. Alice does the following (she creates one of the four states in the Bell basis):
(a) If a = 1, then she applies Z to the qubit A.
(b) If b = 1, then she applies X to the possibly transformed qubit A.
(c) She sends the possibly transformed qubit A to Bob.
3. Bob does the following (he measures the qubits in the Bell basis):
(a) He applies CNOT(A, B). (b) He applies H to A.
1 0 0 −1 ab After 2a After 2b After 3a
00 √1 (|00⟩ + |11⟩) √1 (|00⟩ + |11⟩) √1 (|00⟩ + |10⟩) = √1 (|0⟩ + |1⟩)|0⟩ 2222
01 √1 (|00⟩ + |11⟩) √1 (|10⟩ + |01⟩) √1 (|11⟩ + |01⟩) = √1 (|1⟩ + |0⟩)|1⟩ 2222
10 √1 (|00⟩ − |11⟩) √1 (|00⟩ − |11⟩) √1 (|00⟩ − |10⟩) = √1 (|0⟩ − |1⟩)|0⟩ 2222
11 √1 (|00⟩ − |11⟩) √1 (|10⟩ − |01⟩) √1 (|11⟩ − |01⟩) = √1 (|1⟩ − |0⟩)|1⟩ 2222
(c) He measures both A and B. X=01Z=10
[Teleportation]
The task: Alice has a qubit α|0⟩ + β|1⟩ and wants to tell Bob what it is; she wants to do that by sending classical bits to Bob.
Like in superdense coding, Bob creates the state √1 (|00⟩ + |11⟩) and sends the first qubit of 2
that state to Alice.
Let us look at the state of all three qubits, of which the first two belong to Alice and the third
belong to Bob:
(α|0⟩ + β|1⟩) ⊗ √1 (|00⟩ + |11⟩) 2
Now Alice measures her two qubits in the Bell basis and sends the result to Bob. Specifically, Alice applies the following to her two qubits:
After 3b Bob sees |00⟩ 00
|10⟩ 10 −|11⟩ 11
after which Alice measures her two qubits and gets one of 00, 01, 10, 11, with probability 14 , and then sends those two bits to Bob.
Let us go through the steps of how this works. Let us rewrite the state of all three qubits:
(α|0⟩ + β|1⟩) ⊗ √1 (|00⟩ + |11⟩) = √1 (α|000⟩ + α|011⟩ + β|100⟩ + β|111⟩) 22
Now, after Alice has applied CNOT, the state of all three qubits is:
√1 (α|000⟩+α|011⟩+β|110⟩+β|101⟩) 2
Then, after Alice has applied H to the first qubit, the state of all three qubits is:
21(α|000⟩ + α|100⟩ + α|011⟩ + α|111⟩ + β|010⟩ − β|110⟩ + β|001⟩ − β|101⟩)
= 12(|00⟩(α|0⟩ + β|1⟩) + |01⟩(α|1⟩ + β|0⟩) + |10⟩(α|0⟩ − β|1⟩) + |11⟩(α|1⟩ − β|0⟩)
Now Alice measures her two qubits. What is the chance that she sees 00? We can see above that it is the square of 12 , which is 14 . Similar reasoning applies to the other three cases.
Bob receives the two classical bits ab from Alice, and then Bob does the following: • Ifb=1,thenheappliesX tohisqubit.
• Ifa=1,thenheappliesZ tohisqubit.
The result is:
: α|0⟩ + β|1⟩
01 : X(α|1⟩ + β|0⟩) =
α|0⟩ + β|1⟩ α|0⟩ + β|1⟩
ZX(α|1⟩ − β|0⟩) = α|0⟩ + β|1⟩
Note that in the process of teleporting a qubit from Alice to Bob, we destroyed Alice’s qubit. This is the way it is supposed to be: we cannot clone an unknown qubit, as we will discuss next.
10 11 :
: Z(α|0⟩ − β|1⟩) =
[No-cloning]
We can copy a classical bit; what about a qubit?
Theorem: No quantum operation maps |ψ⟩|0⟩ to |ψ⟩|ψ⟩.
Proof: Suppose we have such an operation U, so, for every |ψ⟩:
U |ψ⟩|0⟩ = |ψ⟩|ψ⟩ (1) Let us pick |ψ1⟩ and |ψ2⟩, such that they are not orthogonal and not proportional, that is:
⟨ψ1|ψ2⟩ ̸= 0 ∧ ⟨ψ1|ψ2⟩ ̸= 1 (2) Now we will do a calculation that uses the following property:
We calculate as follows. ⟨ψ1 |ψ2 ⟩ =
⟨(v1 ⊗ v2)|(w1 ⊗ w2)⟩
⟨v1|w1⟩ ⟨v2|w2⟩ (3)
(⟨0|0⟩ = 1)
(use property (3))
(U preserves inner products) (use our assumption (1)) (use property (3))
⟨ψ1 |ψ2 ⟩ ⟨0|0⟩
= ⟨(ψ1 ⊗ |0⟩)|(ψ2 ⊗ |0⟩)⟩
= ⟨U (ψ1 ⊗ |0⟩)|U (ψ2 ⊗ |0⟩)⟩
= ⟨(ψ1 ⊗ |ψ1 ⟩)|(ψ2 ⊗ |ψ2 ⟩)⟩
= ⟨ψ1 |ψ2 ⟩2
From this we get that either ⟨ψ1|ψ2⟩ = 0 or ⟨ψ1|ψ2⟩ = 1. This contradicts Equation (2). QED. Transition to MP3: What is the machine language of quantum circuits?
Main Point 3: Universal sets of operations.
[Universal sets exists]
S is a universal set for a model if any gate from that model can be realized using only combinations of gates from S.
For classical computing, {NAND} is a universal set. Let us review why. We will get there in three steps. Our starting point is that we know that {AND,OR,NOT} is universal. First, we implement OR in terms of AND and NOT gates using De Morgan’s rule:
OR(x1, x2) = NOT(AND(NOT(x1), NOT(x2))) We can also use standard notation:
x1 ∨ x2 = ¬((¬x1) ∧ (¬x2)) Second, we implement AND in terms of NAND gates:
AND(x1, x2) = NOT(NAND(x1, x2) Third, we implement NOT in terms of NAND gates:
NOT(x1) = NAND(x1, 1)
Notice that we used a helper bit, initialized to 1. So, the statement that, for classical computing, {NAND} is a universal set means that NAND gates plus helper bits is a universal set. We know that helper bits are important in reversible computing and we will use them again and again.
For reversible computing, we observe that NAND is not reversible, so, we have to think harder. Fortunately, NOT is reversible: it is a bijection on {0, 1}, as the following table shows:
input output 01 10
Indeed, NOT(NOT x ) = x.
Now let us look at CNOT, also known as controlled-NOT:
Or, in table form:
CNOT(x1, x2)
= (x1, x1 ⊕ x2)
input output 00 00
This mapping is a bijection so CNOT is good for reversible computing. Indeed,
CNOT(CNOT xy ) = xy
Now let us take the CNOT idea a step further and look at CCNOT, also known as controlled-
controlled-NOT, and in quantum computing known as the Toffoli gate: CCNOT(x1, x2, x3) = (x1, x2, AND(x1, x2) ⊕ x3)
Or, in table form:
input output
This mapping is a bijection so CCNOT is good for reversible computing. Indeed, CCNOT(CCNOT xyz ) = xyz
Now for the crux about reversible computing: we can implement NAND using CCNOT: NAND(x1, x2) = CCNOT(x1, x2, 1)
So, for reversible computing, CCNOT gates plus helper bits is a universal set. Additionally, let us note that we can get |1⟩ from |0⟩ by using CCNOT:
CCNOT(1, 1, 0) = (1, 1, 1)
So, helper bits can always be initialized to 0. Or, if we prefer, helper bits can always be initialized to 1.
For probabilistic computing, {NAND,CoinFlipp} is a universal set. Here, CoinFlipp is a coin flip operation on a single bit operating with bias p. In practice, {NAND,CoinFlip1 } is a universal
set; the fair coin can simulate any biased coin with arbitrary precision.
For quantum computing, {CCNOT,H} is a universal set. This set can express all real unitary
matrices. Once we add S, we can also express all complex unitary matrices. ()
[Universal sets can be quite different]
For quantum programming, the gate set {CCNOT,H,S} is difficult to work with. Rather than using CCNOT for everything, CNOT would be easier. So, for quantum programming, people prefer to use the universal gate set {CNOT, H, T }, where
10 0 eiπ/4
How do we know that {CNOT, H, T } is universal? All we need to do is to implement everything in the universal gate set {CCNOT,H,S}, which boils down to implementing CCNOT and S. Turns out, CCNOT has a well-known implementation that uses six CNOT gates and some H gates and T gates. Additionally, the foundational people have shown that no combination of five or fewer CNOT gates, plus 1-qubit gates, implements CCNOT. Also, S has an easy implementation in terms of T ; indeed, S = (T T ):
The foundational people love the gate set {CCNOT,H,S} because they can prove easily that it is
universal.
[Different quantum computers support different sets of matrices]
Aside from a gate set that we can easily prove universal and a gate set that we can use for programming, we also need a gate set that we can implement without too much trouble. The concept of a finite universal gate set is welcome here; it gives the implementers a finite list of tasks to do.
Which finite gate set is easy to implement? Turns out, this depends on the qubit technology. Here are two examples.
The gates are defined as follows. u(λ)=
u2 (φ, λ) u3(θ, φ, λ) =
cos (θ/2) −eiλ sin (θ/2)
eiφ sin (θ/2) ei(λ+φ) cos (θ/2) ()
Rx(θ) = Ry(θ) = Rz(θ) =
e−iθY /2 =
Quantum computer IBMQX5
Ion Trap ( .)
u1, u2, u3, CNOT Rx,Ry,Rz,XX
= √1 1 −eiλ 2 eiφ ei(λ+φ)
cos (θ/2) −i sin (θ/2)
−i sin (θ/2) cos (θ/2) ()
cos (θ/2) − sin (θ/2) sin (θ/2) cos (θ/2)
cosφ 0 0 −isinφ √1 0 cosφ −isinφ 0 2 0 −isinφ cosφ 0
−isinφ 0 0 cosφ
e−iθZ/2 =
For each gate set, we can prove that it is universal like we did above: show that we can implement everything in a universal gate set.
Notice that having one gate set for programming and another gate set at the level of the quantum computer creates a compilation task. Specifically, we must translate each program level gate to some quantum-computer-level gates.
Transition to Close: So there you have it.
Review: We can draw circuit diagrams and do amazing little tasks, and we can talk about
universal sets of operations.
Strong finish: Now we are ready to study quantum algorithms, which we will express as quantum circuits.
Call to action: Play around with the quantum circuit simulator that we linked online. 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com