Quantum Programming Implementation: Compilers
May 19, 2020
Quantum Programming, by Outline Implementation: compilers; 100 minutes; May 19, 2020
Copyright By PowCoder代写 加微信 powcoder
Hook: How do we get programs in languages such as PyQuil, Cirq, and Qiskit to run on a quantum computer? The answer is a compiler that translates programs to a native gate set. What are the challenges in building such a compiler?
Purpose: Persuade you that a quantum compiler can be straightforward.
1. The native gate sets are all universal yet different.
2. The qubit registers are connected in different ways.
3. The key steps are gate selection, qubit allocation, and qubit swapping.
Transition to Body: Let us begin with a look at the target instructions that we can use.
Main Point 1: The native gate sets are all universal yet different.
[A gate set should be universal, that is, able to implement any quantum program] [A gate set must contain at least one multi-qubit gate to be universal]
[We can compare the gate sets of some of today’s quantum computers]
Transition to MP2: Now let us look at how the qubit registers are connected.
Main Point 2: The qubit registers are connected in different ways. [Connectivity varies wildly across quantum technologies] [Multi-qubit gates require a connection between the qubit registers] [We can compare the connectivity on today’s quantum computers]
Transition to MP3: Let us design a quantum compiler.
Main Point 3: The key steps are gate selection, qubit allocation, and qubit swapping. [Let us compare the tasks of a classical compiler and a quantum compiler] [Register allocation is somewhat similar to qubit allocation]
[Likely we need qubit swapping to make a compiled program work]
Transition to Close: So there you have it.
Review: Every quantum computer today tends to be unique in the gates that it supports, in its
connectivity, and in the reliability of its operations.
Strong finish: How do we design retargetable quantum compilers, that is, compilers that we can retarget easily from one quantum computer to another?
Call to action: Now is a great time to design the next generation of quantum compilers.
Detailed presentation
Hook: How do we get programs in languages such as PyQuil, Cirq, and Qiskit to run on a quantum computer? The answer is a compiler that translates programs to a native gate set. What are the challenges in building such a compiler?
Purpose: Persuade you that a quantum compiler can be straightforward.
1. The native gate sets are all universal yet different.
2. The qubit registers are connected in different ways.
3. The key steps are gate selection, qubit allocation, and qubit swapping.
Transition to Body: Let us begin with a look at the target instructions that we can use. Main Point 1: The native gate sets are all universal yet different.
[A gate set should be universal, that is, able to implement any quantum program] Quantum programs consist of unitary operations so we need the target platform to enable us to implement any unitary operation. The implementation must be doable solely by product and matrix tensor product. For example, a program may use Z, but the quantum computer supports H,X. Now we can use the identity
Z=HXH to implement Z on the computer computer.
[A gate set must contain at least one multi-qubit gate to be universal]
Consider two famous universal gate sets: {H, T , CNOT} and {H, S, CCNOT}. Notice that while H, T , S are single-qubit gates, CNOT is a two-qubit gate, and CCNOT is a three-qubit gate. We need at least one multi-qubit gate to have a universal set. This means that some qubit registers have to be connected to enable multi-qubit operations.
[We can compare the gate sets of some of
Quantum computer #qubits IBMQX5 16
today’s quantum computers] Gate set
u1, u2, u3, CNOT
Rx(θ) (θ = kπ/2 where k ∈ Z), Rz(θ), CZ Rxy (φ, θ), Rz (θ), CNOT, CZ, CCNOT, CCZ Rx(θ), Ry(θ), Rz(θ), XX
Rigetti Agave
Neutral Atoms (U. Wisconsin) Ion Trap ( .)
Notice that each of those quantum computers has at least one single-qubit gate and at least one multi-qubit gate. Also, the Neutral Atoms quantum computer from U. Wisconsin is the only one that supports a three-qubit gate, namely CCNOT.
Here are the definitions of the gates on those quantum computers:
u2(φ,λ)=√1(1 −eiλ) 2 eiφ ei(λ+φ)
u3(θ, φ, λ) = Rx(θ) = Ry(θ) = Rz(θ) = Rxy (φ, θ) =
−eiλ sin (θ/2) ) ei(λ+φ) cos (θ/2)
cos (θ/2) −i sin (θ/2)) e−iθX/2 = −i sin (θ/2) cos (θ/2)
( cos (θ/2) eiφ sin (θ/2)
(cos (θ/2) e−iθY /2 = sin (θ/2)
e−iθZ/2 = 0 ( cos (θ/2)
−ieiφ sin (θ/2)
1 0 0 0 0 1 0 0 0 0 0 1 0010
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 −1
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 00000001 00000010
1 0 0 0 0 0 0 0100000 0010000 0001000 0000100 0 0 0 0 0 1 0
0 00000010
0 0 0 0 0 0 0 −1
−isinφ 2 0 −isinφ cosφ 0
−isinφ 0 0 cosφ The XX gate is also known as the Mølmer-Sørensen gate.
cosφ 0 0 XX(φ)=√10 cosφ−isinφ 0
− sin (θ/2)) cos (θ/2)
) −ie−iφ sin (θ/2))
Transition to MP2: Now let us look at how the qubit registers are connected. Main Point 2: The qubit registers are connected in different ways.
[Multi-qubit gates require a connection between the qubit registers]
One of the most error-prone aspects of a quantum computer is the connection between two qubit registers. We need those connections to support multi-qubit gates. As a rule of thumb for today’s quantum computers, two-qubit gates are ten times more unreliable and ten times slower than one-qubit gates.
[Connectivity varies wildly across quantum technologies]
A quantum computer with ion-trapped qubits tend to have every qubit register connected to every other qubit register. Thus the graph that represents qubit register connectivity is dense.
In contrast, a quantum computer with superconducting qubits tend to have each qubit regis- ter connected to only a few other qubit registers. Thus the graph that represents qubit register connectivity is sparse. For a while, all such quantum computers supported only planar graphs of connectivity, but recently IBM have introduced nonplanar connectivity.
[We can compare the connectivity on today’s quantum computers] IBMQX5:
In the diagram above, directional arrows show entanglement capabilities. For example, we could perform the operation CNOT(Q1, Q2), but not the operation CNOT(Q2, Q1). However, we can implement CNOT(Q2, Q1) using the following identity:
CNOT(Q2, Q1) = (H ⊗ H) CNOT(Q1, Q2) (H ⊗ H)
Rigetti Agave:
Notice that the edges are undirected. This makes sense because the supported two-qubit gate is CZ which is symmetric in its two arguments. If we want to use CNOT, then we can get it from CZ by using the following identity:
CNOT(1,2) = (I ⊗ H) CZ(1,2) (I ⊗ H) 5
Transition to MP3: Let us design a quantum compiler.
Main Point 3: The key steps are gate selection, qubit allocation, and qubit swapping.
[Let us compare the tasks of a classical compiler and a quantum compiler]
Phase Front end
Middle end Back end
Classical compiler
Build program representation (Type check)
Instruction selection
Register allocation
Quantum compiler
Build program representation ⟨No type check?!⟩
⟨Too early to optimize?!?!⟩ Gate selection
Qubit allocation
(Qubit swapping)
Let us design an nonoptimizing quantum compiler that targets the Rigetti Agave. The lack of optimizations means that the differences with a classical compiler show up in the back end.
The source language supports {D, H, S, T , X, CNOT}. Here, ()
D=T†=10 0 1−i
This language is sufficient for convenient programming of the Deutsch-Jozsa algorithm, the Bernstein- Vazirani algorithm, Simon’s algorithm, Grover’s algorithm, etc.
Our target language supports {Rx,Rz,CZ}, where Rx must be applied to (kπ/2)(k ∈ Z). The first task is gate selection, which we can do manually as follows.
CNOT(i, j) = D=
(I⊗H)CZ(i,j)(I⊗H) − e i π8 R z ( − π4 )
iRy(−π2)Rx(π)
T = X = Ry(θ) =
eiπ8 Rz(π4)
Rz(−π2) Rx(θ) Rz(π2)
Notice that for the translation of H, we use Ry in an intermediate representation, which we then translate to gates in the target.
Notice that for H and for X, we get almost the right result, except that we have an additional factor of i. This is okay because ultimately we care only about the probability distribution over the bitstrings when we measure, and multiplying by i changes nothing. Similar story for D and T .
[Register allocation is somewhat similar to qubit allocation]
In a classical compiler, register allocation maps a variable in the source program to a register in the target. In a quantum compiler, qubit allocation maps each qubit in the source program to a qubit register in the target. If every qubit register is connected to every other qubit register, then for our example compiler, we are done because CNOT is always supported.
In a classical compiler, register allocation may have to map some variables to locations on the stack, rather than to registers. This is because we may have more variables than we can fit into the available registers. However, a quantum compiler cannot allocate to stack: the only resource we have for storing source-level qubits are target-level qubit registers.
[Likely we need qubit swapping to make a compiled program work]
We want to compile to Rigetti Agave, which has sparse connectivity. For example, let us consider Grover with n=3 and f(000) = 1, and f(abc) = 0 for abc ̸= 000. At this source level, my way of programming this algorithm uses all of CNOT(0, 1) and CNOT(0, 2) and CNOT(1, 2), and we know that for CNOT(i,j), we will want to use CZ(i,j). Notice that no matter how we do qubit allocation, at least one of those CNOT operations will work two qubit registers that have no edge between them.
Let us decide that our qubit allocation is:
0 → 0 1 → 1 2 → 2
In Rigetti Agave we have an edge between 0 and 1, and we have an edge between 1 and 2, but no edge between 0 and 2. How do we implement CZ(0,2)? The only way to make this happen is to bring the qubits in those registers to two registers that are connected. This is where we use qubit swapping.
CZ(0, 2) =
Swap(i, j) =
Swap(1, 2) CZ(0, 1) Swap(1, 2)
CNOT(i, j ) CNOT(j, i) CNOT(i, j)
We can translate those uses of CNOT into uses CZ, as discussed earlier. Transition to Close: So there you have it.
Review: Every quantum computer today tends to be unique in the gates that it supports, in its connectivity, and in the reliability of its operations.
Strong finish: How do we design retargetable quantum compilers, that is, compilers that we can retarget easily from one quantum computer to another?
Call to action: Now is a great time to design the next generation of quantum compilers. 7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com