PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallelizing quantum circuit synthesis

Olivia Di Matteo, Michele Mosca

arXiv:1606.07413v2quant-ph

TL;DR

Exact multi-qubit circuit synthesis becomes intractable as qubit count and circuit depth grow. This paper applies deterministic walks to parallel circuit synthesis, reporting faster synthesis of known circuits and confirming optimal T-count 7 for a 4-qubit 1-bit full adder.

  • Problem

    Exact synthesis often scales exponentially with qubit count and circuit depth, making circuits beyond a handful of qubits and layers intractable.

    Source: §1 · p. 2

  • Method

    The paper maps circuit synthesis to deterministic walks and implements parallel claw finding for circuit search.

    Source: §1 · p. 2, §3 · p. 4

  • Results

    At roughly 25s, synthesis times for 3-qubit circuits with T-count 7 improved on the greater-than-4-minute times reported in, and the 4-qubit 1-bit full adder was confirmed to have T-count 7.

    Source: §5.2 · p. 12, §5.3 · p. 12

  • Takeaways & Limitations

    The authors report a clear advantage over existing techniques with a relatively modest number of processors and directly synthesized a 4-qubit circuit they describe as previously intractable.

    Source: §6 · p. 13

    Runtime remains exponential in qubit count and circuit depth, and further work is needed to characterize scaling and extend synthesis to general gate sets and approximate synthesis.

    Source: §3 · p. 7, §6 · p. 13

Abstract

from arXiv · show

Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools which can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal $T$-count synthesis over the Clifford+$T$ gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal $T$-count 7 and $T$-depth 3.

1. Introduction

Circuit synthesis translates quantum circuits into executable gate sequences, but exact multi-qubit synthesis becomes intractable as circuit size and depth grow. This paper proposes deterministic walks as a framework for searching possible circuits and develops a parallel implementation.

1. Introduction

  • Circuit synthesis is an integral part of quantum compilation, which translates human-readable programs into operations executable on quantum hardware.Source: §1 · pp. 1–2
  • Exact synthesis time and space often grow exponentially with qubit count and circuit depth, making circuits beyond a handful of qubits and layers intractable.Source: §1 · p. 2
  • Deterministic walks provide a framework for traversing circuits of a given depth and searching for solutions to synthesis problems.The method maps unitary operators to fixed-length binary strings and back, enabling walks over circuits for universal gate sets and any number of qubits.Source: §1 · p. 2
  • The paper implements parallel optimal T-count synthesis and reports speedups, including confirmation that a 4-qubit 1-bit full adder has optimal T-count 7 and T-depth 3.Source: §1 · p. 2

2. Walking through circuits

Deterministic walks use a hash and reduction function to generate repeatable paths through a search space. The paper maps circuit products to these walks so they can be searched for a synthesis solution.

2. Walking through circuits

  • A hash followed by a reduction function generates a trail through the domain; once its starting point is chosen, the trail is completely determined.Source: §2 · pp. 2–3
  • Deterministic walks have also been used for pre-image search, collision finding, and claw finding, including parallel collision search in double DES.Source: §2 · p. 3
  • Deterministic walks can reduce storage needs to each trail’s starting point, ending point, and number of intermediate steps.Conventional search techniques store every computed point.Source: §2 · p. 3
  • The paper encodes each gate in a unitary as a unique binary string, then concatenates those encodings to represent a circuit product.The encoding can include gate identity, Hermitian conjugation, qubit locations, controls, and targets.Source: §2 · pp. 3–4
  • Mappings from binary strings to unitary matrices and back, combined with a hash function, let repeated applications traverse possible circuit products pseudorandomly.Figure 1 depicts this repeated mapping-and-hashing process.Source: Figure 1 · p. 3, §2 · p. 4

3. Parallel circuit synthesis

The paper adapts meet-in-the-middle synthesis into a parallel search using deterministic walks and claw finding. Its runtime remains exponential in circuit size and depth, but benefits inversely from processor count and available memory.

3. Parallel circuit synthesis

  • Circuit synthesis is reformulated as claw finding between two functions whose inputs encode the two sides of the decomposition.The algorithm treats each application of the combined function as one step in a deterministic walk.Source: §3 · pp. 4–5
  • The approach adapts meet-in-the-middle synthesis, which divides the decomposition in half and reduces the brute-force search space by roughly a square-root factor.Brute-force runtime is described as O(ξ^k), while the meet-in-the-middle method searches databases of unitaries from each side.Source: §3 · p. 4
  • Parallel search retains exponential dependence on qubit count and half the circuit depth, but runtime scales inversely with processor count.Source: §3 · pp. 4–5
  • Processors start random trails and stop at distinguished points, recording each trail’s start, endpoint, and length in shared memory.A repeated endpoint with a different starting point signals trails that have merged.Source: §3 · pp. 5–6
  • Only a merge immediately preceded by different functions, z1 and z2, yields a synthesis solution; same-function merges do not.Figure 2 illustrates the possible trail-merger cases.Source: §3 · p. 6, Figure 2 · p. 6
  • Runtime remains exponential in qubit count and circuit depth, while benefiting inversely from processor count and available memory.The estimate depends on the number of stored distinguished points and the time per iteration, which is largely spent on matrix multiplication.Source: §3 · pp. 6–7

4. Implementation details

The implementation applies parallel search to optimal T-count synthesis, using Pauli representations and sparse channel-matrix operations. The software was tested on both a multi-core node and a large supercomputer.

4.1. Optimal T-count synthesis

  • The optimal T-count formulation represents a circuit using a sequence of Paulis and a Clifford, with each Pauli contributing one T gate.The algorithm is relevant because T gates are costly in fault-tolerant computation due to magic-state distillation.Source: §4.1 · pp. 7–8
  • Binary symplectic Pauli encodings provide a simple mapping for deterministic walks, while sparse channel representations enable fast matrix multiplication.The channel representation has dimension 4^n × 4^n.Source: §4.1 · pp. 7–8

4.2. Computer specifications

  • pQCS implements parallel optimal T-count synthesis in C++11 with Boost.MPI; an OpenMP-only version is also available for multi-core computers.Source: §4.2 · p. 8
  • Testing used up to 16 processors on a SHARCNET Orca node and a Blue Gene/Q supercomputer with 65,536 processors; the largest test involved 8,192 cores.Reported results are from the Blue Gene/Q.Source: §4.2 · p. 8

5. Results

The results tune pQCS’s worker, collector, and verifier allocation and show faster synthesis for known circuits. The method also directly confirms optimal resources for the 4-qubit 1-bit full adder.

5.1. Determining effective simulation parameters

  • pQCS assigns deterministic walks to workers, stores distinguished points in-core on collectors, and uses verifiers to check possible claws.Collector storage depends on collector count, while the number of parallel walks is expected to depend on worker count when enough collectors and verifiers are available.Source: §5.1 · pp. 8–10, Figure 3 · p. 9
  • The best tested allocation used collectors equal to 1/8 and verifiers equal to 1/4 of total processors.More than 3/8 of processes devoted to storage and verification leaves too few workers; too many workers increase the distinguished points each collector must process.Source: §5.1 · p. 10, Figure 4 · p. 10
  • Runtime followed the expected inverse dependence on processor count, but at 8192 cores overhead and communication were suspected to outweigh the benefits.Figure 5 shows the core-count variation; the authors attribute the deviation from the expected trend to likely overhead and communication costs for this problem size.Source: §5.1 · p. 10, Figure 5 · p. 11
  • With 4096 processors and 512 collectors plus 1024 verifiers, average Toffoli synthesis time was roughly 26s and runtime varied inversely with distinguished-point fraction.The Toffoli parameter sweep used distinguished-point fractions from 1/2 to 1/32; the available memory exceeded what was needed to store the entire search space.Source: §5.1 · p. 11, Figure 6 · p. 11

5.2. Benchmarking known circuits

  • At roughly 25s, synthesis of the known 3-qubit circuits was markedly faster than the greater-than-4-minute times reported in.The benchmark set contains five circuits with optimal T-count 7.Source: §5.2 · p. 12, Table 1 · p. 12, Figure 7 · p. 12

5.3. Pushing the boundaries

  • The 4-qubit 1-bit full adder has optimal T-count 7 and T-depth 3, confirming a previously suspected T-count of 7.An earlier synthesis reported T-count 8; the new synthesis took 12.5 hours on 4096 cores, and the adder is affine equivalent to the Toffoli.Source: §5.3 · pp. 12–13, Figure 8 · p. 13

6. Concluding remarks

The conclusion presents deterministic-walk synthesis and its parallel implementation as advantageous with a modest number of processors. It identifies extensions and scaling characterization as future work.

6. Concluding remarks

  • The framework and parallel software showed a clear advantage over existing techniques with a relatively modest number of processors, and directly synthesized a 4-qubit circuit.The authors state that this circuit would have been intractable using previous methods.Source: §6 · p. 13
  • Future work includes improving application structure and parallelization, extending synthesis over specified gate sets, and implementing approximate synthesis.The authors also seek to push pQCS further to characterize its scaling as circuit search spaces grow.Source: §6 · p. 13
  • The conclusion leaves pQCS’s scaling with available memory in larger circuit search spaces to be characterized.The stated focus is the regime where circuit search spaces become sufficiently large.Source: §6 · pp. 13–14

Appendix

The appendix discusses the collision-finding runtime analysis used for pQCS and extends it to unequal meet-in-the-middle search spaces. Under its stated assumptions, the resulting runtime is exponential in qubit count and T-count and inversely proportional to processor count and distinguished-point fraction.

Appendix

  • The runtime analysis starts from finding a collision in a space of size N when memory holds w distinguished points.The analysis calls the runtime estimate ‘flawed’ and attributes its origin to.Source: Appendix · p. 15
  • The collision estimate accounts for traversing about w/θ elements to fill memory and tracing back two trails averaging 1/θ in length.The first contribution uses a 1/N chance that a new trail point lands on a previously seen point; the second is the traceback cost.Source: Appendix · p. 15
  • For the generalized T-count search, the model allows unequal MITM halves and sequentially searches the larger half when the depth is odd.With w >> N2, the expression is exponential in both n and t and inversely proportional to m and θ, matching the reported practice.Source: Appendix · p. 16
Loading 1606.07413v2…