Quantum Programming Implementation: Compilers, Peephole Optimization
Mar 8, 2021
Quantum Programming, by Outline Implementation: compilers, peephole optimization; 100 minutes; Mar 8, 2021
Copyright By PowCoder代写 加微信 powcoder
Hook: How can we make a quantum circuit smaller and more reliable? When we do many, small, local transformations, the result can be major improvements in circuit size and overall reliability. Such transformations are known as peephole optimizations and can be based on matrix identities.
Purpose: Persuade you that peephole optimization in quantum compilers is nontrivial.
1. Peephole optimization can be done by propagate-and-cancel.
2. Peephole optimization can be done by search-and-replace.
3. Peephole optimizers have impressive performance and can be proved correct.
Transition to Body: Let us begin with a straightforward approach.
Main Point 1: Peephole optimization can be done by propagate-and-cancel.
[We can find matrix identities for commutation and cancellation]
[Use commutation rules to move a gate to the right while hoping that cancellation applies] [If the gate doesn’t get cancelled, return it to its original position]
Transition to MP2: Peephole optimizers can also be entirely local in nature.
Main Point 2: Peephole optimization can be done by search-and-replace. [Identify a pattern of gates and replace it with an equivalent pattern]
[Move Rz gates based on an analysis of a subcircuit of CNOT and Rz gates] [Merge back-to-back Rz gates]
Transition to MP3: Now let us turn to the outcomes of peephole optimization.
Main Point 3: Peephole optimizers have impressive performance and can be proved correct. [The optimization schedule can be nonintuitive]
[The decrease in number of gates can be impressive]
[Peephole optimizers can be proved correct]
Transition to Close: So there you have it.
Review: We can do peephole optimization by propagate-and-cancel and by search-and-replace.
The results are impressive and can be proved correct.
Strong finish: When we scale to 100+ qubits, we cannot simulate the output of a quantum compiler to check that it is correct. Additionally, the low reliability and probabilistic nature of quantum computers make the outcome of measurements difficult to validate. Instead, verification of the compiler itself appears to be the best option.
Call to action: Implement a peephole optimizer yourself and try out different matrix identities.
Detailed presentation
Hook: How can we make a quantum circuit smaller and more reliable? When we do many, small, local transformations, the result can be major improvements in circuit size and overall reliability. Such transformations are known as peephole optimizations and can be based on matrix identities.
Purpose: Persuade you that peephole optimization in quantum compilers is nontrivial.
1. Peephole optimization can be done by propagate-and-cancel.
2. Peephole optimization can be done by search-and-replace.
3. Peephole optimizers have impressive performance and can be proved correct.
Transition to Body: Let us begin with a straightforward approach.
Main Point 1: Peephole optimization can be done by propagate-and-cancel.
[We can find matrix identities for commutation and cancellation]
The following paper presents an optimizer for quantum circuits: A Verified Optimizer for Quantum Circuits, by , , Shih- , Xiaodi Wu, and , in POPL 2021. The paper works with the gate set {H, X, Rz, CNOT }. Here, Rz(k) means a rotation by kπ.
The first optimization technique is Not propagation. We use these matrix identities:
Xq;Hq = Hq;Zq
X q; Rz(k)q = Rz(2−k)q; X q
Xq1;CNOTq1q2 = CNOTq1q2;Xq1 Xq2 X q2; CNOT q1q2 = CNOT q1q2; X q2
Xq;Xq = Iq
The second optimization technique is Hadamard reduction. We use these matrix identities:
Above, P is the gate Rz(12) and P† is its inverse Rz(23). After all this, apply H H = I. 3
[Use commutation rules to move a gate to the right while hoping that cancellation applies] The third and fourth optimization are single-qubit gate cancellation and two-qubit gate cancellation. Both use the following idea. We write a propagate function that takes as inputs:
• an instruction list,
• a gate to propagate, and
• a set of rules for commuting and cancelling that gate.
At each iteration, propagate performs the following actions:
if (a cancellation rule applies)
apply that rule and return the modified list
if (a commutation rule applies)
commute the gate and recursively call propagate on the remainder of the list
else return the original list (with the gate in its original position ) The cancellation rules:
The commutation rules:
XX=I CNOT CNOT = I
Rz(k) Rz(k′) = Rz(k + k′)
[If the gate doesn’t get cancelled, return it to its original position]
Gate cancellation uses back-tracking: if the gate doesn’t get cancelled, return it to its original position. After that we can try propagate-and-cancel with a different gate.
Transition to MP2: Peephole optimizers can also be entirely local in nature.
Main Point 2: Peephole optimization can be done by search-and-replace.
[Identify a pattern of gates and replace it with an equivalent pattern]
The fifth optimization is Rotation merging. The first step is to identify a subcircuit of CNOT and Rz gates. We can think of this subcircuit as being “walled off” by H and X gates. A key reason for why Hadamard reduction is valuable is that it gets H gates out of the way such that subcircuits with CNOT and Rz gates can be larger.
[Move Rz gates based on an analysis of a subcircuit of CNOT and Rz gates] Move Rz gates based on phase polynomials.
[Merge back-to-back Rz gates]
We can combine Rz(k) and Rz(k′) to get Rz(k + k′).
Transition to MP3: Now let us turn to the outcomes of peephole optimization.
Main Point 3: Peephole optimizers have impressive performance and can be proved correct.
[The optimization schedule can be nonintuitive] The optimization schedule: 0, 1, 3, 2, 3, 1, 2, 4, 3, 2.
not propagation
Hadamard reduction single-qubit gate cancellation two-qubit gate cancellation rotation merging
The optimization schedule has ten passes and runs (2) three times. The single-qubit gate cancella- tion (2) and rotation merging (4) were the most effective at reducing gate count.
Timing of the optimizer, geometric mean:
Qiskit t|ket⟩ Nam (L) Nam (H) voqc 0.812s 0.129s 0.002s 0.018s 0.013s
[The decrease in number of gates can be impressive] The following table shows the number of gates in the circuit.
Benchmark adder 8
gf2-8 mult
qcla mod 7
Geo. mean reduction
Original Qiskit t|ket⟩ 900 805 775 883 804 806 884 793 780
– 10.1% 10.6%
Nam (L) 646 712 636
Nam (H) voqc 606 682 712 705 624 723
Above, the row for qcla mod 7 shows a problem with Nam (L) and Nam (H): in each case, the resulting optimized circuit was inequivalent to the original circuit. So, those optimizers have bugs!
[Peephole optimizers can be proved correct]
Hietala and co-authors implemented their optimizer in Coq and proved that it is correct. Thus,
even if it optimizes less than Nam (L) and Nam (H), it always works. Transition to Close: So there you have it.
Review: We can do peephole optimization by propagate-and-cancel and by search-and-replace. The results are impressive and can be proved correct.
Strong finish: When we scale to 100+ qubits, we cannot simulate the output of a quantum compiler to check that it is correct. Additionally, the low reliability and probabilistic nature of quantum computers make the outcome of measurements difficult to validate. Instead, verification of the compiler itself appears to be the best option.
Call to action: Implement a peephole optimizer yourself and try out different matrix identities.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com