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
Faster quantum chemistry simulation on fault-tolerant quantum computers
Cody Jones, N., Whitfield, J. D., McMahon, P. L., Yung, M.-H., Meter, R. V., Aspuru-Guzik, A., & Yamamoto, Y. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/11/115023 · Cited by 145
Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
Paetznick, A., & Svore, K. M. (2014) · Quantum Information and Computation · doi:10.26421/qic14.15-16-2 · Cited by 110
Self-citationConstructing arbitrary Steane code single logical qubit fault-tolerant gates
Fowler, A. G. (2011) · Quantum Information and Computation · doi:10.26421/qic11.9-10-10 · Cited by 104
Ancilla-driven universal quantum computation
Anders, J., Oi, D. K. L., Kashefi, E., Browne, D. E., & Andersson, E. (2010) · Physical Review A · doi:10.1103/physreva.82.020301 · Cited by 76
Resource-Optimal Single-Qubit Quantum Circuits
Bocharov, A., & Svore, K. M. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.190501 · Cited by 69
Self-citationDistillation of nonstabilizer states for universal quantum computation
Duclos-Cianci, G., & Svore, K. M. (2013) · Physical Review A · doi:10.1103/physreva.88.042325 · Cited by 54
Self-citationFloating point representations in quantum circuit synthesis
Wiebe, N., & Kliuchnikov, V. (2013) · New Journal of Physics · doi:10.1088/1367-2630/15/9/093041 · Cited by 53
Synthesis of unitaries with Clifford+T circuitsPreprint
Kliuchnikov, V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.3200 · Cited by 24
Schmidt, W. M. (1991) · Lecture notes in mathematics · doi:10.1007/bfb0098248 · Cited by 20
Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operatorsPreprint
Giles, B. G., & Selinger, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.6584 · Cited by 19
Efficient Clifford+T approximation of single-qubit operatorsPreprint
Selinger, P. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.6253 · Cited by 18
Ancilla Driven Quantum Computation with arbitrary entangling strengthPreprint
Shah, K. H., & Oi, D. K. L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.2066 · Cited by 9
Cited by
Sorted by citations
Majorana zero modes and topological quantum computation
Sarma, S. D., Freedman, M., & Nayak, C. (2015) · npj Quantum Information · doi:10.1038/npjqi.2015.1 · Cited by 1,180
Elucidating reaction mechanisms on quantum computers
Reiher, M., Wiebe, N., Svore, K. M., Wecker, D., & Troyer, M. (2017) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1619152114 · Cited by 745
Self-citationHow to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
Practical quantum advantage in quantum simulation
Daley, A. J., Bloch, I., Kokail, C., Flannigan, S., Pearson, N., Troyer, M., & Zoller, P. (2022) · Nature · doi:10.1038/s41586-022-04940-6 · Cited by 783
Toward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
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
