Efficient synthesis of probabilistic quantum circuits with fallback

Abstract

Recently it has been shown that Repeat-Until-Success (RUS) circuits can approximate a given single-qubit unitary with an expected number of $T$ gates of about $1/3$ of what is required by optimal, deterministic, ancilla-free decompositions over the Clifford+$T$ gate set. In this work, we introduce a more general and conceptually simpler circuit decomposition method that allows for synthesis into protocols that probabilistically implement quantum circuits over several universal gate sets including, but not restricted to, the Clifford+$T$ gate set. The protocol, which we call Probabilistic Quantum Circuits with Fallback (PQF), implements a walk on a discrete Markov chain in which the target unitary is an absorbing state and in which transitions are induced by multi-qubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols terminate after a finite number of steps. Specifically, we apply our method to the Clifford+$T$, Clifford+$V$, and Clifford+$\pi /12$ gate sets to achieve decompositions with expected gate counts of ${\log }_b(1/\epsilon )+O(\log (\log (1/\epsilon )))$, where $b$ is a quantity related to the expansion property of the underlying universal gate set.

17 pages, 7 figures; added Appendix F on the runtime performance of the synthesis algorithm

References in corpus (15)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Magic state distillation with low overhead
• Exact synthesis of multiqubit Clifford+T circuits
• Efficient synthesis of universal Repeat-Until-Success circuits
• Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• Reducing the quantum computing overhead with complex gate distillation
• Optimal ancilla-free Clifford+T approximation of z-rotations
• Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Synthesis of unitaries with Clifford+T circuits
• Efficient Clifford+T approximation of single-qubit operators
• A minimum control ancilla driven quantum computation scheme with repeat-until-success style gate generation

Cited by in corpus (34)

• Majorana Zero Modes and Topological Quantum Computation
• Elucidating Reaction Mechanisms on Quantum Computers
• Roads towards fault-tolerant universal quantum computation
• Automated Search for new Quantum Experiments
• Q#: Enabling scalable quantum computing and development with a high-level domain-specific language
• A Software Methodology for Compiling Quantum Programs
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• The Complexity Geometry of a Single Qubit
• A randomized quantum algorithm for statistical phase estimation
• Computer-inspired Quantum Experiments
• Early fault-tolerant simulations of the Hubbard model
• Anticoncentration theorems for schemes showing a quantum speedup
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
• An efficient magic state approach to small angle rotations
• Universal Gates via Fusion and Measurement Operations on SU$(2{)}_4$ Anyons
• Shorter quantum circuits via single-qubit gate approximation
• Fibonacci anyons versus Majorana fermions
• Lattice Surgery Translation for Quantum Computation
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Optimal Ancilla-free Pauli+V Circuits for Axial Rotations
• A framework for exact synthesis
• Reinforcement Learning Generation of 4-Qubits Entangled States
• Cost-optimal single-qubit gate synthesis in the Clifford hierarchy
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Sparse Probabilistic Synthesis of Quantum Operations
• Lower T-count with faster algorithms
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Quantum advantage in temporally flat measurement-based quantum computation
• Phase estimation with partially randomized time evolution
• Sampling and the complexity of nature
• High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
• Contributions to the Theory of Clifford-Cyclotomic Circuits