{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:38:17Z","timestamp":1773193097913,"version":"3.50.1"},"reference-count":43,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension-N<\/mml:mi><\/mml:math> pure quantum state specified by a list of N<\/mml:mi><\/mml:math> classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O<\/mml:mi><\/mml:mrow>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>N<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:mrow>)<\/mml:mo><\/mml:math> clean qubits and a tunable number of &#x223C;<\/mml:mo>(<\/mml:mo>&#x03BB;<\/mml:mi>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>N<\/mml:mi><\/mml:mrow><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:mfrac>)<\/mml:mo><\/mml:mrow>)<\/mml:mo><\/mml:math> dirty qubits, to reduce the T-gate cost to O<\/mml:mi><\/mml:mrow>(<\/mml:mo>N<\/mml:mi>&#x03BB;<\/mml:mi><\/mml:mfrac>+<\/mml:mo>&#x03BB;<\/mml:mi>log<\/mml:mi>&#x2061;<\/mml:mo>N<\/mml:mi>&#x03F5;<\/mml:mi><\/mml:mfrac><\/mml:mrow>log<\/mml:mi>&#x2061;<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>N<\/mml:mi><\/mml:mrow><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:mfrac><\/mml:mrow>)<\/mml:mo><\/mml:math>. This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.<\/jats:p>","DOI":"10.22331\/q-2024-06-17-1375","type":"journal-article","created":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T14:41:42Z","timestamp":1718635302000},"page":"1375","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":33,"title":["Trading T gates for dirty qubits in state preparation and unitary synthesis"],"prefix":"10.22331","volume":"8","author":[{"given":"Guang Hao","family":"Low","sequence":"first","affiliation":[{"name":"Quantum Architectures and Computation, Microsoft Research, Washington, Redmond, USA"},{"name":"Azure Quantum, Microsoft, Washington, Redmond, USA"}]},{"given":"Vadym","family":"Kliuchnikov","sequence":"additional","affiliation":[{"name":"Quantum Architectures and Computation, Microsoft Research, Washington, Redmond, USA"},{"name":"Azure Quantum, Microsoft, Washington, Redmond, USA"}]},{"given":"Luke","family":"Schaeffer","sequence":"additional","affiliation":[{"name":"Quantum Architectures and Computation, Microsoft Research, Washington, Redmond, USA"},{"name":"Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, Maryland, College Park, USA"}]}],"member":"9598","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631\u2013633 (2014).","DOI":"10.1038\/nphys3029"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. ``Simulating Hamiltonian dynamics with a truncated Taylor series''. Physical Review Letters 114, 090502 (2015).","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian simulation by quantum signal processing''. Physical Review Letters 118, 010501 (2017).","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009).","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Chunhao Wang and Leonard Wossnig. ``A quantum algorithm for simulating non-sparse Hamiltonians''. Quantum Information & Computation 20, 597\u2013615 (2020).","DOI":"10.26421\/QIC20.7-8-5"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Nathan Wiebe, Daniel Braun, and Seth Lloyd. ``Quantum algorithm for data fitting''. Physical Review Letters 109, 050505 (2012).","DOI":"10.1103\/PhysRevLett.109.050505"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov and Amnon Ta-Shma. ``Adiabatic quantum state generation and statistical zero knowledge''. Proceedings of the thirty-fifth ACM symposium on Theory of computingPage 20 (2003).","DOI":"10.1145\/780542.780546"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. ``Encoding electronic spectra in quantum circuits with linear T complexity''. Physical Review X 8, 041015 (2018).","DOI":"10.1103\/PhysRevX.8.041015"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. (2010). 10th anniversary edition.","DOI":"10.1017\/CBO9780511976667"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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, 607\u2013630 (2013).","DOI":"10.26421\/QIC13.7-8-4"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Neil J Ross and Peter Selinger. ``Optimal ancilla-free Clifford+T approximation of Z-rotations''. Quantum Information & Computation 16, 901\u2013953 (2016).","DOI":"10.26421\/QIC16.11-12-1"},{"key":"11","doi-asserted-by":"publisher","unstructured":"V. V. Shende, S. S. Bullock, and I. L. Markov. ``Synthesis of quantum-logic circuits''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000\u20131010 (2006).","DOI":"10.1109\/TCAD.2005.855930"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang. ``Efficient discrete approximations of quantum gates''. Journal of Mathematical Physics 43, 4445\u20134451 (2002).","DOI":"10.1063\/1.1495899"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. ``A game of surface codes: large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019).","DOI":"10.22331\/q-2019-03-05-128"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. ``Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42, 3301\u20133314 (2023).","DOI":"10.1109\/TCAD.2023.3244885"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).","DOI":"10.22331\/q-2019-07-12-163"},{"key":"16","unstructured":"Guang Hao Low and Isaac L. Chuang. ``Hamiltonian simulation by uniform spectral amplification'' (2017). arXiv:1707.05391."},{"key":"17","unstructured":"Scott Aaronson. ``The complexity of quantum states and transformations: From quantum money to black holes'' (2016). arXiv:1607.05256."},{"key":"18","doi-asserted-by":"publisher","unstructured":"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''. Physical Review A 52, 3457\u20133467 (1995).","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. ``Toward the first quantum simulation with quantum speedup''. Proceedings of the National Academy of Sciences 115, 9456\u20139461 (2018).","DOI":"10.1073\/pnas.1801723115"},{"key":"20","unstructured":"Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). arXiv:quant-ph\/0208112."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Craig Gidney. ``Halving the cost of quantum addition''. Quantum 2, 74 (2018).","DOI":"10.22331\/q-2018-06-18-74"},{"key":"22","unstructured":"Guang Hao Low. ``Halving the cost of quantum multiplexed rotations'' (2021). arXiv:2110.13439."},{"key":"23","doi-asserted-by":"publisher","unstructured":"Alston S. Householder. ``Unitary triangularization of a nonsymmetric matrix''. Journal of the ACM 5, 339\u2013342 (1958).","DOI":"10.1145\/320941.320947"},{"key":"24","unstructured":"Vadym Kliuchnikov. ``Synthesis of unitaries with Clifford+T circuits'' (2013). arXiv:1306.3200."},{"key":"25","doi-asserted-by":"publisher","unstructured":"David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo. ``An algorithm for the T-count''. Quantum Information & Computation 14, 1261\u20131276 (2014).","DOI":"10.26421\/QIC14.15-16-1"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Caterina E. Mora and Hans J. Briegel. ``Algorithmic complexity and entanglement of quantum states''. Physical Review Letters 95, 200503 (2005).","DOI":"10.1103\/PhysRevLett.95.200503"},{"key":"27","unstructured":"E. Knill. ``Approximation by quantum circuits'' (1995). arXiv:quant-ph\/9508006."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. ``Lower bounds on the non-clifford resources for quantum computations''. Quantum Science and Technology 5, 035009 (2020).","DOI":"10.1088\/2058-9565\/ab8963"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. ``Fault-tolerant resource estimation of quantum random-access memories''. IEEE Transactions on Quantum Engineering 1, 1\u201313 (2020).","DOI":"10.1109\/TQE.2020.2965803"},{"key":"30","unstructured":"Thomas H\u00e4ner, Vadym Kliuchnikov, Martin Roetteler, and Mathias Soeken. ``Space-time optimized table lookup'' (2022). arXiv:2211.01133."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Kaiwen Gui, Alexander M. Dalzell, Alessandro Achille, Martin Suchara, and Frederic T. Chong. ``Spacetime-efficient low-depth quantum state preparation with applications''. Quantum 8, 1257 (2024).","DOI":"10.22331\/q-2024-02-15-1257"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. ``The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation''. 46th International Colloquium on Automata, Languages, and Programming 132, 33:1\u201333:14 (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"33","doi-asserted-by":"publisher","unstructured":"B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng. ``Quantum resources required to block-encode a matrix of classical data''. IEEE Transactions on Quantum Engineering 3, 1\u201323 (2022).","DOI":"10.1109\/TQE.2022.3231194"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang. ``Resilience of quantum random access memory to generic noise''. PRX Quantum 2, 020311 (2021).","DOI":"10.1103\/PRXQuantum.2.020311"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush. ``Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization''. Quantum 3, 208 (2019).","DOI":"10.22331\/q-2019-12-02-208"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Vera von Burg, Guang Hao Low, Thomas H\u00e4ner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. ``Quantum computing enhanced computational catalysis''. Physical Review Research 3, 033055 (2021).","DOI":"10.1103\/PhysRevResearch.3.033055"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush. ``Even more efficient quantum computations of chemistry through tensor hypercontraction''. PRX Quantum 2, 030305 (2021).","DOI":"10.1103\/PRXQuantum.2.030305"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. ``Quantum algorithms for quantum chemistry and quantum materials science''. Chemical Reviews 120, 12685\u201312717 (2020).","DOI":"10.1021\/acs.chemrev.9b00829"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. ``Compilation of fault-tolerant quantum heuristics for combinatorial optimization''. PRX Quantum 1, 020312 (2020).","DOI":"10.1103\/PRXQuantum.1.020312"},{"key":"40","unstructured":"Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. ``A new quantum ripple-carry addition circuit'' (2004). arXiv:quant-ph\/0410184."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Thomas H\u00e4ner, Martin Roetteler, and Krysta M Svore. ``Factoring using 2n + 2 qubits with Toffoli based modular multiplication''. Quantum Information & Computation 17, 673\u2013684 (2017).","DOI":"10.26421\/QIC17.7-8-7"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. ``Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits''. Physical Review Letters 110, 190502 (2013).","DOI":"10.1103\/PhysRevLett.110.190502"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-06-17-1375\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T14:41:50Z","timestamp":1718635310000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-06-17-1375\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":43,"URL":"https:\/\/doi.org\/10.22331\/q-2024-06-17-1375","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,17]]},"article-number":"1375"}}