Efficient synthesis of universal Repeat-Until-Success circuits

Abstract

Recently, it was shown that Repeat-Until-Success (RUS) circuits can achieve a $2.5$ times reduction in expected $T$-count over ancilla-free techniques for single-qubit unitary decomposition. However, the previously best known algorithm to synthesize RUS circuits requires exponential classical runtime. In this paper we present an algorithm to synthesize an RUS circuit to approximate any given single-qubit unitary within precision $\epsilon$ in probabilistically polynomial classical runtime. Our synthesis approach uses the Clifford+$T$ basis, plus one ancilla qubit and measurement. We provide numerical evidence that our RUS circuits have an expected $T$-count on average $2.5$ times lower than the theoretical lower bound of $3{\log }_2(1/\epsilon )$ for ancilla-free single-qubit circuit decomposition.

15 pages, 10 figures; reformatted and minor edits; added Fig. 2 to visualize the density of z-rotations implementable via RUS protocols

References in corpus (13)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Magic state distillation with low overhead
• Novel constructions for the fault-tolerant Toffoli gate
• Exact synthesis of multiqubit Clifford+T circuits
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Ancilla-Driven Universal Quantum Computation
• A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• Floating Point Representations in Quantum Circuit Synthesis
• Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators
• Synthesis of unitaries with Clifford+T circuits
• Efficient Clifford+T approximation of single-qubit operators
• Ancilla Driven Quantum Computation with arbitrary entangling strength

Cited by in corpus (88)

• Majorana Zero Modes and Topological Quantum Computation
• Elucidating Reaction Mechanisms on Quantum Computers
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Toward the first quantum simulation with quantum speedup
• Automated Search for new Quantum Experiments
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Low rank representations for quantum simulation of electronic structure
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Quantifying the magic of quantum channels
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• A Threshold for Quantum Advantage in Derivative Pricing
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• A randomized quantum algorithm for statistical phase estimation
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Global optimization of quantum dynamics with AlphaZero deep exploration
• Early fault-tolerant simulations of the Hubbard model
• Applying quantum algorithms to constraint satisfaction problems
• Efficient synthesis of probabilistic quantum circuits with fallback
• Shorter gate sequences for quantum computing by mixing unitaries
• Primitive Quantum Gates for an SU(2) Discrete Subgroup: BT
• A logical qubit in a linear array of semiconductor quantum dots
• Unifying gate-synthesis and magic state distillation
• Classically emulated digital quantum simulation for screening and confinement in the Schwinger model with a topological term
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Use of global interactions in efficient quantum circuit constructions
• Nonlinear Quantum Neuron: A Fundamental Building Block for Quantum Neural Networks
• T-count optimization and Reed-Muller codes
• Reducing the quantum computing overhead with complex gate distillation
• Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
• Constrained Optimization via Quantum Zeno Dynamics
• An efficient magic state approach to small angle rotations
• The Efficient Preparation of Normal Distributions in Quantum Registers
• Approximate Quantum Circuit Synthesis using Block-Encodings
• Energetic cost of superadiabatic quantum computation
• Shorter quantum circuits via single-qubit gate approximation
• On the complexity of implementing Trotter steps
• A polynomial time and space heuristic algorithm for T-count
• Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry
• Exact gate decompositions for photonic quantum computing
• Optimal quantum operations at zero energy cost
• Simulating Effective QED on Quantum Computers
• Parallelizing quantum circuit synthesis
• Repeat-Until-Success circuits with fixed-point oblivious amplitude amplification
• Exact and approximate continuous-variable gate decompositions
• Primitive Quantum Gates for an SU(3) Discrete Subgroup: $\Sigma (36\times 3)$
• Introducing Non-Linear Activations into Quantum Generative Models
• Realization of a quantum neural network using repeat-until-success circuits in a superconducting quantum processor
• Continuous quantum gate sets and pulse class meta-optimization
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Option pricing under stochastic volatility on a quantum computer
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• A framework for exact synthesis
• Variational secure cloud quantum computing
• Ancilla-driven quantum computation for qudits and continuous variables
• Solving reaction dynamics with quantum computing algorithms
• Reinforcement Learning Generation of 4-Qubits Entangled States
• Multi-objective evolutionary algorithms for quantum circuit discovery
• Simulating Vibrational Dynamics on Bosonic Quantum Devices
• Advantages of a modular high-level quantum programming framework
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Compressing Hamiltonians with ab initio downfolding for simulating strongly-correlated materials on quantum computers
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Probabilistic unitary synthesis with optimal accuracy
• Trotter simulation of vibrational Hamiltonians on a quantum computer
• Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
• An Amplitude-Based Implementation of the Unit Step Function on a Quantum Computer
• Feasibility of Logical Bell State Generation in Memory Assisted Quantum Networks
• Quantum advantage in temporally flat measurement-based quantum computation
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Resource comparison of two surface code implementations of small angle Z rotations
• Quantum state preparation via piecewise QSVT
• Fault-tolerant quantum simulation of generalized Hubbard models
• Error Crafting in Mixed Quantum Gate Synthesis
• A Jordan-Wigner gadget that reduces T count by more than 6x for quantum chemistry applications
• Catalytic $z$-rotations in constant $T$-depth
• High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
• Saving resources through repeat-until-success positive-operator-valued-measure measurements in quantum computation
• Model Checking for Verification of Quantum Circuits
• Synthesis of Single Qutrit Circuits from Clifford+R
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms