Quantum state preparation with optimal T-count

David Gosset; Robin Kothari; Kewen Wu

doi:10.22331/q-2026-07-22-2168

Quantum state preparation with optimal T-count

David Gosset^1,2,3, Robin Kothari¹, and Kewen Wu⁴

¹Google Quantum AI
²Department of Combinatorics and Optimization and Institute for Quantum Computing, University of Waterloo
³Perimeter Institute for Theoretical Physics
⁴Computing and Mathematical Sciences Department, Caltech

Published:	2026-07-22, volume 10, page 2168
Editor:	Lorenzo Leone
Eprint:	arXiv:2411.04790v3
Doi:	https://doi.org/10.22331/q-2026-07-22-2168
Citation:	Quantum 10, 2168 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

How many $T$ gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $\varepsilon$? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is

$\Theta\left(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon)\right)$

if we allow ancilla qubits. We also show that this is the optimal $T$-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $\varepsilon$. We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.

► BibTeX data

@article{Gosset2026quantumstate,
  doi = {10.22331/q-2026-07-22-2168},
  url = {https://doi.org/10.22331/q-2026-07-22-2168},
  title = {Quantum state preparation with optimal {T}-count},
  author = {Gosset, David and Kothari, Robin and Wu, Kewen},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2168},
  month = jul,
  year = {2026}
}

► References

[1] Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256, 2016. arXiv:1607.05256, doi:10.48550/arXiv.1607.05256.
https://doi.org/10.48550/arXiv.1607.05256
arXiv:1607.05256

[2] Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 115–128. IEEE, 2007. doi:10.1109/CCC.2007.27.
https://doi.org/10.1109/CCC.2007.27

[3] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52:3457–3467, Nov 1995. doi:10.1103/PhysRevA.52.3457.
https://doi.org/10.1103/PhysRevA.52.3457

[4] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum, 3:181, 2019. doi:10.22331/q-2019-09-02-181.
https://doi.org/10.22331/q-2019-09-02-181

[5] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. Lower bounds on the non-Clifford resources for quantum computations. Quantum Science and Technology, 5(3):035009, 2020. doi:10.1088/2058-9565/ab8963.
https://doi.org/10.1088/2058-9565/ab8963

[6] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809. IEEE, 2015. doi:10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54

[7] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by Clifford gates. Physical review letters, 116(25):250501, 2016. doi:10.1103/PhysRevLett.116.250501.
https://doi.org/10.1103/PhysRevLett.116.250501

[8] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. doi:10.1090/conm/305/05215.
https://doi.org/10.1090/conm/305/05215

[9] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A—Atomic, Molecular, and Optical Physics, 71(2):022316, 2005. doi:10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316

[10] Thomas Barthel and Jianfeng Lu. Fundamental limitations for measurements in quantum many-body systems. Physical Review Letters, 121(8):080406, 2018. doi:10.1103/PhysRevLett.121.080406.
https://doi.org/10.1103/PhysRevLett.121.080406

[11] Joan Boyar and René Peralta. The exact multiplicative complexity of the Hamming weight function. In Electronic Colloquium on Computational Complexity (ECCC’05),(049), 2005.

[12] Sergey Bravyi, Graeme Smith, and John A Smolin. Trading classical and quantum computational resources. Physical Review X, 6(2):021043, 2016. doi:10.1103/PhysRevX.6.021043.
https://doi.org/10.1103/PhysRevX.6.021043

[13] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354, 1998. doi:10.1098/rspa.1998.0164.
https://doi.org/10.1098/rspa.1998.0164

[14] Richard Cleve and Daniel Gottesman. Efficient computations of encodings for quantum error correction. Physical Review A, 56(1):76, 1997. doi:10.1103/PhysRevA.56.76.
https://doi.org/10.1103/PhysRevA.56.76

[15] Tyler D. Ellison, Kohtaro Kato, Zi-Wen Liu, and Timothy H. Hsieh. Symmetry-protected sign problem and magic in quantum phases of matter. Quantum, 5:612, 2021. doi:10.22331/q-2021-12-28-612.
https://doi.org/10.22331/q-2021-12-28-612

[16] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O’Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer. Real analysis in computer science: A collection of open problems, 2014. URL: https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf.
https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf

[17] Daniel Gottesman. The heisenberg representation of quantum computers. arXiv preprint quant-ph/9807006, 1998. arXiv:quant-ph/9807006, doi:10.48550/arXiv.quant-ph/9807006.
https://doi.org/10.48550/arXiv.quant-ph/9807006
arXiv:quant-ph/9807006

[18] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/0208112, 2002. arXiv:quant-ph/0208112, doi:10.48550/arXiv.quant-ph/0208112.
https://doi.org/10.48550/arXiv.quant-ph/0208112
arXiv:quant-ph/0208112

[19] Lov K Grover. Quantum computers can search rapidly by using almost any transformation. Physical Review Letters, 80(19):4329, 1998. doi:10.1103/PhysRevLett.80.4329.
https://doi.org/10.1103/PhysRevLett.80.4329

[20] Brett Giles and Peter Selinger. Exact synthesis of multiqubit Clifford+T circuits. Physical Review A—Atomic, Molecular, and Optical Physics, 87(3):032332, 2013. doi:10.1103/PhysRevA.87.032332.
https://doi.org/10.1103/PhysRevA.87.032332

[21] Craig Gidney, Noah Shutty, and Cody Jones. Magic state cultivation: growing t states as cheap as cnot gates. arXiv preprint arXiv:2409.17595, 2024. doi:10.48550/arXiv.2409.17595.
https://doi.org/10.48550/arXiv.2409.17595
arXiv:2409.17595

[22] Uffe Haagerup. The best constants in the Khintchine inequality. Studia Mathematica, 70(3):231–283, 1981. doi:10.4064/sm-70-3-231-283.
https://doi.org/10.4064/sm-70-3-231-283

[23] Alston S Householder. Unitary triangularization of a nonsymmetric matrix. Journal of the ACM (JACM), 5(4):339–342, 1958. doi:10.1145/320941.320947.
https://doi.org/10.1145/320941.320947

[24] Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang. Efficient discrete approximations of quantum gates. Journal of Mathematical Physics, 43(9):4445–4451, 2002. doi:10.1063/1.1495899.
https://doi.org/10.1063/1.1495899

[25] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem. In 37th Computational Complexity Conference, 2022. doi:10.4230/LIPIcs.CCC.2022.5.
https://doi.org/10.4230/LIPIcs.CCC.2022.5

[26] Vadym Kliuchnikov. Synthesis of unitaries with Clifford+T circuits. arXiv preprint arXiv:1306.3200, 2013. doi:10.48550/arXiv.1306.3200.
https://doi.org/10.48550/arXiv.1306.3200
arXiv:1306.3200

[27] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Information & Computation, 13(7-8):607–630, 2013. doi:10.26421/QIC13.7-8-4.
https://doi.org/10.26421/QIC13.7-8-4

[28] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits. IEEE Transactions on Computers, 65(1):161–172, 2015. doi:10.1109/TC.2015.2409842.
https://doi.org/10.1109/TC.2015.2409842

[29] William Kretschmer. Quantum mass production theorems. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.TQC.2023.10.
https://doi.org/10.4230/LIPIcs.TQC.2023.10

[30] Daniel Litinski. Magic state distillation: Not as costly as you think. Quantum, 3:205, 2019. doi:10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[31] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T gates for dirty qubits in state preparation and unitary synthesis. Quantum, 8:1375, 2024. doi:10.22331/q-2024-06-17-1375.
https://doi.org/10.22331/q-2024-06-17-1375

[32] Lorenzo Leone, Salvatore FE Oliviero, and Alioscia Hamma. Stabilizer Rényi entropy. Physical Review Letters, 128(5):050402, 2022. doi:10.1103/PhysRevLett.128.050402.
https://doi.org/10.1103/PhysRevLett.128.050402

[33] Zi-Wen Liu and Andreas Winter. Many-body quantum magic. PRX Quantum, 3(2):020333, 2022. doi:10.1103/PRXQuantum.3.020333.
https://doi.org/10.1103/PRXQuantum.3.020333

[34] Dmitri Maslov. Optimal and asymptotically optimal nct reversible circuits by the gate types. Quantum Information & Computation, 16(13-14):1096–1112, 2016. doi:10.26421/QIC16.13-14-2.
https://doi.org/10.26421/QIC16.13-14-2

[35] Saeed Mehraban and Mehrdad Tahmasbi. Quadratic lower bounds on the approximate stabilizer rank: A probabilistic approach. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 608–619, 2024. doi:10.1145/3618260.3649733.
https://doi.org/10.1145/3618260.3649733

[36] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010. doi:10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[37] Eduard I. Nechiporuk. On the complexity of schemes in some bases containing nontrivial elements with zero weights. Problemy kibernetiki, 8:123–160, 1962.

[38] Denis Pankratov. Direct sum questions in classical communication complexity. Master's thesis, University of Chicago, 2012.

[39] Gregory Rosenthal. Query and depth upper bounds for quantum unitaries via grover search. arXiv preprint arXiv:2111.07992, 2021. arXiv:2111.07992, doi:10.48550/arXiv.2111.07992.
https://doi.org/10.48550/arXiv.2111.07992
arXiv:2111.07992

[40] Gregory Rosenthal. Efficient quantum state synthesis with one query. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2508–2534. SIAM, 2024. doi:10.1137/1.9781611977912.89.
https://doi.org/10.1137/1.9781611977912.89

[41] Neil J. Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of Z-rotations. Quantum Inf. Comput., 16(11&12):901–953, 2016. doi:10.26421/QIC16.11-12-1.
https://doi.org/10.26421/QIC16.11-12-1

[42] Claus-Peter Schnorr. The multiplicative complexity of Boolean functions. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 6th International Conference, AAECC-6 Rome, Italy, July 4–8, 1988 Proceedings 6, pages 45–58. Springer, 1989. doi:10.1007/3-540-51083-4_47.
https://doi.org/10.1007/3-540-51083-4_47

[43] Peter Selinger. Efficient Clifford+T approximation of single-qubit operators. Quantum Information & Computation, 15(1-2):159–180, 2015. doi:10.26421/QIC15.1-2-10.
https://doi.org/10.26421/QIC15.1-2-10

[44] Xinyu Tan. Unitary synthesis with fewer t gates. arXiv preprint arXiv:2509.25702, 2025. doi:10.48550/arXiv.2509.25702.
https://doi.org/10.48550/arXiv.2509.25702
arXiv:2509.25702

[45] Dietmar Uhlig. Networks computing Boolean functions for multiple input values. In Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 165–173, 1992. doi:10.1017/CBO9780511526633.013.
https://doi.org/10.1017/CBO9780511526633.013

[46] D Ulig. On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Mathematical Notes of the Academy of Sciences of the USSR, 15:558–562, 1974. doi:10.1007/BF01152835.
https://doi.org/10.1007/BF01152835

[47] Victor Veitch, S. A. Hamed Mousavian, Daniel Gottesman, and Joseph Emerson. The resource theory of stabilizer quantum computation. New Journal of Physics, 16(1):013009, 2014. doi:10.1088/1367-2630/16/1/013009.
https://doi.org/10.1088/1367-2630/16/1/013009

[48] Nathan Wiebe and Andrew Childs. Hamiltonian simulation using linear combinations of unitary operations. In APS March Meeting Abstracts, volume 2012, pages T30–003, 2012. doi:10.26421/QIC12.11-12-1.
https://doi.org/10.26421/QIC12.11-12-1

[49] Wikipedia. Covering number — Wikipedia, the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Covering%20number&oldid=1190804299, 2024. [Online; accessed 20-September-2024].
http://en.wikipedia.org/w/index.php?title=Covering%20number&oldid=1190804299

[50] Wikipedia. Khintchine inequality — Wikipedia, the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Khintchine%20inequality&oldid=1200765288, 2024. [Online; accessed 11-June-2024].
http://en.wikipedia.org/w/index.php?title=Khintchine%20inequality&oldid=1200765288

[51] Mark M Wilde. From classical to quantum shannon theory. arXiv preprint arXiv:1106.1445, 2011. doi:10.48550/arXiv.1106.1445.
https://doi.org/10.48550/arXiv.1106.1445
arXiv:1106.1445

Cited by

[1] Danial Motlagh, Robert A. Lang, Paarth Jain, Jorge A. Campos-Gonzalez-Angulo, William Maxwell, Tao Zeng, Alan Aspuru-Guzik, and Juan Miguel Arrazola, "Quantum algorithm for vibronic dynamics: case study on singlet fission solar cell design", Quantum Science and Technology 10 4, 045048 (2025).

[2] Mathias Weiden, Justin Kalloor, John Kubiatowicz, Ed Younis, and Costin Iancu, "High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization", arXiv:2409.00433, (2024).

[3] E. Rule, I. A. Chernyshev, I. Stetcu, J. Carlson, and R. Weiss, "Recursive algorithm for constructing antisymmetric fermionic states in first quantization mapping", Quantum 10, 2056 (2026).

[4] Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, and Stephen P. Jordan, "Verifiable Quantum Advantage via Optimized DQI Circuits", arXiv:2510.10967, (2025).

[5] David Gosset, Robin Kothari, and Chenyi Zhang, "Multi-qubit Toffoli with exponentially fewer T gates", arXiv:2510.07223, (2025).

[6] Jingquan Luo and Lvzhou Li, "Optimal Circuit Size for Fixed-Hamming-Weight Quantum States Preparation", arXiv:2508.17197, (2025).

[7] William J. Huggins, Tanuj Khattar, and Nathan Wiebe, "Productionizing Quantum Mass Production", arXiv:2506.00132, (2025).

[8] Giacomo Belli, Marco Mordacci, and Michele Amoretti, "SRBB-Based Quantum State Preparation", arXiv:2503.13647, (2025).

[9] Jingquan Luo, Guanzhong Li, and Lvzhou Li, "Space-time tradeoff for sparse quantum state preparation", arXiv:2506.16964, (2025).

[10] Michał Szczepanik, Ákos Nagy, and Emil Żak, "Simulating high-accuracy nuclear motion Hamiltonians using discrete variable representation and Walsh-Hadamard QROM on fault-tolerant quantum computers", arXiv:2510.19062, (2025).

[11] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

[12] Guedong Park, Jaekwon Chang, Yosep Kim, Yong Siah Teo, and Hyunseok Jeong, "Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic", arXiv:2602.09710, (2026).

[13] Renaud Vilmart, Sunheang Ty, and Chetra Mang, "Resource-Efficient Synthesis of Sparse Quantum States", arXiv:2508.05386, (2025).

[14] Emmanuel Hainry, Romain Péchoux, and Mário Alberto Machado da Silva, "Branch Sequentialization in Quantum Polytime", arXiv:2412.09153, (2024).

[15] Berta Casas, Paolo Braccia, Élie Gouzien, M. Cerezo, and Diego García-Martín, "Matchgate synthesis via Clifford matchgates and $T$ gates", arXiv:2602.05425, (2026).

[16] Guillermo Alonso-Linaje, Utkarsh Azad, Jay Soni, Jarrett Smalley, Leigh Lapworth, and Juan Miguel Arrazola, "Quantum compilation framework for data loading", arXiv:2512.05183, (2025).

[17] Daniel Grier, Jackson Morris, and Kewen Wu, "$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)", arXiv:2601.03243, (2026).

[18] Emil Zak, "Fault-tolerant quantum simulation of the Pauli-Breit Hamiltonian for ab initio hybrid quantum-classical molecular design with applications to photodynamic therapy", arXiv:2601.18898, (2026).

[19] Keisuke Murota, Frédéric Sauvage, Marco Ballarin, Gabriel Matos, and Enrico Rinaldi, "Exact log-depth preparation of highly entangled matrix product states", arXiv:2606.24475, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-12 19:50:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-12 19:50:14).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.