Resource quantification for programming low-depth quantum circuits

Entong He; Yuxiang Yang

doi:10.22331/q-2026-07-20-2166

Resource quantification for programming low-depth quantum circuits

Entong He and Yuxiang Yang

QICI Quantum Information and Computation Initiative, School of Computing and Data Science, The University of Hong Kong, Pokfulam Road, Hong Kong SAR, China

Published:	2026-07-20, volume 10, page 2166
Editor:	Xin Wang
Eprint:	arXiv:2509.09642v2
Doi:	https://doi.org/10.22331/q-2026-07-20-2166
Citation:	Quantum 10, 2166 (2026).

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

Abstract

Noisy intermediate-scale quantum (NISQ) devices pave the way for implementing quantum algorithms that offer quantum advantages over their classical counterparts. Due to the intrinsic noise and decoherence in the physical system, NISQ machines are naturally modeled as large-scale, low-depth quantum circuits. In practice, executing such circuits requires sending program states that encode the relevant instructions to a programmable quantum computer, typically through a cloud service. Existing programming approaches designed for generic unitary transformations are computationally inefficient in the low-depth setting, and therefore remain unsatisfactory. As such, to realize NISQ algorithms, it is crucial to find an efficient way to program low-depth circuits as the number of qubits $N$ increases. Here, we investigate the circuit complexity and the size of quantum memory, known as the program cost, required to program low-depth brickwork circuits. We establish a tight worst-case program cost of $\Theta(N \mathrm{polylog} N)$ for universally programming low-depth brickwork circuits in the large-$N$ regime. Moreover, we analyze the trade-off between the cost of describing the layout of local gates and the cost of programming them to implement the target unitaries via the light-cone argument. Our findings suggest that faithful gate-wise programming is essentially optimal in the low-depth regime.

Featured image: A universal measure-and-operate scheme for programming low-depth quantum circuits that uses quantum memory of almost linear size in the number of qubits. The program state encodes the local gates, which a fixed processor retrieves and faithfully composes to implement the target circuit.

Popular summary

Near-term quantum computers are expected to run wide but low-depth quantum circuits because their qubits are highly vulnerable to noise. When a computation is delegated to a cloud quantum computer, the desired circuit must be encoded into a "program state" as quantum instructions. A fundamental question is how much quantum memory and operations are required to store and execute these instructions.

We study this question for low-depth brickwork circuits, a standard architecture composed of local gates arranged in layers. We show that, in the worst case, the required program memory grows nearly linearly with the number of qubits, up to logarithmic factors, and that this scaling is both necessary and sufficient. We also investigate whether combining local gates into larger operations can reduce the total resources, but find that it generally offers no advantage. Our results therefore indicate that programming a low-depth circuit gate by gate is essentially optimal, providing a resource benchmark for programmable near-term quantum computers.

► BibTeX data

@article{He2026resource,
  doi = {10.22331/q-2026-07-20-2166},
  url = {https://doi.org/10.22331/q-2026-07-20-2166},
  title = {Resource quantification for programming low-depth quantum circuits},
  author = {He, Entong and Yang, Yuxiang},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2166},
  month = jul,
  year = {2026}
}

► References

[1] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[2] Lov K. Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. Page 212–219. STOC '96New York, NY, USA (1996). Association for Computing Machinery.
https://doi.org/10.1145/237814.237866

[3] Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM Journal on Computing 26, 1484–1509 (1997).
https://doi.org/10.1137/s0097539795293172

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

[5] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. ``Noisy intermediate-scale quantum algorithms''. Rev. Mod. Phys. 94, 015004 (2022).
https://doi.org/10.1103/RevModPhys.94.015004

[6] Yunchao Liu. ``Shallow quantum circuits: Algorithms, complexity, and fault tolerance''. PhD thesis. University of California, Berkeley. (2024).

[7] Sergey Bravyi, David Gosset, and Robert König. ``Quantum advantage with shallow circuits''. Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106

[8] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. ``Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Page 515–526. STOC 2019New York, NY, USA (2019). Association for Computing Machinery.
https://doi.org/10.1145/3313276.3316404

[9] Anne Broadbent. ``Delegating private quantum computations''. Canadian Journal of Physics 93, 941–946 (2015).
https://doi.org/10.1139/cjp-2015-0030

[10] Alex Lombardi, Fermi Ma, and John Wright. ``A one-query lower bound for unitary synthesis and breaking quantum cryptography''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 979–990. STOC 2024New York, NY, USA (2024). Association for Computing Machinery.
https://doi.org/10.1145/3618260.3649650

[11] M. A. Nielsen and Isaac L. Chuang. ``Programmable quantum gate arrays''. Physical Review Letters 79, 321–324 (1997).
https://doi.org/10.1103/physrevlett.79.321

[12] Mark Hillery, Vladimír Bužek, and Mário Ziman. ``Probabilistic implementation of universal quantum processors''. Phys. Rev. A 65, 022301 (2002).
https://doi.org/10.1103/PhysRevA.65.022301

[13] D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia. ``Measurement-based quantum computation beyond the one-way model''. Phys. Rev. A 76, 052315 (2007).
https://doi.org/10.1103/PhysRevA.76.052315

[14] Satoshi Ishizaka and Tohya Hiroshima. ``Asymptotic teleportation scheme as a universal programmable quantum processor''. Phys. Rev. Lett. 101, 240501 (2008).
https://doi.org/10.1103/PhysRevLett.101.240501

[15] Aleksander M. Kubicki, Carlos Palazuelos, and David Pérez-García. ``Resource quantification for the no-programing theorem''. Physical Review Letters 122 (2019).
https://doi.org/10.1103/physrevlett.122.080505

[16] Yuxiang Yang, Renato Renner, and Giulio Chiribella. ``Optimal universal programming of unitary gates''. Phys. Rev. Lett. 125, 210501 (2020).
https://doi.org/10.1103/PhysRevLett.125.210501

[17] Martina Gschwendtner, Andreas Bluhm, and Andreas Winter. ``Programmability of covariant quantum channels''. Quantum 5, 488 (2021).
https://doi.org/10.22331/q-2021-06-29-488

[18] Garazi Muguruza and Florian Speelman. ``Port-Based State Preparation and Applications''. Quantum 8, 1573 (2024).
https://doi.org/10.22331/q-2024-12-18-1573

[19] Satoshi Yoshida, Jisho Miyazaki, and Mio Murao. ``Quantum advantage in storage and retrieval of isometry channels'' (2025). arXiv:2507.10784.
https://doi.org/10.1103/fdvq-9m8m
arXiv:2507.10784

[20] Sanjeev Arora and Boaz Barak. ``Computational complexity: A modern approach''. Cambridge University Press. (2009).
https://doi.org/10.1017/cbo9780511804090

[21] Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern. ``Linear growth of quantum circuit complexity''. Nature Physics 18, 528–532 (2022).
https://doi.org/10.1038/s41567-022-01539-6

[22] Daniel Belkin, James Allen, Soumik Ghosh, Christopher Kang, Sophia Lin, James Sud, Frederic T. Chong, Bill Fefferman, and Bryan K. Clark. ``Approximate $t$-designs in generic circuit architectures''. PRX Quantum 5, 040344 (2024).
https://doi.org/10.1103/PRXQuantum.5.040344

[23] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro. ``Learning quantum states and unitaries of bounded gate complexity''. PRX Quantum 5 (2024).
https://doi.org/10.1103/prxquantum.5.040306

[24] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. ``Learning shallow quantum circuits''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1343–1351. STOC 2024New York, NY, USA (2024). Association for Computing Machinery.
https://doi.org/10.1145/3618260.3649722

[25] Yuxiang Yang. ``Compression of quantum shallow-circuit states''. Phys. Rev. Lett. 134 (2025).
https://doi.org/10.1103/physrevlett.134.010603

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

[27] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. ``On the pauli spectrum of $\mathsf{QAC}^0$''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1498–1506. STOC ’24. ACM (2024).
https://doi.org/10.1145/3618260.3649662

[28] Roe Goodman and Nolan R. Wallach. ``Symmetry, representations, and invariants''. Springer New York. (2009).
https://doi.org/10.1007/978-0-387-79852-3

[29] Aram W. Harrow. ``Applications of coherent classical communication and the schur transform to quantum information theory''. PhD thesis. Massachusetts Institute of Technology. (2005).
https://doi.org/10.48550/arXiv.quant-ph/0512255
arXiv:quant-ph/0512255

[30] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. `` Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries ''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 485–492. Los Alamitos, CA, USA (2024). IEEE Computer Society.
https://doi.org/10.1109/FOCS61266.2024.00038

[31] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. ``Exact and approximate unitary 2-designs and their application to fidelity estimation''. Phys. Rev. A 80, 012304 (2009).
https://doi.org/10.1103/PhysRevA.80.012304

[32] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini, and Paolo Perinotti. ``Optimal quantum learning of a unitary transformation''. Phys. Rev. A 81, 032324 (2010).
https://doi.org/10.1103/PhysRevA.81.032324

[33] Joseph Emerson, Robert Alicki, and Karol Zyczkowski. ``Scalable noise estimation with random unitary operators''. Journal of Optics B: Quantum and Semiclassical Optics 7, S347–S352 (2005).
https://doi.org/10.1088/1464-4266/7/10/021

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

[35] Hari Krovi. ``An efficient high dimensional quantum Schur transform''. Quantum 3, 122 (2019).
https://doi.org/10.22331/q-2019-02-14-122

[36] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. ``Quantum state preparation with optimal circuit depth: Implementations and applications''. Phys. Rev. Lett. 129, 230504 (2022).
https://doi.org/10.1103/PhysRevLett.129.230504

[37] Aram W. Harrow and Saeed Mehraban. ``Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates''. Communications in Mathematical Physics 401, 1531–1626 (2023).
https://doi.org/10.1007/s00220-023-04675-z

[38] Jeongwan Haah, Yunchao Liu, and Xinyu Tan. ``Efficient approximate unitary designs from random pauli rotations''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 463–475. (2024).
https://doi.org/10.1109/FOCS61266.2024.00036

[39] Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. ``Incompressibility and spectral gaps of random circuits'' (2024). arXiv:2406.07478.
arXiv:2406.07478

[40] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. ``Random unitaries in extremely low depth''. Science 389, 92–96 (2025).
https://doi.org/10.1126/science.adv8590

[41] G. Chiribella, G. M. D'Ariano, and M. F. Sacchi. ``Optimal estimation of group transformations using entanglement''. Phys. Rev. A 72, 042338 (2005).
https://doi.org/10.1103/PhysRevA.72.042338

[42] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. ``Query-optimal estimation of unitary channels in diamond distance''. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). Pages 363–390. (2023).
https://doi.org/10.1109/FOCS57990.2023.00028

[43] Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov. ``Synthesis of quantum logic circuits''. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference. Page 272–275. ASP-DAC '05New York, NY, USA (2005). Association for Computing Machinery.
https://doi.org/10.1145/1120725.1120847

[44] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. Number 47 in Graduate Studies in Mathematics. American Mathematical Soc. (2002).

[45] Alexander Semenovich Holevo. ``Bounds for the quantity of information transmitted by a quantum communication channel''. Problemy Peredachi Informatsii 9, 3–11 (1973). url: https://www.mathnet.ru/eng/ppi903.
https://www.mathnet.ru/eng/ppi903

[46] Andreas Winter. ``Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distance and energy constraints''. Communications in Mathematical Physics 347, 291–313 (2016).
https://doi.org/10.1007/s00220-016-2609-8

[47] Amitai Regev. ``Asymptotic values for degrees associated with strips of young diagrams''. Advances in Mathematics 41, 115–136 (1981).
https://doi.org/10.1016/0001-8708(81)90012-8

[48] Yuxiang Yang, Giulio Chiribella, and Masahito Hayashi. ``Optimal compression for identically prepared qubit states''. Phys. Rev. Lett. 117, 090502 (2016).
https://doi.org/10.1103/PhysRevLett.117.090502

[49] Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao. ``On the computational power of $\mathsf{QAC}^0$ with barely superlinear ancillae''. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Page 1476–1487. STOC '25New York, NY, USA (2025). Association for Computing Machinery.
https://doi.org/10.1145/3717823.3718189

[50] Alexei Aleksandrov and Vladimir Peller. ``Operator lipschitz functions (english translation)'' (2016). arXiv:1611.01593.
arXiv:1611.01593

[51] Nai-Hui Chia, Daniel Liang, and Fang Song. ``Quantum state and unitary learning implies circuit lower bounds''. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory. Volume 291 of Proceedings of Machine Learning Research, pages 1194–1252. PMLR (2025). url: https://proceedings.mlr.press/v291/chia25a.html.
https://proceedings.mlr.press/v291/chia25a.html

[52] Héctor J. García, Igor L. Markov, and Andrew W. Cross. ``On the geometry of stabilizer states''. Quantum Info. Comput. 14, 683–720 (2014).
https://doi.org/10.26421/QIC14.7-8-9

[53] Iman Marvian. ``Restrictions on realizable unitary operations imposed by symmetry and locality''. Nature Physics 18, 283–289 (2022).
https://doi.org/10.1038/s41567-021-01464-0

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2026-07-21 00:17:00). On SAO/NASA ADS no data on citing works was found (last attempt 2026-07-21 00:17:01).

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.