Applies when the backend accepts continuous-angle rotations, i.e. pre-fault-tolerant hardware. It does not apply to a surface-code backend, where only a discrete gate set is available and synthesis becomes mandatory; the targets optimized here, depth and two-qubit gate count, are also the wrong targets there.

An abstract circuit (arbitrary-angle rotations, arbitrary two-qubit gates, all-to-all qubit indices); a device model giving the native gate set, coupling graph and calibration data; an approximation budget $\varepsilon$.

1. Abstract circuit → Routed circuitSatisfy the hardware connectivity constraint

   Routing maps logical qubits onto the device graph $G_D = (V_D, E_D)$ so that each two-qubit gate's qubits $(q,q')$ satisfy $(p(q), p(q')) \in E_D$, permuting the mapping with added SWAPs. The initial placement $p$ is not assumed: a preceding noise-aware pass scores candidate placements "for maximum expected overall fidelity". Routing then iterates the two-qubit gates in topological order and takes as the first slice $S_0$ the first set of interactions violating $E_D$ in which no logical qubit appears twice. Candidates $\{p''_0,\dots,p''_n\}$ are built by permuting the running placement $p'$ with a SWAP on each edge of $E_D$, an edge with no qubit in $S_0$ being ignored, and are scored by the distance between $S_0$'s interactions; ties defer to later slices $S_1, S_2, \dots$. A CX whose logical qubits sit at device-distance two under $p'$ may be emitted as a distributed CX instead, scored against the SWAP candidate. approximation: this greedy per-slice search stands in for the true optimum, since "finding an optimal solution to the routing problem in this manner is NP-complete in general".

   approximation

   Open this step

2. Routed circuit → Device circuitrebase to the native gate, then optimize

   What remains after routing is a rebase and a second round of optimisation. The architecture-dependent phase of t|ket> is stated as exactly those two parts — "a rebase, which maps the gates present in the circuit into those supported by the device, and a qubit mapping phase" — and the recommended pipeline puts the rebase last: FullPeepholeOptimise, then the qubit mapping pass, then SynthesiseIBM, then "rebasing to the final gate set". That ordering is possible because "many of the architecture-agnostic passes will additionally preserve any connectivity already satisfied by the inputs, allowing them to be applied after routing", which is also the paper's own account of how retargetability is bought without losing performance. The passes doing the work here are the two-qubit ones: CliffordSimp, which recognises rewrite identities that reduce CX count, and KAKDecomposition, which "reduces two-qubit subcircuits to at most three CX gates". assumption: The rebase target is treated as interchangeable when the result is measured: "as only single-qubit Hadamard gates are required for conversion between CX and CZ gates, we discount the gate-conversion step, and accept either gate set for the two-qubit gate-count and depth metrics". The reported outcome for the whole pipeline is a ratio, not a bound — two-qubit gate count out over in of $0.939 \pm 0.011$ at full connectivity, $1.773 \pm 0.034$ on Sycamore, $1.864 \pm 0.039$ on Aspen and $1.975 \pm 0.042$ on Rochester.

   assumption

A native-gate instruction sequence obeying the connectivity constraint, plus the overhead it added (SWAP count, T-count, depth) and the accumulated synthesis error.

given  a circuit, and a backend that accepts continuous-angle rotations
       i.e. pre-fault-tolerant hardware, with its own two-qubit gate
       and its coupling graph

decompose to the device's own two-qubit gate

emit arbitrary-angle single-qubit rotations directly
    # the hardware executes them, so no discrete synthesis stage is entered

route onto the coupling graph
    # hand the connectivity constraint to the layer below

optimize for two-qubit gate count and depth

return the decomposed, routed and optimized circuit

# this pipeline does not apply to a surface-code backend: only a discrete
# gate set is available there and synthesis becomes mandatory, and the
# targets optimized here, depth and two-qubit gate count, are also the wrong
# targets there

# no complexity is transcribed because the paper states none, in the
# abstract or the full text: its quantitative claims are benchmarks --
# extensively benchmarked and outperforming most competitors in circuit
# optimisation and qubit routing, in its own words. the cost of running the
# compiler itself is left unstated

The paper states no complexity for the pass pipeline, in the abstract or the full text; its quantitative claims are benchmarks — extensively benchmarked and outperforming most competitors in circuit optimisation and qubit routing, in its own words. The targets being optimized are two-qubit gate count and depth; the cost of running the compiler itself is left unstated.

• t|ket⟩, Cambridge Quantum's retargetable compiler, released as the Python module pytket

  • t|ket⟩: A Retargetable Compiler for NISQ Devices

    Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, Ross Duncan · 2020

  About

  t|ket⟩ is the quantum software development platform built by Cambridge Quantum Computing Ltd, whose heart the authors describe in this paper as "a language-agnostic optimising compiler designed to generate code for a variety of NISQ devices". The problem it takes on is the one this method names. The paper's own definition of the task is "the process of translating a circuit, presented in OpenQASM, and outputting an equivalent circuit that has been optimised and has the relevant device constraints satisfied, i.e. has been routed and converted to the correct gate set", and it excludes two things for two different reasons: high-level algorithm design as beyond the scope of a compiler, and low-level pulse optimisation as a topic "only in its infancy as a research topic". The optimisation targets are set by the device: the paper reports, on the authority of Arute et al.'s Sycamore paper rather than from a measurement of its own, that NISQ devices "provide fast, high-fidelity single-qubit rotations, with the error rates of multi-qubit operations being an order of magnitude worse", so it minimises two-qubit gate count (Definition 6.1, "the number of maximally-entangling two-qubit gates used in the circuit") and two-qubit depth (the $G = \mathrm{CX}$ case of the G-depth of Definition 6.2, and the quantity labelled 'Two-qubit depth overhead' on Figures 19 and 21). Single-qubit gates are omitted from the metric entirely to improve device-independence, "since the number of gates required varies significantly with the gate set" - the paper's example being that a single IBM U3 gate captures any rotation where up to three Rz and Ry gates would be needed.

  Methods

  The pass pipeline actually run in the benchmarks is named in the paper. The recommended generic routine, called 'FullPass', is the FullPeepholeOptimise pass, followed by the corresponding qubit mapping pass, then SynthesiseIBM, then a rebase pass into the target gate set. A chemistry-specific variant, 'ChemPass', prepends the PauliSimp pass to FullPass; PauliSimp recognises Pauli gadgets, the paper's canonical form (Definition 6.6) for a multi-qubit exponential of a Pauli string, and re-synthesises sequences of them. Inside the mapping pass, placement is cast as a subgraph monomorphism from the circuit's interaction graph into the device's connectivity graph, with edges dropped from the latest circuit slice and the match retried until one is found; routing then walks the two-qubit gates in topological order, and for the first slice of gates that violates connectivity it scores candidate SWAPs on the device's edges, breaking ties on later slices, and may substitute a distributed CX when the two logical qubits sit at distance two. These were compared against Qiskit's default compiler passes at optimisation level 3 and Quilc's default pass, the two alternatives the paper identifies as "able to do both general circuit optimisation and routing". Four targets were compiled for: the fully-connected graph (no routing needed), the connectivity graph of IBM Rochester (53 qubits), that of Google's Sycamore (53 qubits), and the Rigetti Aspen 16-qubit architecture, with all circuits over 16 qubits discarded for Aspen.

  Data

  Three test sets, all capped at 10^4 initial gates - a threshold chosen because circuits larger than that are "several orders of magnitude too large for near-term devices" and, in addition, because "the runtimes of Qiskit and Quilc already reach several minutes per circuit at this range". (i) The IBM set, circuits published for the Qiskit Developer Challenge, taken from https://github.com/iic-jku/ibm_qx_mapping and chosen because they resist peephole optimisation, which isolates routing performance. (ii) The UCCSD set, VQE circuits for the ground-state energy of small molecules under the unitary coupled cluster ansatz in Jordan-Wigner, parity or Bravyi-Kitaev encoding, "generated using Qiskit Aqua" and extending the set of Cowtan et al. (iii) The Product Formula set, Hamiltonian-simulation circuits used by Nam et al. from https://github.com/njross/optimizer, supplied in Quipper's ASCII format and converted to OpenQASM, included both before and after Nam et al.'s own optimisation, and with rotation angles edited upward to clear Qiskit's 10^-5 cutoff below which they would have been dropped as identities. The collated set is in the released repository: its arxiv-2003-10611/qasm_files directory holds 151 QASM circuits and its chem_qasm directory 78, over C2H4, CH2, H2, H2O, H4, H8, LiH and NH, in the sto-3g, 6-31G, cc-pVDZ and cc-pVTZ bases with frozen-core and complete variants, and the generator script in that directory drives qiskit-aqua ~0.6.4 with PySCFDriver and the UCCSD variational form, so the integrals come from PySCF through Qiskit.

  Code

  The compiler core is C++ and the released artefact is the Python module pytket, installed with `pip install pytket`. The paper gives the documentation as https://cqcl.github.io/pytket/, which no longer resolves - it returns HTTP 404 with no redirect, as do the deep links the paper gives for the operation types and the predicate list; the documentation is now at https://docs.quantinuum.com/tket/api-docs/, the URL PyPI itself lists as pytket's documentation link. Interoperability lives in separate plug-in packages, at the time of the paper pytket_qiskit, pytket_cirq, pytket_pyquil, pytket_projectq and pytket_pyzx. The paper states that "the pytket module is free for non-commercial use". Since then the C++ source has been published at https://github.com/CQCL/tket, which now resolves to https://github.com/Quantinuum/tket following the organisation's rename; GitHub records that repository as created on 2021-09-13, after this paper, listed as C++ and licensed Apache-2.0, and the pytket package on PyPI now carries the Apache-2.0 classifier. The benchmark scripts and data are separate, at https://github.com/CQCL/tket_benchmarking (now https://github.com/Quantinuum/tket_benchmarking), whose arxiv-2003-10611 directory holds bench.py, the two config CSVs, the QASM sets and per-compiler result CSVs; its README pins pytket==0.4.1 for the t|ket⟩ runs and pytket==0.5.2 with pytket-qiskit==0.4.1 and pytket-pyquil==0.4 for the Qiskit and Quilc runs.

  Results

  This sweep is compilation only: no quantum device executed anything. The three restricted targets entered as connectivity graphs - Figure 17 draws Rochester, Sycamore and Aspen, the fourth target being the fully-connected graph, which has no layout - and every run was on "a machine with a 2.3 GHz Intel Core i5 processor and 8 GB of 2133 MHz LPDDR3 memory, running MacOS Mojave v10.14", using t|ket⟩ v0.4.1, Quilc v1.16.3 and Qiskit Terra v0.12.0. The figure of merit is multiplicative overhead, which the figure captions define as the overhead in two-qubit gate count (or two-qubit depth) "from input circuit to output circuit", i.e. the compiled value over the input one, so a value below 1 is a reduction. Over all benchmark circuits (Fig. 18, means with standard error, columns FullConnectivity / Aspen / Rochester / Sycamore) the two-qubit gate count overheads were: FullPass 0.939 ± 0.011, 1.864 ± 0.039, 1.975 ± 0.042, 1.773 ± 0.034; Quilc 0.949 ± 0.010, 1.362 ± 0.022, 2.595 ± 0.074, 2.343 ± 0.061; Qiskit 0.958 ± 0.010, 2.896 ± 0.052, 3.201 ± 0.065, 2.789 ± 0.047. The depth overheads (Fig. 19) track them: FullPass 0.937 ± 0.011, 1.844 ± 0.040, 1.924 ± 0.041, 1.780 ± 0.038. So t|ket⟩ led on the two 53-qubit graphs but Quilc was ahead on Aspen, which the paper flags itself, ranking the compilers "t|ket⟩, followed by Quilc (with special note of their performance for the Aspen device), with Qiskit consistently introducing a very high gate overhead". On the UCCSD set the chemistry pass changes the picture (Fig. 20, two-qubit gate count): ChemPass 0.647 ± 0.025 on FullConnectivity against FullPass 0.765 ± 0.014, Quilc 0.801 ± 0.013 and Qiskit 0.783 ± 0.016, and in depth (Fig. 21) ChemPass reached 0.615 ± 0.029 on FullConnectivity and 0.949 ± 0.049 on Sycamore, i.e. still below the input depth after routing onto a restricted graph. The paper is equally explicit about the cost of using it in the wrong place: on circuits that do not resemble the UCCSD set, adding PauliSimp "can cause a drastic drop in performance". Comparing against the FullConnectivity column, the paper attributes the spread between compilers to routing: "these differences are dominated by differences in routing performance".

• Noise-aware graph placement, benchmarked on the ibmq_16_melbourne device

  • t|ket⟩: A Retargetable Compiler for NISQ Devices

    Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, Ross Duncan · 2020

  About

  The same paper's second experiment, and the only part of it that ran on quantum hardware. The question is whether the placement stage of the pipeline should read the device's reported error rates at all. t|ket⟩ offers graph placement (GP), which chooses an initial map by subgraph monomorphism into the device graph. The paper does not claim GP minimises the SWAPs routing will add: because routing adds gates dynamically, "it is in general not possible to predict which placements will correspond to the fewest gates added", so what GP actually applies is a heuristic - "placements are found such that a maximum number of two-qubit operations at the beginning of the circuit can be completed with no SWAP gates added". Noise-aware graph placement (NAGP) then scores the many candidate monomorphisms by expected overall fidelity using per-qubit and per-gate error information from the device. Since "the effectiveness of these methods depends strongly on the error characteristics of physical devices", the authors settle it by running circuits on a real machine with and without each method.

  Methods

  Each benchmark circuit was compiled three ways, differing only in how the initial partial placement was computed: "None" (no qubits placed, so routing places them on the fly), "Graph Placement", and "Noise-Aware Graph Placement". Routing and post-routing optimisation were identical across the three, and compilation included translating to the IBM Q gate set of U1, U2, U3 and CX. All three compilations of a given input circuit were submitted consecutively inside the same job (the API caps a job at 75 circuits) so that drift in the device's characteristics between jobs could not be mistaken for a difference between methods. Each compiled circuit was run at the maximum 8192 shots. The figure of merit is distance from the ideal distribution: the authors reject the Kullback-Leibler divergence because it is asymmetric and is infinite when the measured distribution's support is not contained in the ideal one, and a zero-padding fix would leave the value dependent on a tuning parameter, so they use the Jensen-Shannon divergence, $D_{JS}(P,Q) = (1/2) D_{KL}(P,M) + (1/2) D_{KL}(Q,M)$ with $M = (P+Q)/2$, which is symmetric and bounded in $[0,1]$ in base 2. The ideal distribution comes from exact simulation of every circuit, a methodology the paper notes "requires classical resources that scale exponentially with qubit number" and accepts on the grounds that the techniques are only relevant while devices stay small and heterogeneous.

  Data

  Random circuits, not algorithms, because "at the time of writing, it is difficult to implement many common algorithms on publicly-available quantum devices and extract a signal from the noise". Each circuit is built by sampling gates uniformly from X, Y, Z, H, T, S and CX, sampling uniformly over qubits for one-qubit gates and over pairs for CX, with any sample containing no CX discarded. Sets were generated at 4 and 8 qubits and at 20, 40, 60 and 80 gates; the 4-qubit 80-gate set was dropped as "too deep and therefore noisy for effective comparison of methods", leaving "a total of 7 sets each with 90 samples" - the 4-qubit panel of Figure 22 is ticked 20, 40, 60 and the 8-qubit panel 20, 40, 60, 80, which is what fixes which set went.

  Code

  The placement and routing passes are those of t|ket⟩ itself, distributed as pytket. The paper points to https://github.com/CQCL/tket_benchmarking - now https://github.com/Quantinuum/tket_benchmarking - for "the full datasets and scripts used for generating these results".

  Results

  All circuits were run on "the publicly-available ibmq_16_melbourne device via the IBM Q Experience", an IBM superconducting machine, with the ideal reference distributions from exact simulation; the paper states no qubit count for the device. Figure 22 plots the mean Jensen-Shannon divergence over the 90 samples of each set, for the three placement methods. "In general", the paper's own qualifier, graph placement lowers the mean against no initial placement, which it attributes to "reducing the number of error-prone two-qubit gates that need to be added", and noise-aware scoring of those same placements "is able to make further significant reductions", which the authors read as evidence that exploiting device heterogeneity is worth pursuing. Two expected trends hold: the 8-qubit means sit above the 4-qubit means, and in the 8-qubit case the divergence rises monotonically with gate count. One does not, and the paper says so rather than smoothing it over: "the peak for DJS mean at 40 gates for 4 qubits, for all placement methods, is unexpected and warrants further investigation". No table of values accompanies the figure, and its y-axis is ticked 0.10 to 0.25 in the 4-qubit panel and 0.35 to 0.60 in the 8-qubit panel, so no individual mean is quotable from it.