Trading T gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low; Vadym Kliuchnikov; Luke Schaeffer

doi:10.22331/q-2024-06-17-1375

Trading T gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low^1,2, Vadym Kliuchnikov^1,2, and Luke Schaeffer^1,3,4

¹Quantum Architectures and Computation, Microsoft Research, Washington, Redmond, USA
²Azure Quantum, Microsoft, Washington, Redmond, USA
³Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA
⁴Joint Center for Quantum Information and Computer Science, University of Maryland, Maryland, College Park, USA

Published:	2024-06-17, volume 8, page 1375
Eprint:	arXiv:1812.00954v2
Doi:	https://doi.org/10.22331/q-2024-06-17-1375
Citation:	Quantum 8, 1375 (2024).

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

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$ pure quantum state specified by a list of $N$ classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses $\mathcal{O}(\log{(N/\epsilon)})$ clean qubits and a tunable number of $\sim(\lambda\log{(\frac{\log{N}}{\epsilon})})$ dirty qubits, to reduce the T-gate cost to $\mathcal{O}(\frac{N}{\lambda}+\lambda\log{\frac{N}{\epsilon}}\log{\frac{\log{N}}{\epsilon}})$. 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.

Featured image: Our key result is a realization of any lookup table with $N$ addresses to $b$-bit words by our `SelectSwap' quantum circuit that uses as few as $\mathcal{O}(\sqrt{N b})$ non-Clifford T gates.

TQC 2019

Popular summary

The dominant cost in many quantum algorithms that compute on classical data is the number of queries made to so-called quantum oracles encoding the data. Minimizing the cost of the quantum circuits implementing such oracles is hence of great interest.

Often, interesting computations require a very large number of queries on a very large amount of classical data. Such large computations necessitate fault-tolerant quantum computation on logical qubits, which have a cost model where Clifford gates are cheap but non-Clifford gates are expensive. In contrast, physical qubits typically have a cost model with cheap single-qubit non-Clifford gates but expensive two-qubit Clifford gates.

Motivated by the constraints of fault-tolerant quantum computation, we present a family of quantum circuits that realize arbitrary quantum oracles with the fewest number of non-Clifford gates, up to an optimal square-root factor improvement over prior art. This work enables more accurate costing of quantum algorithms in the fault-tolerant regime.

► BibTeX data

@article{Low2024tradingtgatesdirty,
  doi = {10.22331/q-2024-06-17-1375},
  url = {https://doi.org/10.22331/q-2024-06-17-1375},
  title = {Trading {T} gates for dirty qubits in state preparation and unitary synthesis},
  author = {Low, Guang Hao and Kliuchnikov, Vadym and Schaeffer, Luke},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1375},
  month = jun,
  year = {2024}
}

► References

[1] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014).
https://doi.org/10.1038/nphys3029

[2] 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).
https://doi.org/10.1103/PhysRevLett.114.090502

[3] Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian simulation by quantum signal processing''. Physical Review Letters 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501

[4] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502

[5] Chunhao Wang and Leonard Wossnig. ``A quantum algorithm for simulating non-sparse Hamiltonians''. Quantum Information & Computation 20, 597–615 (2020).
https://doi.org/10.26421/QIC20.7-8-5

[6] Nathan Wiebe, Daniel Braun, and Seth Lloyd. ``Quantum algorithm for data fitting''. Physical Review Letters 109, 050505 (2012).
https://doi.org/10.1103/PhysRevLett.109.050505

[7] 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).
https://doi.org/10.1145/780542.780546

[8] 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).
https://doi.org/10.1103/PhysRevX.8.041015

[9] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. (2010). 10th anniversary edition.
https://doi.org/10.1017/CBO9780511976667

[10] 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–630 (2013).
https://doi.org/10.26421/QIC13.7-8-4

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

[12] 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–1010 (2006).
https://doi.org/10.1109/TCAD.2005.855930

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

[14] Daniel Litinski. ``A game of surface codes: large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[15] 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–3314 (2023).
https://doi.org/10.1109/TCAD.2023.3244885

[16] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[17] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian simulation by uniform spectral amplification'' (2017). arXiv:1707.05391.
arXiv:1707.05391

[18] Scott Aaronson. ``The complexity of quantum states and transformations: From quantum money to black holes'' (2016). arXiv:1607.05256.
arXiv:1607.05256

[19] 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–3467 (1995).
https://doi.org/10.1103/PhysRevA.52.3457

[20] 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–9461 (2018).
https://doi.org/10.1073/pnas.1801723115

[21] Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). arXiv:quant-ph/0208112.
arXiv:quant-ph/0208112

[22] Craig Gidney. ``Halving the cost of quantum addition''. Quantum 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74

[23] Guang Hao Low. ``Halving the cost of quantum multiplexed rotations'' (2021). arXiv:2110.13439.
arXiv:2110.13439

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

[25] Vadym Kliuchnikov. ``Synthesis of unitaries with Clifford+T circuits'' (2013). arXiv:1306.3200.
arXiv:1306.3200

[26] David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo. ``An algorithm for the T-count''. Quantum Information & Computation 14, 1261–1276 (2014).
https://doi.org/10.26421/QIC14.15-16-1

[27] Caterina E. Mora and Hans J. Briegel. ``Algorithmic complexity and entanglement of quantum states''. Physical Review Letters 95, 200503 (2005).
https://doi.org/10.1103/PhysRevLett.95.200503

[28] E. Knill. ``Approximation by quantum circuits'' (1995). arXiv:quant-ph/9508006.
arXiv:quant-ph/9508006

[29] 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).
https://doi.org/10.1088/2058-9565/ab8963

[30] Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. ``Fault-tolerant resource estimation of quantum random-access memories''. IEEE Transactions on Quantum Engineering 1, 1–13 (2020).
https://doi.org/10.1109/TQE.2020.2965803

[31] Thomas Häner, Vadym Kliuchnikov, Martin Roetteler, and Mathias Soeken. ``Space-time optimized table lookup'' (2022). arXiv:2211.01133.
arXiv:2211.01133

[32] 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).
https://doi.org/10.22331/q-2024-02-15-1257

[33] Shantanav Chakraborty, András Gilyén, 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–33:14 (2019).
https://doi.org/10.4230/LIPIcs.ICALP.2019.33

[34] 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–23 (2022).
https://doi.org/10.1109/TQE.2022.3231194

[35] 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).
https://doi.org/10.1103/PRXQuantum.2.020311

[36] 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).
https://doi.org/10.22331/q-2019-12-02-208

[37] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. ``Quantum computing enhanced computational catalysis''. Physical Review Research 3, 033055 (2021).
https://doi.org/10.1103/PhysRevResearch.3.033055

[38] 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).
https://doi.org/10.1103/PRXQuantum.2.030305

[39] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. ``Quantum algorithms for quantum chemistry and quantum materials science''. Chemical Reviews 120, 12685–12717 (2020).
https://doi.org/10.1021/acs.chemrev.9b00829

[40] 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).
https://doi.org/10.1103/PRXQuantum.1.020312

[41] 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.
arXiv:quant-ph/0410184

[42] Thomas Häner, Martin Roetteler, and Krysta M Svore. ``Factoring using 2n + 2 qubits with Toffoli based modular multiplication''. Quantum Information & Computation 17, 673–684 (2017).
https://doi.org/10.26421/QIC17.7-8-7

[43] 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).
https://doi.org/10.1103/PhysRevLett.110.190502

Cited by

[1] Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha, "Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates", Quantum 8, 1530 (2024).

[2] Charles Yuan, "Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra", Proceedings of the ACM on Programming Languages 10 PLDI, 200 (2026).

[3] Jack S. Baker, Pablo A. M. Casares, Modjtaba Shokrian Zini, Jaydeep Thik, Debasish Banerjee, Chen Ling, Alain Delgado, and Juan Miguel Arrazola, "Simulating optically active spin defects with a quantum computer", Physical Review A 110 3, 032606 (2024).

[4] Hengyun Zhou, Casey Duckering, Chen Zhao, Dolev Bluvstein, Madelyn Cain, Aleksander Kubica, Sheng-Tao Wang, and Mikhail D. Lukin, Proceedings of the 52nd Annual International Symposium on Computer Architecture 1432 (2025) ISBN:9798400712616.

[5] Xiao-Ming Zhang, "Robust and Optimal Loading of General Classical Data Into Quantum Computers", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 45 3, 1170 (2026).

[6] Matias Ginzburg and Ugo Marzolino, "Error convergence of quantum linear system solvers", Physical Review A 113 6, 062436 (2026).

[7] Shuchen Zhu, Aarthi Sundaram, and Guang Hao Low, "Unified architecture for quantum lookup tables", Physical Review Research 7 4, 043230 (2025).

[8] Shifan Xu, Alvin Lu, and Yongshan Ding, Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 390 (2025) ISBN:9798400710797.

[9] Jiqi Li, Jingyi Mei, Wang Fang, and Ji Guan, Lecture Notes in Computer Science 16684, 326 (2026) ISBN:978-3-032-32536-5.

[10] Giacomo Lancellotti, Alberto Guerrini, Giacomo Ranieri, Valeria Zaffaroni, and Paolo Cremonesi, 2025 IEEE International Conference on Quantum Artificial Intelligence (QAI) 41 (2025) ISBN:979-8-3315-6986-0.

[11] Zhicheng Zhang and Mingsheng Ying, "Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs", Proceedings of the ACM on Programming Languages 9 PLDI, 822 (2025).

[12] Wei Zi, Siyi Wang, Hyunji Kim, Xiaoming Sun, Anupam Chattopadhyay, and Patrick Rebentrost, "Efficient quantum circuits for machine learning activation functions including constant T-depth ReLU", Physical Review Research 6 4, 043048 (2024).

[13] Samuel Jaques and Arthur G. Rattew, "QRAM: A Survey and Critique", Quantum 9, 1922 (2025).

[14] Hyeonjun Yeo, Ha Eum Kim, IlKwon Sohn, and Kabgyun Jeong, "Reducing circuit depth in quantum state preparation for quantum simulation using measurements and feedforward", Physical Review Applied 23 5, 054066 (2025).

[15] Hang Zou, Erika Magnusson, Hampus Brunander, Werner Dobrautz, and Martin Rahm, "Multireference error mitigation for quantum computation of chemistry", Digital Discovery 4 9, 2521 (2025).

[16] Sam McArdle, András Gilyén, and Mario Berta, "Quantum State Preparation without Coherent Arithmetic", Physical Review Letters 136 24, 240603 (2026).

[17] Athena Caesura, Cristian L. Cortes, William Pol, Sukin Sim, Mark Steudtner, Gian-Luca R. Anselmetti, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, Michael Streif, and Christofer S. Tautermann, "Faster Quantum Chemistry Simulations on a Quantum Computer with Improved Tensor Factorization and Active Volume Compilation", PRX Quantum 6 3, 030337 (2025).

[18] Calvin Ku, Yu-Cheng Chen, Alice Hu, and Min-Hsiu Hsieh, "Benchmarking quantum simulation of chemical Hamiltonians using the sorted-list encoding", Physical Review Research 8 3, 033091 (2026).

[19] 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).

[20] Priyanka Mukhopadhyay, "A quantum random access memory (QRAM) using a polynomial encoding of binary strings", Scientific Reports 15 1, 11002 (2025).

[21] Hiroaki Murakami, Kenzo Makino, Yasunori Lee, Keita Kanno, and Tomonori Fukuta, Communications in Computer and Information Science 2743, 329 (2026) ISBN:978-3-032-13851-4.

[22] Oliver O'Brien and Christoph Sünderhauf, "Quantum state preparation via piecewise QSVT", Quantum 9, 1786 (2025).

[23] Daniel Marti-Dafcik, Hugh G. A. Burton, and David P. Tew, "Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers", Physical Review Research 7 1, 013191 (2025).

[24] William J. Huggins, Oskar Leimkuhler, Torin F. Stetina, and K. Birgitta Whaley, "Efficient State Preparation for the Quantum Simulation of Molecules in First Quantization", PRX Quantum 6 2, 020319 (2025).

[25] Dominic W. Berry, Yu Tong, Tanuj Khattar, Alec White, Tae In Kim, Guang Hao Low, Sergio Boixo, Zhiyan Ding, Lin Lin, Seunghoon Lee, Garnet Kin-Lic Chan, Ryan Babbush, and Nicholas C. Rubin, "Rapid Initial-State Preparation for the Quantum Simulation of Strongly Correlated Molecules", PRX Quantum 6 2, 020327 (2025).

[26] Bonan Su, Li Zhou, Yuan Feng, and Mingsheng Ying, Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 274 (2026) ISBN:9798400723599.

[27] R Au-Yeung, B Camino, O Rathore, and V Kendon, "Quantum algorithms for scientific computing", Reports on Progress in Physics 87 11, 116001 (2024).

[28] Parfait Atchade-Adelomou and Laia Coronas Sala, "A Quantum Strategy for the Simulation of Large Proteins: From Fragmentation in Small Proteins to Scalability in Complex Systems", Electronics 14 13, 2601 (2025).

[29] Tatsuya Tomaru, Hideo Takahashi, Toshiyuki Hirano, Saisei Tahara, and Fumitoshi Sato, "Chemical reaction simulator on quantum computers by first quantization—Basic treatment: Theoretical", AIP Advances 14 12, 125306 (2024).

[30] Matthias Rosenkranz, Eric Brunner, Gabriel Marin-Sanchez, Nathan Fitzpatrick, Silas Dilkes, Yao Tang, Yuta Kikuchi, and Marcello Benedetti, "Quantum state preparation for multivariate functions", Quantum 9, 1703 (2025).

[31] Pauline J. Ollitrault, Jérôme F. Gonthier, Dario Rocca, Gian-Luca Anselmetti, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Improving the Runtime of Quantum Phase Estimation for Chemistry through Basis Set Optimization", Journal of Chemical Theory and Computation 21 23, 12034 (2025).

[32] Natchapol Patamawisut, Naphan Benchasattabuse, Michal Hajdušek, and Rodney Van Meter, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 291 (2025) ISBN:979-8-3315-5736-2.

[33] Francesco Cesa, Hannes Bernien, and Hannes Pichler, "Resource-state quantum RAM for fast and error-correctable queries", Nature Communications 17 1, 7152 (2026).

[34] Oskar Leimkuhler and K. Birgitta Whaley, "A quantum eigenvalue solver based on tensor networks", npj Quantum Information 11 1, 184 (2025).

[35] Aleksei V. Ivanov, Andrew Patterson, Marius Bothe, Christoph Sünderhauf, Bjorn K. Berntson, Jens Jørgen Mortensen, Mikael Kuisma, Earl Campbell, and Róbert Izsák, "Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set", Journal of Chemical Theory and Computation 21 15, 7360 (2025).

[36] Erik J. Gustafson, Henry Lamm, Diyi Liu, Edison M. Murairi, and Shuchen Zhu, "Synthesis of single-qutrit circuits from Clifford +R gates", Physical Review A 112 6, 062414 (2025).

[37] Yun‐Jie Wang, Sheng Zhang, Tai‐Ping Sun, Ze‐An Zhao, Xiao‐Fan Xu, Xi‐Ning Zhuang, Huan‐Yu Liu, Cheng Xue, Peng Duan, Yu‐Chun Wu, Zhao‐Yun Chen, and Guo‐Ping Guo, "Hardware‐Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms", Advanced Quantum Technologies 8 5, 2400519 (2025).

[38] Guang Hao Low, Robbie King, Dominic W. Berry, Qiushi Han, A. Eugene DePrince, Alec F. White, Ryan Babbush, Rolando D. Somma, and Nicholas C. Rubin, "Fast Quantum Simulation of Electronic Structure by Spectral Amplification", Physical Review X 15 4, 041016 (2025).

[39] David Gosset, Robin Kothari, and Kewen Wu, "Quantum state preparation with optimal T-count", Quantum 10, 2168 (2026).

[40] Mingfei Yu, Mathias Soeken, and Giovanni De Micheli, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 511 (2025) ISBN:979-8-3315-5736-2.

[41] Stepan Fomichev, Kasra Hejazi, Modjtaba Shokrian Zini, Matthew Kiser, Joana Fraxanet, Pablo Antonio Moreno Casares, Alain Delgado, Joonsuk Huh, Arne-Christian Voigt, Jonathan E. Mueller, and Juan Miguel Arrazola, "Initial State Preparation for Quantum Chemistry on Quantum Computers", PRX Quantum 5 4, 040339 (2024).

[42] Sam McArdle, András Gilyén,, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", Quantum 10, 2058 (2026).

[43] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[44] Craig Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits", arXiv:2505.15917, (2025).

[45] 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 3, 030305 (2021).

[46] YaoChong Li, Ri-Gui Zhou, RuQing Xu, Jia Luo, and WenWen Hu, "A quantum deep convolutional neural network for image recognition", Quantum Science and Technology 5 4, 044003 (2020).

[47] 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).

[48] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, "Quantum computing enhanced computational catalysis", Physical Review Research 3 3, 033055 (2021).

[49] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan, "Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications", Physical Review Letters 129 23, 230504 (2022).

[50] Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, and Hartmut Neven, "Quantum simulation of chemistry with sublinear scaling in basis size", npj Quantum Information 5 1, 92 (2019).

[51] Kianna Wan, Mario Berta, and Earl T. Campbell, "Randomized Quantum Algorithm for Statistical Phase Estimation", Physical Review Letters 129 3, 030503 (2022).

[52] Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush, "Optimization by Decoded Quantum Interferometry", arXiv:2408.08292, (2024).

[53] Bettina Heim, Mathias Soeken, Sarah Marshall, Chris Granade, Martin Roetteler, Alan Geller, Matthias Troyer, and Krysta Svore, "Quantum programming languages", Nature Reviews Physics 2 12, 709 (2020).

[54] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush, "Fault-Tolerant Quantum Simulations of Chemistry in First Quantization", PRX Quantum 2 4, 040332 (2021).

[55] Nicholas P. Bauman, Eric J. Bylaska, Sriram Krishnamoorthy, Guang Hao Low, Nathan Wiebe, Christopher E. Granade, Martin Roetteler, Matthias Troyer, and Karol Kowalski, "Downfolding of many-body Hamiltonians using active-space models: Extension of the sub-system embedding sub-algebras approach to unitary coupled cluster formalisms", Journal of Chemical Physics 151 1, 014107 (2019).

[56] Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee, "Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules", Physical Review Research 4 2, 023019 (2022).

[57] Hector Bombin, Isaac H. Kim, Daniel Litinski, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Sam Roberts, and Terry Rudolph, "Interleaving: Modular architectures for fault-tolerant photonic quantum computing", arXiv:2103.08612, (2021).

[58] 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 42 10, 3301 (2023).

[59] Connor T. Hann, Gideon Lee, S. M. Girvin, and Liang Jiang, "Resilience of Quantum Random Access Memory to Generic Noise", PRX Quantum 2 2, 020311 (2021).

[60] Alain Delgado, Pablo A. M. Casares, Roberto dos Reis, Modjtaba Shokrian Zini, Roberto Campos, Norge Cruz-Hernández, Arne-Christian Voigt, Angus Lowe, Soran Jahangiri, M. A. Martin-Delgado, Jonathan E. Mueller, and Juan Miguel Arrazola, "Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer", Physical Review A 106 3, 032428 (2022).

[61] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan, "Quantum algorithms for quantum chemistry and quantum materials science", arXiv:2001.03685, (2020).

[62] Daniel Litinski and Naomi Nickerson, "Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections", arXiv:2211.15465, (2022).

[63] Christoph Sünderhauf, Earl Campbell, and Joan Camps, "Block-encoding structured matrices for data input in quantum computing", Quantum 8, 1226 (2024).

[64] Jessica Lemieux, Matteo Lostaglio, Sam Pallister, William Pol, Karthik Seetharam, Sukin Sim, and Burak Şahinoğlu, "Quantum sampling algorithms for quantum state preparation and matrix block-encoding", arXiv:2405.11436, (2024).

[65] Annie Y. Wei, Preksha Naik, Aram W. Harrow, and Jesse Thaler, "Quantum algorithms for jet clustering", Physical Review D 101 9, 094015 (2020).

[66] Aleksei V. Ivanov, Christoph Sünderhauf, Nicole Holzmann, Tom Ellaby, Rachel N. Kerber, Glenn Jones, and Joan Camps, "Quantum computation for periodic solids in second quantization", Physical Review Research 5 1, 013200 (2023).

[67] Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca, "Fault-Tolerant Resource Estimation of Quantum Random-Access Memories", IEEE Transactions on Quantum Engineering 1, TQE.2020.2965803 (2020).

[68] Francisco J. R. Ruiz, Tuomas Laakkonen, Johannes Bausch, Matej Balog, Mohammadamin Barekatain, Francisco J. H. Heras, Alexander Novikov, Nathan Fitzpatrick, Bernardino Romera-Paredes, John van de Wetering, Alhussein Fawzi, Konstantinos Meichanetzidis, and Pushmeet Kohli, "Quantum Circuit Optimization with AlphaTensor", arXiv:2402.14396, (2024).

[69] William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O'Brien, Nathan Wiebe, and Ryan Babbush, "Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values", Physical Review Letters 129 24, 240501 (2022).

[70] Koichi Miyamoto, Soichiro Yamazaki, Fumio Uchida, Kotaro Fujisawa, and Naoki Yoshida, "Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos", Physical Review Research 6 1, 013200 (2024).

[71] Craig Gidney, "Windowed quantum arithmetic", arXiv:1905.07682, (2019).

[72] Pei Yuan and Shengyu Zhang, "Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits", Quantum 7, 956 (2023).

[73] Timothy N. Georges, Marius Bothe, Christoph Sünderhauf, Bjorn K. Berntson, Róbert Izsák, and Aleksei V. Ivanov, "Quantum simulations of chemistry in first quantization with any basis set", npj Quantum Information 11 1, 55 (2025).

[74] Guang Hao Low, Nicholas P. Bauman, Christopher E. Granade, Bo Peng, Nathan Wiebe, Eric J. Bylaska, Dave Wecker, Sriram Krishnamoorthy, Martin Roetteler, Karol Kowalski, Matthias Troyer, and Nathan A. Baker, "Q# and NWChem: Tools for Scalable Quantum Chemistry on Quantum Computers", arXiv:1904.01131, (2019).

[75] Nicholas C. Rubin, Dominic W. Berry, Fionn D. Malone, Alec F. White, Tanuj Khattar, A. Eugene DePrince, Sabrina Sicolo, Michael Küehn, Michael Kaicher, Joonho Lee, and Ryan Babbush, "Fault-Tolerant Quantum Simulation of Materials Using Bloch Orbitals", PRX Quantum 4 4, 040303 (2023).

[76] Salonik Resch and Ulya R. Karpuzcu, "Quantum Computing: An Overview Across the System Stack", arXiv:1905.07240, (2019).

[77] Ignacio Loaiza, Aritra Sankar Brahmachari, and Artur F. Izmaylov, "Majorana tensor decomposition: a unifying framework for decompositions of fermionic Hamiltonians to linear combination of unitaries", Quantum Science and Technology 10 3, 035035 (2025).

[78] Junyu Liu and Liang Jiang, "Quantum Data Center: Perspectives", arXiv:2309.06641, (2023).

[79] Cristian L. Cortes, Matthias Loipersberger, Robert M. Parrish, Sam Morley-Short, William Pol, Sukin Sim, Mark Steudtner, Christofer S. Tautermann, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Fault-Tolerant Quantum Algorithm for Symmetry-Adapted Perturbation Theory", PRX Quantum 5 1, 010336 (2024).

[80] 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, TQE.2022 (2022).

[81] Sam McArdle, András Gilyén, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", arXiv:2209.12887, (2022).

[82] Junyu Liu, Connor T. Hann, and Liang Jiang, "Data centers with quantum random access memory and quantum networks", Physical Review A 108 3, 032610 (2023).

[83] 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).

[84] Mark Steudtner, Sam Morley-Short, William Pol, Sukin Sim, Cristian L. Cortes, Matthias Loipersberger, Robert M. Parrish, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Fault-tolerant quantum computation of molecular observables", Quantum 7, 1164 (2023).

[85] Sam McArdle, Alexander M. Dalzell, Aleksander Kubica, and Fernando G. S. L. Brandão, "The Fast for the Curious: How to accelerate fault-tolerant quantum applications", arXiv:2510.26078, (2025).

[86] Jarrod R. McClean, Fabian M. Faulstich, Qinyi Zhu, Bryan O'Gorman, Yiheng Qiu, Steven R. White, Ryan Babbush, and Lin Lin, "Discontinuous Galerkin discretization for quantum simulation of chemistry", New Journal of Physics 22 9, 093015 (2020).

[87] Kun Fang and Zi-Wen Liu, "No-Go Theorems for Quantum Resource Purification: New Approach and Channel Theory", PRX Quantum 3 1, 010337 (2022).

[88] David Gosset, Robin Kothari, and Kewen Wu, "Quantum state preparation with optimal T-count", arXiv:2411.04790, (2024).

[89] Sean Greenaway, William Pol, and Sukin Sim, "A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques", arXiv:2404.01396, (2024).

[90] Felipe H. da Jornada, Matteo Lostaglio, Sam Pallister, Burak Şahinoğlu, and Karthik I. Seetharam, "A comprehensive framework to simulate real-time chemical dynamics on a fault-tolerant quantum computer", arXiv:2504.06348, (2025).

[91] Gideon Lee, Connor T. Hann, Shruti Puri, S. M. Girvin, and Liang Jiang, "Error Suppression for Arbitrary-Size Black Box Quantum Operations", Physical Review Letters 131 19, 190601 (2023).

[92] Pei Yuan, Jonathan Allcock, and Shengyu Zhang, "Does Qubit Connectivity Impact Quantum Circuit Complexity?", IEEE Transactions on Computer Aided Design 43 2, 520 (2024).

[93] Natchapol Patamawisut, Naphan Benchasattabuse, Michal Hajdušek, and Rodney Van Meter, "Quantum Circuit Design for Decoded Quantum Interferometry", arXiv:2504.18334, (2025).

[94] Alexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle, Grant Salton, Quynh T. Nguyen, Aleksander Kubica, and Fernando G. S. L. Brandão, "A distillation-teleportation protocol for fault-tolerant QRAM", arXiv:2505.20265, (2025).

[95] Shifan Xu, Connor T. Hann, Ben Foxman, Steven M. Girvin, and Yongshan Ding, "Systems Architecture for Quantum Random Access Memory", arXiv:2306.03242, (2023).

[96] Modjtaba Shokrian Zini, Alain Delgado, Roberto dos Reis, Pablo Antonio Moreno Casares, Jonathan E. Mueller, Arne-Christian Voigt, and Juan Miguel Arrazola, "Quantum simulation of battery materials using ionic pseudopotentials", Quantum 7, 1049 (2023).

[97] William J. Huggins, Tanuj Khattar, Amanda Xu, Matthew Harrigan, Christopher Kang, Guang Hao Low, Austin Fowler, Nicholas C. Rubin, and Ryan Babbush, "The FLuid Allocation of Surface code Qubits (FLASQ) cost model for early fault-tolerant quantum algorithms", arXiv:2511.08508, (2025).

[98] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).

[99] Kianna Wan, "Exponentially faster implementations of Select(H) for fermionic Hamiltonians", Quantum 5, 380 (2021).

[100] Richard Meister, Simon C. Benjamin, and Earl T. Campbell, "Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries", Quantum 6, 637 (2022).

[101] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).

[102] Pablo A. M. Casares, Roberto Campos, and M. A. Martin-Delgado, "TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry", Quantum 6, 768 (2022).

[103] Hengyun Zhou, Casey Duckering, Chen Zhao, Dolev Bluvstein, Madelyn Cain, Aleksander Kubica, Sheng-Tao Wang, and Mikhail D. Lukin, "Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays", arXiv:2505.15907, (2025).

[104] Aleksei V. Ivanov, Andrew Patterson, Marius Bothe, Christoph Sünderhauf, Bjorn K. Berntson, Jens Jørgen Mortensen, Mikael Kuisma, Earl Campbell, and Róbert Izsák, "Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set", arXiv:2408.03159, (2024).

[105] Alexis Ralli, Gabriel Greene-Diniz, David Muñoz Ramo, and Nathan Fitzpatrick, "Calculating the Single-Particle Many-body Green's Functions via the Quantum Singular Value Transform Algorithm", arXiv:2307.13583, (2023).

[106] Kun Fang and Zi-Wen Liu, "No-go theorems for quantum resource purification II: new approach and channel theory", arXiv:2010.11822, (2020).

[107] Bonan Su, Li Zhou, Yuan Feng, and Mingsheng Ying, "Borrowing Dirty Qubits in Quantum Programs", arXiv:2508.17190, (2025).

[108] Dario Rocca, Cristian L. Cortes, Jérôme F. Gonthier, Pauline J. Ollitrault, Robert M. Parrish, Gian-Luca Anselmetti, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Reducing the Runtime of Fault-Tolerant Quantum Simulations in Chemistry through Symmetry-Compressed Double Factorization", Journal of Chemical Theory and Computation 20 11, 4639 (2024).

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

[110] 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", arXiv:2007.07391, (2020).

[111] Charles Yuan, Agnes Villanyi, and Michael Carbin, "Quantum Control Machine: The Limits of Control Flow in Quantum Programming", arXiv:2304.15000, (2023).

[112] Dario Rocca, Cristian L. Cortes, Jerome Gonthier, Pauline J. Ollitrault, Robert M. Parrish, Gian-Luca Anselmetti, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Reducing the runtime of fault-tolerant quantum simulations in chemistry through symmetry-compressed double factorization", arXiv:2403.03502, (2024).

[113] Roberto Campos, "Hybrid Quantum-Classical Algorithms", arXiv:2406.12371, (2024).

[114] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).

[115] Pablo Antonio Moreno Casares, "Fault-tolerant quantum algorithms", arXiv:2301.08057, (2023).

[116] Saeed Mehraban and Mehrdad Tahmasbi, "Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach", arXiv:2305.10277, (2023).

[117] kos Nagy, Jaime Park, Cindy Zhang, Atithi Acharya, and Alex Khan, "Fixed-Point Grover Adaptive Search for Quadratic Binary Optimization Problems", IEEE Transactions on Quantum Engineering 5, TQE.2024 (2024).

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

[119] Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia, "Implementing Grover oracles for quantum key search on AES and LowMC", arXiv:1910.01700, (2019).

[120] Guang Hao Low, "Halving the cost of quantum multiplexed rotations", arXiv:2110.13439, (2021).

[121] Zhicheng Zhang and Mingsheng Ying, "Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs", arXiv:2408.10054, (2024).

[122] Orlane Zang, Grégoire Barrué, and Tony Quertier, "Benchmarking data encoding methods in Quantum Machine Learning", arXiv:2505.14295, (2025).

[123] Thomas Häner, Vadym Kliuchnikov, Martin Roetteler, and Mathias Soeken, "Space-time optimized table lookup", arXiv:2211.01133, (2022).

[124] Charles Yuan, "Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra", arXiv:2511.01736, (2025).

[125] Israel F. Araujo, Daniel K. Park, Teresa B. Ludermir, Wilson R. Oliveira, Francesco Petruccione, and Adenilton J. da Silva, "Configurable sublinear circuits for quantum state preparation", arXiv:2108.10182, (2021).

[126] Charles Yuan and Michael Carbin, "The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation", arXiv:2311.12772, (2023).

[127] D. V. Denisenko, "Quantum Circuits for S-Box Implementation without Ancilla Qubits", Soviet Journal of Experimental and Theoretical Physics 128 6, 847 (2019).

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

[129] Marco Majland, Rasmus Berg Jensen, Patrick Ettenhuber, Irfansha Shaik, Nikolaj Thomas Zinner, and Ove Christiansen, "Fault-tolerant quantum computations of vibrational wave functions", arXiv:2508.16253, (2025).

[130] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", arXiv:2504.05624, (2025).

[131] Rajiv Krishnakumar, Mathias Soeken, Martin Roetteler, and William J. Zeng, "A Q# Implementation of a Quantum Lookup Table for Quantum Arithmetic Functions", arXiv:2210.11786, (2022).

[132] Alessandro Berti and Francesco Ghisoni, "Efficient Quantum State Preparation with Bucket Brigade QRAM", arXiv:2510.16149, (2025).

[133] Marco Majland, Rasmus Berg Jensen, Patrick Ettenhuber, Irfansha Shaik, Nikolaj Thomas Zinner, and Ove Christiansen, "Fault-Tolerant Quantum Computations of Vibrational Wave Functions", Journal of Chemical Theory and Computation 22 1, 30 (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 15:14:22) and SAO/NASA ADS (last updated successfully 2026-08-13 15:14:23). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.