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

Quantum Information and Computation

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

WiebeNathan, RoettelerMartin

Published Jan 1, 2016• 4 citations
Publisher

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 demo...
DOI
10.5555/3179320.3179329

Related papers

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

Nathan Wiebe, Martin Roetteler

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.

arXiv:1406.2040•Quantum Information and Computation•Jan 1, 2016•51 citations

Optimal quantum circuit synthesis from controlled-unitary gates (6 pages)

Jiří Vala, Jiang Zhang, Shankar Sastry +1 more

Physical Review A•Jan 1, 2004•1 citation

Efficient Synthesis of Optimal 3-qubit Reversible Circuits Using Bit Operation

Zhiqiang Li, Hanwu Chen, Xiaoyu Song B

International Journal of Digital Content Technology and its Applications•Jun 30, 2012•1 citation

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

Matrix-Based Algorithm for 4-Qubit Reversible Logic Circuits Synthesis

Dong Wang, Shengyao Sun, Hanwu Chen

Energy Procedia•Jan 1, 2011•4 citations

Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries

Adam Paetznick, Krysta M. Svore

We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance $ε$ and requires significantly fewer non-Clifford gates than existing techniques. We develop "Repeat-Until-Success" (RUS) circuits and characterize unitaries that can be exactly represented as an RUS circuit. Our RUS circuits operate by conditioning on a given measurement outcome and using only a small number of non-Clifford gates and ancilla qubits. We construct an algorithm based on RUS circuits that approximates an arbitrary single-qubit $Z$-axis rotation to within distance $ε$, where the number of $T$ gates scales as $1.26\log_2(1/ε) - 3.53$, an improvement of roughly three-fold over state-of-the-art techniques. We then extend our algorithm and show that a scaling of $2.4\log_2(1/ε) - 3.28$ can be achieved for arbitrary unitaries and a small range of $ε$, which is roughly twice as good as optimal deterministic decomposition methods.

arXiv:1311.1074•Nov 5, 2013•20 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.
We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance εεε and requires significantly fewer non-Clifford gates than existing techniques. We develop "Repeat-Until-Success" (RUS) circuits and characterize unitaries that can be exactly represented as an RUS circuit. Our RUS circuits operate by conditioning on a given measurement outcome and using only a small number of non-Clifford gates and ancilla qubits. We construct an algorithm based on RUS circuits that approximates an arbitrary single-qubit ZZZ-axis rotation to within distance εεε, where the number of TTT gates scales as 1.26log⁡2(1/ε)−3.531.26\log_2(1/ε) - 3.531.26log2​(1/ε)−3.53, an improvement of roughly three-fold over state-of-the-art techniques. We then extend our algorithm and show that a scaling of 2.4log⁡2(1/ε)−3.282.4\log_2(1/ε) - 3.282.4log2​(1/ε)−3.28 can be achieved for arbitrary unitaries and a small range of εεε, which is roughly twice as good as optimal deterministic decomposition methods.