PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Circuit Placement

D. Maslov, S. M. Falconer, M. Mosca

arXiv:quant-ph/0703256v2quant-ph

TL;DR

Physical quantum hardware can make some direct qubit interactions difficult or costly, so abstract circuits need placement adapted to the hardware. The paper formalizes placement and develops a heuristic that combines subcircuit placement with mapping swaps. It reports results matching the best known experimental solutions and handling circuits with hundreds of qubits and thousands of gates in hours.

  • Problem

    Abstract circuit design assumes direct interaction between any qubits, although physical interactions may be difficult or costly, creating a need to map logical qubits efficiently to physical qubits.

    Source: §1 · pp. 1–2

  • Method

    The paper formulates placement and uses a heuristic that places subcircuits along fast interactions, then inserts SWAP stages to connect their mappings.

    Source: §1 · p. 2, §5.1 · p. 7

  • Results

    The heuristic computed the best results reported by experimental physicists within a fraction of a second and handled circuits with hundreds of qubits and thousands of gates in hours.

    Source: §7 · p. 13

  • Takeaways & Limitations

    Considering subcircuits and swapping their mappings is essential to achieving the best placement results in the reported approach.

    Source: §7 · p. 13

    The method greedily makes the computational stage as large as possible; the authors identify balancing it against the following swapping stage as further research.

    Source: §7 · p. 13

Abstract

from arXiv · show

We study the problem of the practical realization of an abstract quantum circuit when executed on quantum hardware. By practical, we mean adapting the circuit to particulars of the physical environment which restricts/complicates the establishment of certain direct interactions between qubits. This is a quantum version of the classical circuit placement problem. We study the theoretical aspects of the problem and also present empirical results that match the best known solutions that have been developed by experimentalists. Finally, we discuss the efficiency of the approach and scalability of its implementation with regards to the future development of quantum hardware.

1 Introduction

Abstract quantum circuits must be adapted to hardware where some qubit interactions are difficult or costly, making efficient physical-qubit assignment important. The paper formalizes this placement problem, studies its complexity, and develops a heuristic approach evaluated on experimental data.

1 Introduction

  • Direct interactions between some physical qubits can be so weak that they are effectively noise, while indirect coupling can impose costly overhead.The introduction gives an interaction frequency below 0.2 Hz and decoherence around one second as an example.Source: §1 · p. 1
  • The chain nearest-neighbor model does not represent several technologies, including NMR, Josephson junctions, and optical technology.In the cited NMR examples, fastest interactions follow chemical bonds rather than forming a single chain.Source: §1 · p. 1
  • The paper considers pre-given architectures, unlike [25], which forms an architecture according to the circuit being implemented.The two research directions are described as complementary.Source: §1 · p. 2
  • Placement maps logical qubits to physical qubits to optimize interactions, and the place-all-at-once problem is NP-Complete.Exhaustive assignment search requires n! tries, motivating the paper's heuristic-based algorithm.Source: §1 · p. 2
  • The heuristic approach is tested on existing quantum-experiment data, using liquid-state NMR as a test bed without restricting the approach to that technology.The authors note that Ising-type Hamiltonians also describe certain superconductivity proposals.Source: §1 · p. 2

2 Preliminaries

The preliminaries introduce quantum states, gates, and measurement, then connect gate implementation to the timing costs that make physical-qubit assignment consequential. They illustrate these costs using liquid-state NMR gates and an NMR-optimized circuit.

2 Preliminaries

  • A quantum computation evolves a state vector through unitary transformations and obtains probabilistic classical information through measurement.For n qubits, the state vector has length 2^n.Source: §2 · pp. 2–3
  • NMR implements Rx and Ry with radio-frequency pulses, treats Rz as requiring no delay, and waits for ZZ drift interactions to complete.Unneeded ZZ interactions are eliminated through refocussing.Source: §2 · p. 3
  • The illustrated NMR implementation uses four pulses and one two-qubit gate, up to a global phase and output-qubit permutation.The circuit representation is specifically optimized for liquid-state NMR.Source: §2 · pp. 3–4
  • In liquid-state NMR, ZZ interactions can take about 10 times longer than a single-qubit gate, making interaction assignment important for efficient execution.The passage describes NMR as operating in a weak interaction mode.Source: §2 · p. 4

3 Formalization of the circuit mapping problem

The section formalizes circuit placement as assigning logical qubits to physical nuclei to minimize execution runtime. It defines gate costs from physical interaction weights and gate durations, then gives a runtime calculation and a small placement example.

3 Formalization of the circuit mapping problem

  • The input circuit uses one- and two-qubit gates arranged in levels, with gates that can run in parallel grouped at the same level.Levelization is used to reduce overall circuit runtime.Source: §3 · pp. 4–5
  • Logical qubits must be assigned to nuclei before exact gate delays can be determined, and current NMR tools perform timing optimization later in compilation.In the NMR example, Z rotations have zero delay, while the specified 90-degree Ry and ZZ gates each have duration 1.Source: §3 · pp. 4–5
  • Runtime is calculated by tracking each qubit’s completion time, updating it for single-qubit gates and synchronizing the two participating qubits for two-qubit gates.The circuit runtime is the maximum completion time across qubits; the calculation also supports sequential execution of logic levels.Source: §3 · p. 4
  • The physical environment is a weighted graph whose edge weights represent the time needed for fixed-angle one- or two-qubit gates.Weights are proportional to inverse coupling frequencies for two-qubit gates and inverse processing frequencies for single-qubit gates.Source: §3 · p. 4
  • Placement is an injective mapping from circuit qubits to physical nuclei that minimizes circuit runtime.The gate execution cost is the physical-environment weight multiplied by the gate’s duration.Source: §3 · p. 5
  • 136 is the minimum runtime for the three-qubit encoding circuit in acetyl chloride, achieved by mapping a → C2, b → C1, and c → M.The example mapping a → M, b → C2, c → C1 has runtime 770.Source: §3 · p. 6

4 Complexity

The section shows that quantum circuit placement is NP-complete by constructing a placement instance equivalent to a Hamiltonian-cycle problem. Thus, practical solutions must focus on heuristics.

4 Complexity

  • The placement problem is NP-complete, so practical solutions must focus on heuristics.The reduction encodes a Hamiltonian-cycle instance as a circuit and physical environment, with zero minimum runtime possible exactly when the graph has a Hamiltonian cycle.Source: §4 · p. 6

5 Heuristic solution

The heuristic partitions a circuit into subcircuits that fit the fastest interactions, then connects their placements with SWAP circuits. For well-separable interaction graphs, the recursive permutation method has linear complexity.

5.1 Algorithm

  • The placement loop extends each subcircuit while its two-qubit gates remain alignable to fastest interactions, fine-tunes candidate mappings, then connects placements with SWAP circuits.Fine tuning compares runtimes across monomorphisms when they can be found reasonably fast; otherwise it uses hill climbing.Source: §5.1 · pp. 6–7

5.2 Fast permutation circuits

  • The permutation method recursively bisects the connected interaction graph and routes values across the cut, assuming equal-time SWAPs and a well-separable graph.The cut edges serve as communication channels; bounded-degree graphs are stated to satisfy the separability condition.Source: §5.2 · pp. 7–8
  • For s ≥ 1/2, the permutation algorithm uses at most 8n+const logic levels and is asymptotically optimal on the chain nearest-neighbor architecture.The bound applies to circuits composed with SWAPs using the fastest interactions.Source: §5.2 · p. 8
  • In the trans-crotonic acid example, three rounds of swaps move the target values into the correct sides of the 4- and 3-vertex components.The graph cuts have s = 1/2.Source: §5.2 · p. 9, Figure 3 · p. 9

5.3 Implementation and its scalability

  • Graph monomorphism is the bottleneck, called at most 2s times; other operations are at most quadratic, and the authors project under an hour for circuits with a few hundred qubits and thousand gates.The projection uses reported graph-alignment runtimes as its basis.Source: §5.3 · pp. 9–10
  • The leaf-target override reduced swap-stage depth by 0–5%, while depth-2 look-ahead weighs a mapping with its swap and next-stage costs.The implementation also limits consideration to 100 monomorphisms.Source: §5.3 · p. 10

6 Experimental results

The experiments test recovery of experimentally chosen mappings, threshold-sensitive placement of useful circuits, and scalability on generated circuits. The tool matches hand-found solutions, and for a 6-qubit QFT on trans-crotonic acid, thresholded multi-subcircuit placement nearly halves runtime versus whole-circuit placement.

6 Experimental results

  • The circuit-depth calculation caps use of an existing interaction at three times per two-qubit unitary, lowering calculated costs by no more than 1% in tested examples.This adjustment is applied in the reported experiments.Source: §6 · p. 10
  • The tool reconstructs the best hand-found mappings for experimentally run circuits, choosing a single subcircuit and placing it optimally.The estimated runtime may differ slightly from actual runtime because of technology-specific second-order effects.Source: §6 · pp. 10–11
  • The extended tests cover small quantum algorithms and existing NMR molecules; for one molecule, Threshold values of 50 or 100 disallow all interactions.The resulting N/A indicates the computation cannot run under those settings.Source: §6 · p. 11
  • Table 3 reports each placement's runtime and chosen subcircuit count by Threshold, with a final-column baseline for placement without SWAPs.A row value below its final-column value indicates that the swapping strategy outperformed whole-circuit placement.Source: §6 · p. 11
  • .2237 sec is the best runtime for the 6-qubit QFT on trans-crotonic acid, versus .4137 sec for optimal whole-circuit placement.Threshold = 200 gives the best result; Threshold = 10000 uses one workspace, while Threshold = 50 causes excessive swapping.Source: §6 · p. 11, Table 3 · p. 12
  • The implementation processes circuits with hundreds of qubits and tens of thousands of gates in reasonable time, with tests spanning N = 8 to N = 1024.The generated circuits contain hidden permutation stages, each requiring a swapping stage to move between temporary architectures.Source: §6 · p. 12

7 Conclusions

The paper studies quantum circuit placement, proves a simplified version NP-complete, and presents a heuristic implementation. Tests report matches to experimentalists’ best-known solutions and practical runtimes for large circuits, while identifying further optimization directions.

7 Conclusions

  • Even the simplified place-all-at-once placement problem is NP-complete, motivating the paper’s focus on a heuristic solution.The paper studies assigning physical qubits to logical qubits in a given circuit.Source: §7 · p. 12
  • For 512 qubits, exhaustive assignment without SWAP gates has a projected 1167-digit runtime, while the heuristic finds a sensible solution in a few hours.The exhaustive search also cannot produce the meaningful solution described as breaking the circuit into 9 stages.Source: §7 · p. 12
  • Table 4 presents a performance test for circuit placement over chains.Source: Table 4 · p. 13
  • The implementation computed experimentalists’ best-reported results within a fraction of a second and handled circuits with hundreds of qubits and thousands of gates in hours.Considering subcircuits and swapping their mappings was essential to achieving the best placement results.Source: §7 · p. 13
  • Further work could balance computation depth against the following swapping-stage depth; the current method greedily makes the computational stage as large as possible.The paper also suggests using gate commutation or circuit identities to transform instances into potentially more favorable ones.Source: §7 · p. 13

Appendix

The appendix establishes a separability property for bounded-degree graphs and outlines a constructive argument that builds a connected part while preserving a connected complement.

Appendix

  • Every bounded-degree graph with maximal degree k is well separable with parameter s = 1/k.Source: Appendix · p. 13
  • The proof starts with a small connected subgraph whose complement is connected, then adds vertices until the subgraph reaches the stated size threshold while its complement stays connected.The threshold appears in the passages as n−1/k.Source: Appendix · p. 13
  • The proof cuts edges to form a tree while preserving edges incident to a selected vertex, then separates a suitable subtree to obtain connected components.The resulting components can be processed iteratively for well separability.Source: Appendix · pp. 13–14
  • When no sufficiently large component is available, the construction joins small components and continues adding vertices to build a larger connected component.The passages describe handling a case with one large component and several small ones, then iterating through vertices.Source: Appendix · p. 14

Related papers

Loading quant-ph/0703256v2…