Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1406.2040 · Quantum Information and Computation

Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits

Nathan Wiebe, Martin Roetteler

Published Jan 1, 2016• 51 citations
arXivHTMLPDF

Abstract

We develop a method for approximate synthesis of single-qubit rotations of the form e−if(φ1,...,φk)X that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions f can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as 3 ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.

DOI
10.26421/qic16.1-2-9

Related papers

Quantum arithmetic and numerical analysis using repeat-until-success circuits

WiebeNathan, RoettelerMartin

We develop a method for approximate synthesis of single-qubit rotations of the form e-if(ϕ1,...,ϕk)X that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demo...

Quantum Information and Computation•Jan 1, 2016•4 citations

Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits

Alex Bocharov, Martin Roetteler, Krysta M. Svore

Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision ϵ over the Clifford+T basis. Surprisingly, the T count of the synthesized RUS circuit surpasses the theoretical lower bound of 3 log_{2}(1/ϵ) that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected T count of 1.15 log_{2}(1/ϵ) for single-qubit z rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.

arXiv:1404.5320•Physical Review Letters•Feb 27, 2015•142 citations

Efficient synthesis of probabilistic quantum circuits with fallback

Alex Bocharov, Martin Roetteler, Krysta M. Svore

Repeat-until-success (RUS) circuits can approximate a given single-qubit unitary with an expected number of $T$ gates of about $\frac{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 multiqubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols are guaranteed to terminate after a finite number of steps. Specifically, we apply our method to the Clifford + $T$, Clifford + $V$, and Clifford + $\ensuremath{\pi}/12$ gate sets to achieve decompositions with expected gate counts of ${log}_{b}(1/\ensuremath{\varepsilon})+O{ln[ln(1/\ensuremath{\varepsilon})]}$, where $b$ is a quantity related to the expansion property of the underlying universal gate set.

arXiv:1409.3552•Physical Review A•May 18, 2015•59 citations

Direct U(2) approximation via repeat-until-success circuits

Vadym Kliuchnikov, Jendrik Brachter, Marcus P. da Silva

We show how to directly and efficiently approximate arbitrary one-qubit unitaries, bypassing the Euler decomposition and the magnitude approximation problem, at the cost of one ancillary qubit. Our technique also applies to approximating unitaries with multi-qubit gate sets such as Clifford and CS, or Clifford and CCZ, as well as to approximating orthogonal matrices using multi-qubit gate sets such as Real Clifford and CCZ. The key tools are repeat-until-success circuits, lattice-based exact synthesis algorithms, integer point enumeration in convex sets, and relative norm equations.

quant-pharXiv:2604.20033•Apr 23, 2026•0 citations

Floating point representations in quantum circuit synthesis

Nathan Wiebe, Vadym Kliuchnikov

We provide a non-deterministic quantum protocol that approximates the single qubit rotations R x (2 ϕ 2 1 ϕ 2 2 ) using R x (2 ϕ 1 ) and R x (2 ϕ 2 ) and a constant number of Clifford and T operations. We then use this method to construct a 'floating point' implementation of a small rotation wherein we use the aforementioned method to construct the exponent part of the rotation and also to combine it with a mantissa. This causes the cost of the synthesis to depend more strongly on the relative (rather than absolute) precision required. We analyze the mean and variance of the T -count required to use our techniques and provide new lower bounds for the T -count for ancilla free synthesis of small single-qubit axial rotations. We further show that our techniques can use ancillas to beat these lower bounds with high probability. We also discuss the T -depth of our method and see that the vast majority of the cost of the resultant circuits can be shifted to parallel computation paths.

arXiv:1305.5528•New Journal of Physics•Sep 27, 2013•51 citations

A Holistic Approach to Rotation Synthesis for Fault- Tolerant Quantum Computation

Tian-Fu Chen, Cheng-Han Michael Liu, Jie-Hong Roland Jiang

Rotation operations are essential ingredients in quantum algorithms. However, fault-tolerant quantum computation is intrinsically digital, based on a finite set of primitive gates, and thus cannot provide an analog rotation operation with arbitrary angles. It must resort to approximating a rotation operation using a basic universal gate set. Prior work on rotation synthesis either focuses on synthesizing individual rotations without considering a quantum circuit as a whole or is restricted to the specific quantum Fourier transform circuit. In this work, we develop a holistic and general approach to rotation synthesis, taking all rotation operations of a circuit into account for quantum cost minimization. Experimental results demonstrate the superiority of our method compared to the state-of-the-art methods in reducing the cost of synthesized Quantum algorithms with rotation operations.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations
We develop a method for approximate synthesis of single-qubit rotations of the form e−if(φ1,...,φk)X that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions f can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as 3 ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.
Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision ϵ over the Clifford+T basis. Surprisingly, the T count of the synthesized RUS circuit surpasses the theoretical lower bound of 3 log_{2}(1/ϵ) that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected T count of 1.15 log_{2}(1/ϵ) for single-qubit z rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.
Repeat-until-success (RUS) circuits can approximate a given single-qubit unitary with an expected number of TTT gates of about 13\frac{1}{3}31​ of what is required by optimal, deterministic, ancilla-free decompositions over the Clifford + TTT 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 + TTT 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 multiqubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols are guaranteed to terminate after a finite number of steps. Specifically, we apply our method to the Clifford + TTT, Clifford + VVV, and Clifford + $\ensuremath{\pi}/12$ gate sets to achieve decompositions with expected gate counts of ${log}_{b}(1/\ensuremath{\varepsilon})+O{ln[ln(1/\ensuremath{\varepsilon})]}$, where bbb is a quantity related to the expansion property of the underlying universal gate set.
We show how to directly and efficiently approximate arbitrary one-qubit unitaries, bypassing the Euler decomposition and the magnitude approximation problem, at the cost of one ancillary qubit. Our technique also applies to approximating unitaries with multi-qubit gate sets such as Clifford and CS, or Clifford and CCZ, as well as to approximating orthogonal matrices using multi-qubit gate sets such as Real Clifford and CCZ. The key tools are repeat-until-success circuits, lattice-based exact synthesis algorithms, integer point enumeration in convex sets, and relative norm equations.
We provide a non-deterministic quantum protocol that approximates the single qubit rotations R x (2 ϕ 2 1 ϕ 2 2 ) using R x (2 ϕ 1 ) and R x (2 ϕ 2 ) and a constant number of Clifford and T operations. We then use this method to construct a 'floating point' implementation of a small rotation wherein we use the aforementioned method to construct the exponent part of the rotation and also to combine it with a mantissa. This causes the cost of the synthesis to depend more strongly on the relative (rather than absolute) precision required. We analyze the mean and variance of the T -count required to use our techniques and provide new lower bounds for the T -count for ancilla free synthesis of small single-qubit axial rotations. We further show that our techniques can use ancillas to beat these lower bounds with high probability. We also discuss the T -depth of our method and see that the vast majority of the cost of the resultant circuits can be shifted to parallel computation paths.
Rotation operations are essential ingredients in quantum algorithms. However, fault-tolerant quantum computation is intrinsically digital, based on a finite set of primitive gates, and thus cannot provide an analog rotation operation with arbitrary angles. It must resort to approximating a rotation operation using a basic universal gate set. Prior work on rotation synthesis either focuses on synthesizing individual rotations without considering a quantum circuit as a whole or is restricted to the specific quantum Fourier transform circuit. In this work, we develop a holistic and general approach to rotation synthesis, taking all rotation operations of a circuit into account for quantum cost minimization. Experimental results demonstrate the superiority of our method compared to the state-of-the-art methods in reducing the cost of synthesized Quantum algorithms with rotation operations.