Lower Bounds for Unitary Property Testing with Proofs and Advice

Jordi Weggemans

doi:10.22331/q-2025-04-18-1717

Lower Bounds for Unitary Property Testing with Proofs and Advice

QuSoft & CWI, Amsterdam, the Netherlands

Published:	2025-04-18, volume 9, page 1717
Editor:	Aleksandrs Belovs
Eprint:	arXiv:2401.07912v3
Doi:	https://doi.org/10.22331/q-2025-04-18-1717
Citation:	Quantum 9, 1717 (2025).

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

Abstract

In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any $\mathsf{C}$-tester with $\mathsf{C} \subseteq \mathsf{QMA}(2)/\mathsf{qpoly}$, showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which $\mathsf{QMA}(2) \not\supset \mathsf{SBQP}$ and $\mathsf{QMA}/\mathsf{qpoly} \not\supset \mathsf{SBQP}$. The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.

Featured image: Geometrical interpretation in the complex plane of the spectrum of some unitary.

Popular summary

In quantum computing, some problems reduce to deciding whether an unknown quantum operation (i.e., a unitary) satisfies a given property. This task is called unitary property testing. In the most basic setting, the main question is how many times an algorithm needs to use the unknown unitary (called queries) to determine the answer. In more powerful models, the algorithm may also receive some form of help, such as quantum proofs or trusted quantum advice.

This paper introduces a new method for proving that, even in the presence of quantum proofs and advice, many unitary property testing problems remain intrinsically hard: they still require a large number of queries. The technique relies on a connection between testing properties of quantum operations and distinguishing between two types of quantum transformations (a problem known as unitary channel discrimination).

Using this framework, we establish strong lower bounds on the query complexity of various quantum problems, including quantum phase estimation, entropy estimation, and the preparation of certain quantum states. In all but one case, our technique yields optimal bounds, often with much simpler proofs than existing approaches. Moreover, these bounds continue to hold even when the algorithm is given unentangled quantum proofs and quantum advice.

These results imply that, at least in a black-box setting, quantum proofs and advice do not help when high precision is required. Finally, as a direct corollary of our main results, we use our bounds to offer new insights into the power of certain quantum complexity classes.

► BibTeX data

@article{Weggemans2025lowerboundsunitary,
  doi = {10.22331/q-2025-04-18-1717},
  url = {https://doi.org/10.22331/q-2025-04-18-1717},
  title = {Lower {B}ounds for {U}nitary {P}roperty {T}esting with {P}roofs and {A}dvice},
  author = {Weggemans, Jordi},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1717},
  month = apr,
  year = {2025}
}

► References

[1] Guoming Wang. Property testing of unitary operators. Phys. Rev. A, 84: 052328, Nov 2011. arXiv: 1110.1133.
https://doi.org/10.1103/PhysRevA.84.052328
arXiv:1110.1133

[2] Adrian She and Henry Yuen. Unitary Property Testing Lower Bounds by Polynomials. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pages 96:1–96:17, 2023. arXiv: 2210.05885.
https://doi.org/10.4230/LIPIcs.ITCS.2023.96
arXiv:2210.05885

[3] Thomas Chen, Shivam Nadimpalli, and Henry Yuen. Testing and Learning Quantum Juntas Nearly Optimally. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163–1185, 2003. arXiv: 2207.05898.
https://doi.org/10.1137/1.9781611977554.ch43
arXiv:2207.05898

[4] Qisheng Wang and Zhicheng Zhang. Quantum lower bounds by sample-to-query lifting, August 2023. arXiv: 2308.01794.
arXiv:2308.01794

[5] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, page 212–219, New York, NY, USA, 1996. ISBN 0897917855. arXiv: quant-ph/9605043.
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043

[6] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. arXiv: quant-ph/9701001.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001

[7] 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, 2007. arXiv: quant-ph/0604056.
https://doi.org/10.4086/toc.2007.v003a007
arXiv:quant-ph/0604056

[8] A. Acín. Statistical Distinguishability between Unitary Operations. Phys. Rev. Lett., 87: 177901, Oct 2001. arXiv: quant-ph/0102064.
https://doi.org/10.1103/PhysRevLett.87.177901
arXiv:quant-ph/0102064

[9] G. Mauro D'Ariano, Paoloplacido Lo Presti, and Matteo G. A. Paris. Using Entanglement Improves the Precision of Quantum Measurements. Phys. Rev. Lett., 87: 270404, Dec 2001. arXiv: quant-ph/0109040.
https://doi.org/10.1103/PhysRevLett.87.270404
arXiv:quant-ph/0109040

[10] Runyao Duan, Yuan Feng, and Mingsheng Ying. Entanglement is Not Necessary for Perfect Discrimination between Unitary Operations. Phys. Rev. Lett., 98: 100503, Mar 2007. arXiv: quant-ph/0601150.
https://doi.org/10.1103/PhysRevLett.98.100503
arXiv:quant-ph/0601150

[11] Mário Ziman and Michal Sedlák. Single-shot discrimination of quantum unitary processes. Journal of Modern Optics, 57 (3): 253–259, 2010. arXiv: 1003.1488.
https://doi.org/10.1080/09500340903349963
arXiv:1003.1488

[12] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.
https://doi.org/10.1017/9781316848142

[13] Murray J Holland and Keith Burnett. Interferometric detection of optical phase shifts at the Heisenberg limit. Physical review letters, 71 (9): 1355, 1993.
https://doi.org/10.1103/PhysRevLett.71.1355

[14] ZY Ou. Complementarity and fundamental limit in precision phase measurement. Physical review letters, 77 (12): 2352, 1996.
https://doi.org/10.1103/PhysRevLett.77.2352

[15] Arvid J. Bessen. Lower bound for quantum phase estimation. Phys. Rev. A, 71: 042313, Apr 2005. arXiv: quant-ph/0412008.
https://doi.org/10.1103/PhysRevA.71.042313
arXiv:quant-ph/0412008

[16] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC '99, page 384–393, 1999. ISBN 1581130678. arXiv: quant-ph/9804066.
https://doi.org/10.1145/301250.301349
arXiv:quant-ph/9804066

[17] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270: 359–371, 2007. arXiv: quant-ph/0508139.
https://doi.org/10.1007/s00220-006-0150-x
arXiv:quant-ph/0508139

[18] Chi-Fang Chen, Michael J Kastoryano, Fernando GSL Brandão, and András Gilyén. Quantum Thermal State Preparation, March 2023a. arXiv: 2303.18224.
arXiv:2303.18224

[19] Nikhil S. Mande and Ronald de Wolf. Tight Bounds for Quantum Phase Estimation and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023), volume 274, pages 81:1–81:16, 2023. ISBN 978-3-95977-295-2. arXiv: 2305.04908.
https://doi.org/10.4230/LIPIcs.ESA.2023.81
arXiv:2305.04908

[20] Hsin-Yuan Huang, Yu Tong, Di Fang, and Yuan Su. Learning many-body Hamiltonians with Heisenberg-limited scaling. Physical Review Letters, 130 (20): 200403, 2023.
https://doi.org/10.1103/PhysRevLett.130.200403

[21] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4: 372, December 2020. ISSN 2521-327X. arXiv:2002.12508.
https://doi.org/10.22331/q-2020-12-14-372
arXiv:2002.12508

[22] Aram W. Harrow and Ashley Montanaro. Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization. J. ACM, 60 (1), February 2013. ISSN 0004-5411. arXiv: 1001.0017.
https://doi.org/10.1145/2432622.2432625
arXiv:1001.0017

[23] Yi-Kai Liu, Matthias Christandl, and Frank Verstraete. Quantum Computational Complexity of the $N$-Representability Problem: QMA Complete. Phys. Rev. Lett., 98: 110503, Mar 2007. arXiv: quant-ph/0609125.
https://doi.org/10.1103/PhysRevLett.98.110503
arXiv:quant-ph/0609125

[24] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. The power of unentanglement. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 223–236, 2008. arXiv: 0804.0802.
https://doi.org/10.4086/toc.2009.v005a001
arXiv:0804.0802

[25] Salman Beigi. $NP$ $vs$ ${QMA}_{log}(2)$. Quantum Information & Computation, 10 (1): 141–151, 2010. arXiv: 0810.5109.
https://doi.org/10.26421/QIC10.1-2-10
arXiv:0810.5109

[26] Hugue Blier and Alain Tapp. All Languages in NP Have Very Short Quantum Proofs. In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 34–37, 2009. arXiv: 0709.0738.
https://doi.org/10.1109/ICQNM.2009.21
arXiv:0709.0738

[27] Alexei Y. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. Electron. Colloquium Comput. Complex., TR96, 1995. arXiv: quant-ph/9511026.
arXiv:quant-ph/9511026
https://api.semanticscholar.org/CorpusID:17023060

[28] Bill Fefferman and Cedric Lin. Quantum Merlin Arthur with exponentially small gap, 2016. arXiv: 1601.01975.
arXiv:1601.01975

[29] Scott Aaronson. QMA/qpoly $\subseteq$ PSPACE/poly: de-Merlinizing quantum protocols. In 21st Annual IEEE Conference on Computational Complexity (CCC'06), pages 13 pp.–273, July 2006. 10.1109/CCC.2006.36. arXiv: quant-ph/0510230.
https://doi.org/10.1109/CCC.2006.36
arXiv:quant-ph/0510230

[30] Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig. Quantum property testing. SIAM Journal on Computing, 37 (5): 1387–1400, 2008. arXiv: quant-ph/0201117.
https://doi.org/10.1137/S0097539704442416
arXiv:quant-ph/0201117

[31] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48 (4): 778–797, July 2001. ISSN 0004-5411. arXiv: quant-ph/9802049.
https://doi.org/10.1145/502090.502097
arXiv:quant-ph/9802049

[32] Andris Ambainis. Quantum Lower Bounds by Quantum Arguments. Journal of Computer and System Sciences, 64 (4): 750–767, 2002. ISSN 0022-0000. arXiv: quant-ph/0002066, Earlier version in STOC'00.
https://doi.org/10.1006/jcss.2002.1826
arXiv:quant-ph/0002066

[33] Samuel Kutin. Quantum Lower Bound for the Collision Problem with Small Range. Theory of Computing, 1 (2): 29–36, 2005. arXiv: quant-ph/0304162.
https://doi.org/10.4086/toc.2005.v001a002
arXiv:quant-ph/0304162

[34] A. Ambainis. Polynomial degree vs. quantum query complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 230–239, 2003. arXiv: quant-ph/0305028.
https://doi.org/10.1109/SFCS.2003.123819
arXiv:quant-ph/0305028

[35] Peter Hoyer, Troy Lee, and Robert Spalek. Negative weights make adversaries stronger. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, page 526–535, 2007. ISBN 9781595936318. arXiv: quant-ph/0611054.
https://doi.org/10.1145/1250790.1250867
arXiv:quant-ph/0611054

[36] Ben W. Reichardt. Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 544–551, 2009. arXiv: 0904.2759.
https://doi.org/10.1109/FOCS.2009.55
arXiv:0904.2759

[37] Aleksandrs Belovs. Variations on quantum adversary, April 2015. arXiv: 1504.06943.
arXiv:1504.06943

[38] Ashley Montanaro and Ronald de Wolf. A Survey of Quantum Property Testing. Theory of Computing, 2016, 10 2013. arXiv: 1310.2035.
https://doi.org/10.4086/toc.gs.2016.007
arXiv:1310.2035

[39] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature communications, 13 (1): 887, 2022. arXiv: 2101.04634.
https://doi.org/10.1038/s41467-021-27922-0
arXiv:2101.04634

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

[41] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC '19, page 193–204, 2019. ISBN 9781450367059. arXiv: 1806.01838.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838

[42] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states, 2024. arXiv: 2404.04599.
arXiv:2404.04599

[43] Michael M Wolf. Mathematical Introduction to Quantum Information Processing, March 2023.

[44] 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, Los Alamitos, CA, USA, nov 2023. arXiv: 2302.14066.
https://doi.org/10.1109/FOCS57990.2023.00028
arXiv:2302.14066

[45] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge University Press, 2012.
https://doi.org/10.1017/CBO9781139020411

[46] Steph Foulds, Viv Kendon, and Tim Spiller. The controlled SWAP test for determining quantum entanglement. Quantum Science and Technology, 6 (3): 035002, 2021.
https://doi.org/10.1088/2058-9565/abe458

[47] Peter Høyer. Arbitrary phases in quantum amplitude amplification. Phys. Rev. A, 62: 052304, Oct 2000. arXiv: quant-ph/0006031.
https://doi.org/10.1103/PhysRevA.62.052304
arXiv:quant-ph/0006031

[48] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum Fingerprinting. Phys. Rev. Lett., 87: 167902, Sep 2001. arXiv: quant-ph/0102001.
https://doi.org/10.1103/PhysRevLett.87.167902
arXiv:quant-ph/0102001

[49] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? In Algorithms and Computation: 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. Proceedings 14, pages 189–198, 2003.
https://doi.org/10.1007/978-3-540-24587-2_21

[50] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002. arXiv: quant-ph/0005055.
https://doi.org/10.1090/conm/305
arXiv:quant-ph/0005055

[51] Guang Hao Low and Isaac L Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical review letters, 118 (1): 010501, 2017.
https://doi.org/10.1103/PhysRevLett.118.010501

[52] 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

[53] Chi-Fang Chen, Michael J Kastoryano, and András Gilyén. An efficient and exact noncommutative quantum Gibbs sampler, November 2023b. arXiv: 2311.09207.
arXiv:2311.09207

[54] Itai Arad, Zeph Landau, Umesh Vazirani, and Thomas Vidick. Rigorous RG algorithms and area laws for low energy eigenstates in 1D. Communications in Mathematical Physics, 356: 65–105, 2017.
https://doi.org/10.1007/s00220-017-2973-z

[55] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman. The importance of the spectral gap in estimating ground-state energies. PRX Quantum, 3 (4): 040327, December 2022. arXiv:2207.10250.
https://doi.org/10.1103/PRXQuantum.3.040327
arXiv:2207.10250

[56] Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM Journal on computing, 4 (4): 431–442, 1975.
https://doi.org/10.1137/0204037

Cited by

[1] Qisheng Wang and Zhicheng Zhang, "Quantum Lower Bounds by Sample-to-Query Lifting", SIAM Journal on Computing 54 5, 1294 (2025).

[2] Fernando Granha Jeronimo, Pei Wu, and Itai Leigh, "The QMA(2) UniverseComplexity, Entanglement, and Optimization", ACM SIGACT News 57 1, 64 (2026).

[3] Qisheng Wang and Zhicheng Zhang, "Time-Efficient Quantum Entropy Estimator via Samplizer", IEEE Transactions on Information Theory 71 12, 9569 (2025).

[4] Qisheng Wang and Zhicheng Zhang, "Quantum Lower Bounds by Sample-to-Query Lifting", arXiv:2308.01794, (2023).

[5] Kean Chen, Qisheng Wang, and Zhicheng Zhang, "Local Test for Unitarily Invariant Properties of Bipartite Quantum States", arXiv:2404.04599, (2024).

[6] Qisheng Wang and Zhicheng Zhang, "Time-Efficient Quantum Entropy Estimator via Samplizer", arXiv:2401.09947, (2024).

[7] Kean Chen, Qisheng Wang, and Zhicheng Zhang, "A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting", arXiv:2512.01971, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 13:56:04) and SAO/NASA ADS (last updated successfully 2026-08-17 13:56:07). 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.