Parallelizing quantum circuit synthesis

Abstract

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.

16 pages, 9 figures

References in corpus (5)

• Surface codes: Towards practical large-scale quantum computation
• Exact synthesis of multiqubit Clifford+T circuits
• Efficient synthesis of universal Repeat-Until-Success circuits
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets

Cited by in corpus (11)

• Reducing T-count with the ZX-calculus
• There and back again: A circuit extraction tale
• Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers
• A polynomial time and space heuristic algorithm for T-count
• Constructions for Quantum Indistinguishability Obfuscation
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Quantum circuit synthesis using Householder transformations
• Optimizing Quantum Programs against Decoherence: Delaying Qubits into Quantum Superposition
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• Exploring ab initio machine synthesis of quantum circuits
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine