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

Repeat-until-success

PaetznickAdam, M SvoreKrysta

Published Nov 1, 2014• 7 citations
Publisher

Abstract

We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance e and requires significantly fewer non-Clifford gates t...
DOI
10.5555/2685179.2685181

Related papers

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

Direct implementation of an N-qubit controlled-unitary gate in a single step

Preethika Kumar

Quantum Information Processing•Aug 13, 2012•15 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 $\epsilon$ 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 $\epsilon$, where the number of $T$ gates scales as $1.26\log_2(1/\epsilon) - 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/\epsilon) - 3.28$ can be achieved for arbitrary unitaries and a small range of $\epsilon$, which is roughly twice as good as optimal deterministic decomposition methods.

Quantum Information and Computation•Nov 1, 2014•85 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

Asymptotically optimal approximation of the single qubit unitaries by Clifford+T circuits using at most three ancillary qubits

Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca

•Dec 4, 2012•0 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
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.
We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance ϵ\epsilonϵ 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 ϵ\epsilonϵ, where the number of TTT gates scales as 1.26log⁡2(1/ϵ)−3.531.26\log_2(1/\epsilon) - 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/\epsilon) - 3.282.4log2​(1/ϵ)−3.28 can be achieved for arbitrary unitaries and a small range of ϵ\epsilonϵ, which is roughly twice as good as optimal deterministic decomposition methods.
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.
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.