The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“This sequence can be combined into a single shift, and implemented using e.g. the technique in [10], to a level of precision far below other sources of error in the algorithm without incurring a noticeable cost.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [10]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 20,450
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525
Magic-state distillation with low overhead
Bravyi, S. B., & Haah, J. (2012) · Physical Review A · doi:10.1103/physreva.86.052329 · Cited by 345
Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and T gates
Kliuchnikov, V., Maslov, D., & Mosca, M. (2012) · Quantum information & computation · doi:10.26421/qic13.7-8-4 · Cited by 255
Low-overhead constructions for the fault-tolerant Toffoli gate
Jones, C. (2013) · Physical Review A · doi:10.1103/physreva.87.022328 · Cited by 200
Danos, V., Kashefi, E., & Panangaden, P. (2007) · Journal of the ACM · doi:10.1145/1219092.1219096 · Cited by 195
Optimal ancilla-free Clifford+T approximation of z-rotations
Ross, N. J., & Selinger, P. (2016) · Quantum Information and Computation · doi:10.26421/qic16.11-12-1 · Cited by 178
Exact synthesis of multi-qubit Clifford+T circuits
Giles, B. G., & Selinger, P. (2012) · arXiv.org · doi:10.1103/physreva.87.032332 · Cited by 172
Flagged first, then by citations
Cited by
Sorted by citations
Items 101–143 of 143
Advantages of a modular high-level quantum programming framework
Steiger, D. S., Häner, T., & Troyer, M. (2019) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2019.02.003 · Cited by 6
Trading Inverses for an Irrep in the Solovay-Kitaev TheoremPreprint
Bouland, A., & Ozols, M. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2018.6 · Cited by 9
Multi-objective evolutionary algorithms for quantum circuit discoveryPreprint
Potoček, V., Reynolds, A., Fedrizzi, A., & Corne, D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.04458 · Cited by 6
Probabilistic Unitary Synthesis with Optimal Accuracy
Akibue, S., Kato, G., & Tani, S. (2024) · ACM Transactions on Quantum Computing · doi:10.1145/3663576 · Cited by 16
Error crafting in mixed quantum gate synthesis
Yoshioka, N., Akibue, S., Morisaki, H., Tsubouchi, K., & Suzuki, Y. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01032-x · Cited by 8
Improving the implementation of quantum blockchain based on hypergraphs
Orts, F. J., Paulavičius, R., & Filatovas, E. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04096-w · Cited by 5
A Leap among Entanglement and Neural Networks: A Quantum Survey.Preprint
Massoli, F. V., Vadicamo, L., Amato, G. M., & Falchi, F. (2021) · arXiv (Cornell University) · Cited by 5
Quantum circuit optimization of an integer divider
Orts, F. J., Paulavičius, R., & Filatovas, E. (2024) · Journal of Systems and Software · doi:10.1016/j.jss.2024.112091 · Cited by 8
Trotter Simulation of Vibrational Hamiltonians on a Quantum Computer
Malpathak, S., Kallullathil, S. D., Loaiza, I., Fomichev, S., Arrazola, J. M., & Izmaylov, A. F. (2025) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.5c01600 · Cited by 7
Approximate Relational Reasoning for Quantum Programs
Yan, P., Jiang, H., & Yu, N. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-65633-0_22 · Cited by 4
Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
Hindlycke, C., & Larsson, J.-Å. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.l042027 · Cited by 4
Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
Xiang, D., Jiang, Q., Lu, L., Tan, S., & Yin, J. (2025) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca61900.2025.00031 · Cited by 4
Structured Theorem for Quantum Programs and its Applications
Yu, N. (2023) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3587154 · Cited by 3
Quantum advantage in temporally flat measurement-based quantum computation
de Oliveira, M., Barbosa, L. S., & Galvão, E. F. (2024) · Quantum · doi:10.22331/q-2024-04-09-1312 · Cited by 5
Amplitude-based implementation of the unit step function on a quantum computer
Koppe, J., & Wolf, M.-O. (2023) · Physical Review A · doi:10.1103/physreva.107.022606 · Cited by 3
Quantum state preparation via piecewise QSVT
O'Brien, O., & Sünderhauf, C. (2025) · Quantum · doi:10.22331/q-2025-07-03-1786 · Cited by 3
Feasibility of logical Bell state generation in memory assisted quantum networks
Galetsky, V., Vyas, N., Comin, A., & Nötzel, J. (2025) · Physical Review Research · doi:10.1103/rsrk-c7yg · Cited by 2
Fault-Tolerant Quantum Simulation of Generalized Hubbard Models
Bay-Smidt, A. J., Klausen, F. R., Sünderhauf, C., Izsák, R., Solomon, G. C., & Blunt, N. S. (2025) · PRX Quantum · doi:10.1103/gr4t-b1w5 · Cited by 8
Tkachenko, N. V., Ren, H., Billings, W. M., Tomann, R., Whaley, K. B., & Head‐Gordon, M. (2025) · Chemical Science · doi:10.1039/d5sc03585f · Cited by 4
Sun, X. (2016) · Scientia Sinica Informationis · doi:10.1360/n112016-00084 · Cited by 2
High-precision and low-depth quantum algorithm design for eigenstate problems
Sun, J., Zeng, P., Gur, T., & Kim, M. S. (2026) · Science Advances · doi:10.1126/sciadv.aeb1622 · Cited by 10
Tools for Quantum and Reversible Circuit Compilation
Roetteler, M. (2017) · International Workshop on Reversible Computation · doi:10.1007/978-3-319-59936-6_1 · Cited by 1
Self-citationResource comparison of two surface code implementations of small angle Z rotationsPreprint
Mishra, P., & Fowler, A. G. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.4948 · Cited by 2
High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
Weiden, M., Kalloor, J., Kubiatowicz, J., Younis, E., & Iancu, C. (2024) · QPL · doi:10.4204/eptcs.426.8 · Cited by 8
Catalytic z -rotations in constant T -depth
Kim, I. H. (2026) · Quantum · doi:10.22331/q-2026-08-13-2191 · Cited by 1
Optimal length of decomposition sequences composed of imperfect gates
Nam, Y., & Blümel, R. (2017) · Quantum Information Processing · doi:10.1007/s11128-017-1571-5 · Cited by 1
Lahiri, S., Kesh, M., Mandal, R., Bhattacharjee, A., Bhattacharya, S., Sinha, D., Bandyopadhyay, C., Biswal, L., Wille, R., & Drechsler, R. (2024) · International Conference on VLSI Design · doi:10.1109/vlsid60093.2024.00057 · Cited by 1
Synthesis of single-qutrit circuits from Clifford + R gates
Gustafson, E., Lamm, H., Liu, D., Murairi, E. M., & Zhu, S. (2025) · Physical Review A · doi:10.1103/98q1-3yv8 · Cited by 1
A Jordan-Wigner gadget that reduces T count by more than 6x for quantum chemistry applicationsPreprint
Pallister, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.05117 · Cited by 3
Ying, M. (2016) · Elsevier eBooks · doi:10.1016/b978-0-12-802306-8.00008-2
(2016) · Elsevier eBooks · doi:10.1016/b978-0-12-802306-8.09999-7
Ying, M. (2024) · Elsevier eBooks · doi:10.1016/b978-0-44-315942-8.00027-7
(2024) · Elsevier eBooks · doi:10.1016/b978-0-44-315942-8.00030-7
Prepare Linear Distributions with Quantum Arithmetic Units
Li, J. (2024) · Entropy · doi:10.3390/e26110912
A Holistic Approach to Rotation Synthesis for Fault- Tolerant Quantum Computation
Chen, T.-F., Liu, C.-H. M., & Jiang, J.-H. R. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00122
Transversal Architecture for Megaquop-Scale Quantum Simulation with Neutral Atoms
Ismail, R., Chen, I.-C., Zhao, C., Weiss, R., Liu, F., Zhou, H., Wang, S.-T., Sornborger, A. T., & Kornjača, M. (2026) · PRX Quantum · doi:10.1103/j2fw-ccmy · Cited by 23
Reducing T-count and T-depth in approximate quantum Fourier transform circuits
Park, B., & Ahn, D. (2025) · Scientific Reports · doi:10.1038/s41598-025-21087-2
Methods for optimizing the synthesis of quantum circuits
de Brugière, T. G. (2020) · theses.fr (ABES) · doi:10.70675/e70b70f9z8381z43a4z806fz68402f3080de · Cited by 4
Angle Domain Gaussian Perturbations via Ancilla Hamming WeightPreprint
Habib, I., & Ting, T. T. (2026) · Research Square · doi:10.21203/rs.3.rs-9487446/v1
Quantum Circuit Optimization Techniques: A Literature Survey
Макарова, М. И., Pastorello, D., Cavecchia, V., Blanzieri, E., Khadiev, K., & Rumyantsev, A. (2026) · Quantum Information & Computation · doi:10.2478/qic-2026-0008
Halving the arbitrary rotation cost of controlled, Trotterized time evolution
Anonymous, & Love, P. J. (2026) · Physical Review A · doi:10.1103/h9gv-ml7w
Anonymous, Yu, S., & Xiang, H. (2026) · Physical Review A · doi:10.1103/n2h3-x2wq
Verifying Repeat-until-Success Protocols using Automata
Lin, J.-A., Chen, Y., Havlík, J., Lengál, O., Lo, F.-Y., Tsai, W.-L., & Wu, Y.-J. (2026) · Proceedings of the ACM on Programming Languages · doi:10.1145/3839506
Metadata
- Authors
- Bocharov, A., Roetteler, M., & Svore, K. M.
- Affiliations
- Microsoft (United States) (US)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2015-02-27
- Volume
- 114
- Issue
- 8
- Pages
- 080502-080502
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1915167278
- Cited by
- 142
- References
- 22
- Citations by year
- 2026: 8 · 2025: 17 · 2024: 16 · 2023: 12 · 2022: 15 · 2021: 12 · 2020: 13 · 2019: 10 · 2018: 6 · 2017: 12 · 2016: 12 · 2015: 8
- FWCI
- 12.43
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- quantum circuit synthesis, T-count, ancilla qubits, measurement, quantum resource reduction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
