Quantum query complexity of symmetric oracle problems
1UC San Diego
2Reed College
Published: | 2021-03-07, volume 5, page 403 |
Eprint: | arXiv:1812.09428v3 |
Doi: | https://doi.org/10.22331/q-2021-03-07-403 |
Citation: | Quantum 5, 403 (2021). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We study the query complexity of quantum learning problems in which the oracles form a group $G$ of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a $t$-query quantum algorithm in terms of group characters. As an application, we show that $\Omega(n)$ queries are required to identify a random permutation in $S_n$. More generally, suppose $H$ is a fixed subgroup of the group $G$ of oracles, and given access to an oracle sampled uniformly from $G$, we want to learn which coset of $H$ the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a $t$-query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on $n$ which require $n+1$ queries classically and only $1$ query quantumly.
► BibTeX data
► References
[1] Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133–166, 2014. doi:https://doi.org/10.4086/toc.2014.v010a006.
https://doi.org/10.4086/toc.2014.v010a006
[2] Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750 – 767, 2002. doi:https://doi.org/10.1006/jcss.2002.1826.
https://doi.org/10.1006/jcss.2002.1826
[3] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. doi:https://doi.org/10.1145/502090.502097.
https://doi.org/10.1145/502090.502097
[4] Orest Bucicovschi, Daniel Copeland, David A. Meyer, and James Pommersheim. Single-query quantum algorithms for symmetric problems. Quantum Information and Computation, 2016. doi:https://doi.org/10.26421/QIC16.1-2-2.
https://doi.org/10.26421/QIC16.1-2-2
[5] Shalev Ben-David. The Structure of Promises in Quantum Speedups. In TQC 2016, volume 61 of Leibniz International Proceedings in Informatics, pages 7:1–7:14, 2016. doi:https://doi.org/10.4230/LIPIcs.TQC.2016.7.
https://doi.org/10.4230/LIPIcs.TQC.2016.7
[6] Jinho Baik, Percy Deift, and Kurt Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. Journal of the American Mathematical Society, 12(4):1119–1178, 1999. doi:https://doi.org/10.1090/S0894-0347-99-00307-0.
https://doi.org/10.1090/S0894-0347-99-00307-0
[7] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. doi:https://doi.org/10.1137/S0097539796300921.
https://doi.org/10.1137/S0097539796300921
[8] Jianxin Chen, Andrew M. Childs, and Shih-Han Hung. Quantum algorithm for multivariate polynomial interpolation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474, 2018. doi:https://doi.org/10.1098/rspa.2017.0480.
https://doi.org/10.1098/rspa.2017.0480
[9] Andrew M. Childs, Wim van Dam, Shih-Han Hung, and Igor E. Shparlinski. Optimal Quantum Algorithm for Polynomial Interpolation. In ICALP 2016, volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:13, 2016. doi:https://doi.org/10.4230/LIPIcs.ICALP.2016.16.
https://doi.org/10.4230/LIPIcs.ICALP.2016.16
[10] J Niel De Beaudrap, Richard Cleve, John Watrous, et al. Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449–461, 2002. doi:https://doi.org/10.1007/s00453-002-0978-1.
https://doi.org/10.1007/s00453-002-0978-1
[11] Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals. Complexity measures on symmetric group and beyond. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021. doi:https://doi.org/10.4230/LIPIcs.ITCS.2021.87.
https://doi.org/10.4230/LIPIcs.ITCS.2021.87
[12] Percy Diaconis. Threads through group theory. In Character Theory of Finite Groups, volume 524 of Contemp. Math, pages 33–47. Amer. Math. Soc., Providence, RI. doi:https://doi.org/10.1090/conm/524/10343.
https://doi.org/10.1090/conm/524/10343
[13] Y. C. Eldar, A. Megretski, and G. C. Verghese. Optimal detection of symmetric mixed quantum states. IEEE Transactions on Information Theory, 50(6):1198–1207, 2004. doi:https://doi.org/10.1109/TIT.2004.828070.
https://doi.org/10.1109/TIT.2004.828070
[14] Yonina C. Eldar, Alexandre Megretski, and George C. Verghese. Designing optimal quantum detectors via semidefinite programming. IEEE Trans. Inf. Theor., 49(4):1007–1012, 2006. doi:https://doi.org/10.1109/TIT.2003.809510.
https://doi.org/10.1109/TIT.2003.809510
[15] I. Martin Isaacs. Character Theory of Finite Groups. Academic Press, Inc., 1976. doi:https://doi.org/10.1090/chel/359.
https://doi.org/10.1090/chel/359
[16] Bases of primitive linear groups. Journal of Algebra, 252(1):95–113, 2002. doi:https://doi.org/10.1016/S0021-8693(02)00001-7.
https://doi.org/10.1016/S0021-8693(02)00001-7
[17] Ashley Montanaro. Nonadaptive quantum query complexity. Inf. Process. Lett., 110(24):1110–1113, 2010. doi:https://doi.org/10.1016/j.ipl.2010.09.009.
https://doi.org/10.1016/j.ipl.2010.09.009
[18] David A. Meyer and James Pommersheim. Multi-query quantum sums. In TQC 2011, pages 153–163, New York, NY, USA, 2014. Springer-Verlag New York, Inc. doi:https://doi.org/10.1007/978-3-642-54429-3_10.
https://doi.org/10.1007/978-3-642-54429-3_10
[19] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. doi:https://doi.org/10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[20] Bruce Sagan. The Symmetric Group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag New York, 2001. doi:https://doi.org/10.1007/978-1-4757-6804-6.
https://doi.org/10.1007/978-1-4757-6804-6
[21] J.P. Serre. Linear Representations of Finite Groups. Graduate texts in mathematics. Springer-Verlag, 1996. doi:https://doi.org/10.1007/978-1-4684-9458-7.
https://doi.org/10.1007/978-1-4684-9458-7
[22] Wim van Dam. Quantum oracle interrogation: getting all information for almost half the price. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 362–367, 1998. doi:https://doi.org/10.1109/SFCS.1998.743486.
https://doi.org/10.1109/SFCS.1998.743486
[23] Christof Zalka. Grover's quantum searching algorithm is optimal. Phys. Rev. A, 60:2746–2751, Oct 1999. doi:https://doi.org/10.1103/PhysRevA.60.2746.
https://doi.org/10.1103/PhysRevA.60.2746
[24] Mark Zhandry. Quantum oracle classification - the case of group structure. 2015. URL: http://arxiv.org/abs/1510.08352.
arXiv:1510.08352
Cited by
[1] Sophie Decoppet, "Optimal Quantum Algorithm for Vector Interpolation", arXiv:2212.03939, (2022).
[2] Andrew M. Childs, Shih-Han Hung, and Tongyang Li, "Quantum query complexity with matrix-vector products", arXiv:2102.11349, (2021).
The above citations are from SAO/NASA ADS (last updated successfully 2024-03-28 09:56:54). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2024-03-28 09:56:53).
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.