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

Could not fetch Crossref cited-by data during last attempt 2026-07-22 07:13:43: Could not fetch cited-by data for 10.22331/q-2026-07-22-2168 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-07-22 07:13:44: Cannot retrieve data from ADS due to rate limitations.

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.