# Quantum query complexity of symmetric oracle problems

Daniel Copeland1 and Jamie Pommersheim2

1UC San Diego
2Reed College

### 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.

### ► 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] Andrew M. Childs, Shih-Han Hung, and Tongyang Li, "Quantum query complexity with matrix-vector products", arXiv:2102.11349.

The above citations are from SAO/NASA ADS (last updated successfully 2021-08-01 06:04:28). 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 2021-08-01 06:04:26).