PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum circuit optimizations for NISQ architectures

Beatrice Nash, Vlad Gheorghiu, Michele Mosca

arXiv:1904.01972v3quant-ph

TL;DR

Sparse qubit connectivity makes it difficult to compile generic circuits for current quantum devices. This paper synthesizes connectivity-respecting circuits from a device graph and a circuit over {CNOT, RZ}; it reports CNOT-count reductions and compares performance with Qiskit across circuit Hadamard-to-CNOT ratios.

  • Problem

    Sparse qubit connectivity limits near-term devices, while many compilers require input circuits to already account for hardware connectivity.

    Source: §I · p. 1

  • Method

    The heuristic takes a device-connectivity graph and a circuit over {CNOT, RZ} and synthesizes an output circuit that respects that connectivity.

    Source: §I · p. 1

  • Results

    The method significantly reduces CNOT count versus current synthesis methods; for Hadamard-to-CNOT ratios ⪅0.05–0.07 it consistently outperforms Qiskit, but does increasingly worse as the ratio grows.

    Source: §I · p. 1, §IV · p. 8

  • Takeaways & Limitations

    The scheme targets arbitrary device connectivity and was applied to Bristlecone, Tokyo, and Acorn chip graphs, with additional tests on random 20-qubit circuits across sparseness levels.

    Source: §I · p. 1, §V · p. 8

    The method does not weight connectivity edges by differing CNOT error rates; weighting edges by error rate is proposed as future work.

    Source: §V · p. 8

Abstract

from arXiv · show

Currently available quantum computing hardware platforms have limited 2-qubit connectivity among their addressable qubits. In order to run a generic quantum algorithm on such a platform, one has to transform the initial logical quantum circuit describing the algorithm into an equivalent one that obeys the connectivity restrictions. In this work we construct a circuit synthesis scheme that takes as input the qubit connectivity graph and a quantum circuit over the gate set generated by $\{\text{CNOT},R_{Z}\}$ and outputs a circuit that respects the connectivity of the device. As a concrete application, we apply our techniques to Google's Bristlecone 72-qubit quantum chip connectivity, IBM's Tokyo 20-qubit quantum chip connectivity, and Rigetti's Acorn 19-qubit quantum chip connectivity. In addition, we also compare the performance of our scheme as a function of sparseness of randomly generated quantum circuits. Note: Recently, the authors of arXiv:1904.00633 independently presented a similar optimization scheme. Our work is independent of arXiv:1904.00633, being a longer version of the seminar presented by Beatrice Nash at the Dagstuhl Seminar 18381: Quantum Programming Languages, pg. 120, September 2018, Dagstuhl, Germany, slide deck available online at https://materials.dagstuhl.de/files/18/18381/18381.BeatriceNash.Slides.pdf.

I. INTRODUCTION

Sparse hardware connectivity constrains quantum-circuit compilation, while this work synthesizes circuits to respect a supplied device graph. The authors report reduced CNOT counts from considering connectivity during synthesis, using a heuristic because exact optimization appears intractable.

I. INTRODUCTION

  • The method accepts a desired transformation and device-connectivity graph, then outputs a circuit that respects the allowed connectivity.The target gate set is generated by CNOT and arbitrary RZ rotations.Source: §I · p. 1
  • The method is a heuristic because finding the exact optimal solution appears intractable.Source: §I · p. 1
  • Synthesizing while accounting for connectivity produces sizable CNOT-count reductions over synthesizing first and routing afterward.The reductions depend on connectivity sparseness and input-transformation complexity.Source: §I · p. 1
  • The authors describe their work as independent of a similar scheme in [6] and as a longer version of a 2018 Dagstuhl seminar presentation.Source: §I · p. 1

II. METHODS

Remote CNOTs can be implemented with adjacent-qubit gates, but their cost grows with separation. The method adapts circuit synthesis to the device graph rather than routing an already synthesized circuit afterward.

II. METHODS

  • For non-adjacent logical qubits, a CNOT can be implemented by a sequence of CNOTs between adjacent physical qubits.The paper illustrates this for q1 as control and q4 as target on a four-qubit linear-neighbor graph.Source: §II · p. 1, Figure 1 · p. 2
  • The illustrated q1-to-q4 templates use 4(l−1) CNOT gates for the circuit in Fig. 1(b) and 1+6(l−1) gates for the swap circuit in Fig. 1(c).Here l is the distance between the two qubits; dynamic reassignment can remove the last two swaps in Fig. 1(c).Source: §II · pp. 1–2, Figure 1 · p. 2
  • These general templates can be extended to any physical-qubit connectivity graph.Source: §II · p. 1
  • Existing synthesis methods ignore connectivity, so replacing their CNOTs with connectivity-respecting templates can drastically increase CNOT count on sparse graphs.Source: §II · p. 2

A. Linear reversible circuit synthesis

The section adapts linear-reversible circuit synthesis to connectivity constraints by choosing row operations that can be performed efficiently on the hardware graph. Its worst-case output size is O(n^2), regardless of connectivity.

A. Linear reversible circuit synthesis

  • O(n^2) is the proposed algorithm’s worst-case output-circuit size under connectivity constraints, compared with O(n^3 log n) for the earlier approach after connectivity is accounted for.Source: A. Linear reversible circuit synthesis · p. 2
  • The synthesis input is an n×n binary matrix representing the desired linear transformation, and the output is a circuit that produces it [3].The algorithm is described as an optimized Gaussian-elimination approach.Source: A. Linear reversible circuit synthesis · p. 2
  • The algorithm reduces the matrix to upper-triangular form, repeats the process after transposition, then constructs the output circuit from the row operations.The output construction uses the transposed-stage operations first with controls and targets flipped, followed by the initial-stage operations in reverse order.Source: A. Linear reversible circuit synthesis · p. 2
  • For sparse near-term connectivity, the algorithm groups row operations instead of using partitioning, which works well when connectivity is at least about 85%.The authors report that their algorithm works best without partitioning for connectivity as sparse as near-term devices.Source: A. Linear reversible circuit synthesis · pp. 2–3
  • Reordering row operations for the six-qubit example reduces the required CNOT count from 16 to 6 under restricted connectivity.The alternative sequence eliminates the same entries while using shorter-distance operations.Source: A. Linear reversible circuit synthesis · p. 3
  • The method seeks a short set of graph paths hitting the nodes associated with rows to eliminate, then converts those paths into row operations.Source: A. Linear reversible circuit synthesis · p. 3

B. Steiner tree problem reduction

The method reduces connectivity-constrained row elimination to a Steiner-tree problem, then converts the tree into adjacent-node operations. It uses an approximation for the NP-hard minimum-tree problem and achieves an O(n^2) operation bound regardless of connectivity.

B. Steiner tree problem reduction

  • For each column, the method selects terminals from the control and rows to eliminate, then approximates a minimum-weight Steiner tree on the connectivity graph.If the diagonal entry is zero, it first uses the shortest path to a suitable row to add a 1 on the diagonal; it then repeats the process after transposing the matrix.Source: B. Steiner tree problem reduction · pp. 3–4
  • The tree is split into edge-disjoint subtrees, traversed to form row operations, and operations on Steiner nodes are undone while terminal rows are eliminated.After transposition, the smallest node is used as control to preserve triangular form, at a maximum of 4*d additional gates.Source: B. Steiner tree problem reduction · pp. 3–4
  • The tree-to-operation sequence uses approximately 4*(l-d) gates, where l is the number of edges and d the number of terminals excluding the control; a minimum-edge tree gives the optimal solution.Each edge is traversed exactly once.Source: B. Steiner tree problem reduction · p. 4
  • The minimum Steiner-tree problem is NP-hard, so the method uses approximations; the cited best approximation is within a factor of 1.39 of optimal.The passage says this improved on the previous bound of 1.55.Source: B. Steiner tree problem reduction · p. 4
  • The approximation algorithm grows breadth-first searches from terminals and merges paths when they collide; trials suggest it can yield large CNOT-count reductions.Its runtime is O(d*(|V|+|E|)); the choice of approximation algorithm depends on efficiency and performance requirements.Source: B. Steiner tree problem reduction · p. 4
  • The synthesis requires O(n^2) operations overall, regardless of connectivity, because it computes O(n) trees of size O(n).Each tree requires O(n) operations.Source: B. Steiner tree problem reduction · p. 5

C. CNOT + phase circuit synthesis

The method represents a CNOT+RZ circuit by its phase polynomial and linear transformation, then synthesizes a connectivity-aware circuit. It adapts parity-network construction by grouping eliminations through approximate Steiner trees.

C. CNOT + phase circuit synthesis

  • The target unitary is specified by a phase polynomial f and a matrix A for the basis-state transformation.Each nonzero Fourier coefficient of f corresponds to a parity that receives an RZ rotation.Source: C. CNOT + phase circuit synthesis · pp. 5–6
  • Finding an exact minimal parity network is NP-hard, so the cited approach uses a heuristic approximation.The heuristic is described in.Source: C. CNOT + phase circuit synthesis · p. 5
  • A parity matrix P represents the parities as columns and qubits as rows, and recursive splitting uses a selected row’s 0/1 entries.After splitting P into P0 and P1, the method recurses on each part and eliminates eligible rows in P1 using the selected row as control.Source: C. CNOT + phase circuit synthesis · pp. 5–6
  • The method follows the same series of steps as, modifying step 5 to compute an approximate Steiner tree of the connectivity graph and eliminate the selected rows together using row j as control.The selected set comprises rows i such that each element in row i of P 1 equals 1.Source: C. CNOT + phase circuit synthesis · p. 6
  • The constructed parity network supplies each required parity for its RZ rotation, then an appended circuit implements the remaining transformation AC^-1.This completes the target basis-state transformation after the phase polynomial has been implemented.Source: C. CNOT + phase circuit synthesis · pp. 5–6

III. RESULTS

The results section compares connectivity-aware synthesis with circuits synthesized under full connectivity and then adjusted for hardware constraints. It evaluates random circuits across varying connectivity and several device topologies.

III. RESULTS

  • The comparison evaluates output-circuit size against full-connectivity synthesis followed by connectivity adjustment, with further size optimization in both cases.The baseline methods are for linear reversible circuits and for CNOT+T circuits.Source: §III · p. 6
  • The experiments cover random circuits with varying connectivity and the Bristlecone, Tokyo, and Acorn device topologies.The random-circuit studies use 20 qubits; the named architectures have 72, 20, and 19 qubits, respectively, as indicated in the supplied captions.Source: §III · p. 6

IV. UNIVERSAL GATE SETS

The paper extends its connectivity-aware synthesis approach to universal gate sets by partitioning circuits into H-only and CNOT/phase segments. Its results compare output size across connectivity and show that performance against Qiskit depends on the Hadamard-to-CNOT ratio.

IV. UNIVERSAL GATE SETS

  • For random 20-qubit linear transformations, Fig. 8 compares circuit sizes across edge-probability sparseness; the method performs worse near full connectivity because it omits partitioning used by [3].The supplied passage notes that NISQ devices have very sparse, nearest-neighbor connectivity.Source: Figure 8 · p. 6
  • The supplied figures also cover random transformations on Bristlecone, Tokyo, and Acorn topologies, with comparisons against connectivity-adjusted full-connectivity synthesis.The captions identify the architectures and comparison scope but do not provide numerical outcomes.Source: Figure 11 · p. 7, Figure 12 · p. 7, Figure 13 · p. 7
  • A universal-gate circuit is partitioned into H-only and CNOT/phase segments, and the earlier connectivity-aware method is applied to the CNOT/phase segments.The approach seeks to make those segments large.Source: §IV · pp. 7–8
  • A forward-then-backward commuting heuristic assigns gates to the largest CNOT/phase segments they can join.The procedure commutes gates until they meet a noncommuting gate, first forward and then backward.Source: §IV · p. 8
  • For 1000-gate input circuits, the method consistently outperforms Qiskit at Hadamard-to-CNOT ratios of about 0.05–0.07 or less, but does increasingly worse as the ratio grows.The method works best when CNOT-only segments are large; the experiment’s input circuits do not account for connectivity.Source: §IV · p. 8

V. CONCLUSIONS AND OPEN QUESTIONS

The paper presents a connectivity-aware synthesis scheme for circuits over {CNOT, RZ} and applies it to three quantum-chip connectivity graphs. It also compares performance across random 20-qubit circuits of varying sparseness and identifies edge weighting by CNOT error rate as future work.

V. CONCLUSIONS AND OPEN QUESTIONS

  • The synthesis scheme takes a qubit connectivity graph and a circuit over {CNOT, RZ} as input and outputs a circuit respecting device connectivity.Source: §V · p. 8
  • The authors apply the scheme to Google's Bristlecone 72-qubit, IBM's Tokyo 20-qubit, and Rigetti's Acorn 19-qubit connectivity graphs.Source: §V · p. 8
  • Performance is compared across random 20-qubit circuits as a function of sparseness; weighting connectivity edges by CNOT error rate is proposed for future work.Source: §V · p. 8

Appendix A: Example

Figure 15 works through synthesis of the linear transformation from Fig. 3(a) on the connectivity in Fig. 3(b). It describes assembling the synthesized circuit from gates in two step ranges, with different reversal and control-target instructions.

Appendix A: Example

  • Figure 15 gives a worked synthesis example for the linear transformation in Fig. 3(a) on the connectivity in Fig. 3(b).Source: Figure 15 · p. 11
  • The circuit construction first combines gates from steps 8–11 and switches their controls and targets.Source: Figure 15 · p. 11
  • It then combines gates from steps 1–7 in reverse order, leaving controls and targets as shown.Source: Figure 15 · p. 11

Related papers

Loading 1904.01972v3…