{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T09:00:00Z","timestamp":1648803600729},"reference-count":24,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,3,7]],"date-time":"2021-03-07T00:00:00Z","timestamp":1615075200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We study the query complexity of quantum learning problems in which the oracles form a group <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math> 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>-query quantum algorithm in terms of group characters. As an application, we show that <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a9<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> queries are required to identify a random permutation in <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>S<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><\/mml:math>. More generally, suppose <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>H<\/mml:mi><\/mml:math> is a fixed subgroup of the group <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math> of oracles, and given access to an oracle sampled uniformly from <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math>, we want to learn which coset of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>H<\/mml:mi><\/mml:math> 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>-query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> which require <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:math> queries classically and only <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>1<\/mml:mn><\/mml:math> query quantumly.<\/jats:p>","DOI":"10.22331\/q-2021-03-07-403","type":"journal-article","created":{"date-parts":[[2021,3,7]],"date-time":"2021-03-07T13:17:21Z","timestamp":1615123041000},"page":"403","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Quantum query complexity of symmetric oracle problems"],"prefix":"10.22331","volume":"5","author":[{"given":"Daniel","family":"Copeland","sequence":"first","affiliation":[{"name":"UC San Diego"}]},{"given":"Jamie","family":"Pommersheim","sequence":"additional","affiliation":[{"name":"Reed College"}]}],"member":"9598","published-online":{"date-parts":[[2021,3,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133\u2013166, 2014. doi:https:\/\/doi.org\/10.4086\/toc.2014.v010a006.","DOI":"10.4086\/toc.2014.v010a006"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750 \u2013 767, 2002. doi:https:\/\/doi.org\/10.1006\/jcss.2002.1826.","DOI":"10.1006\/jcss.2002.1826"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778\u2013797, 2001. doi:https:\/\/doi.org\/10.1145\/502090.502097.","DOI":"10.1145\/502090.502097"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.26421\/QIC16.1-2-2"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Shalev Ben-David. The Structure of Promises in Quantum Speedups. In TQC 2016, volume 61 of Leibniz International Proceedings in Informatics, pages 7:1\u20137:14, 2016. doi:https:\/\/doi.org\/10.4230\/LIPIcs.TQC.2016.7.","DOI":"10.4230\/LIPIcs.TQC.2016.7"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u20131178, 1999. doi:https:\/\/doi.org\/10.1090\/S0894-0347-99-00307-0.","DOI":"10.1090\/S0894-0347-99-00307-0"},{"key":"6","doi-asserted-by":"publisher","unstructured":"E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411\u20131473, 1997. doi:https:\/\/doi.org\/10.1137\/S0097539796300921.","DOI":"10.1137\/S0097539796300921"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1098\/rspa.2017.0480"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u201316:13, 2016. doi:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.16.","DOI":"10.4230\/LIPIcs.ICALP.2016.16"},{"key":"9","doi-asserted-by":"publisher","unstructured":"J Niel De Beaudrap, Richard Cleve, John Watrous, et al. Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449\u2013461, 2002. doi:https:\/\/doi.org\/10.1007\/s00453-002-0978-1.","DOI":"10.1007\/s00453-002-0978-1"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.4230\/LIPIcs.ITCS.2021.87"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Percy Diaconis. Threads through group theory. In Character Theory of Finite Groups, volume 524 of Contemp. Math, pages 33\u201347. Amer. Math. Soc., Providence, RI. doi:https:\/\/doi.org\/10.1090\/conm\/524\/10343.","DOI":"10.1090\/conm\/524\/10343"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Y. C. Eldar, A. Megretski, and G. C. Verghese. Optimal detection of symmetric mixed quantum states. IEEE Transactions on Information Theory, 50(6):1198\u20131207, 2004. doi:https:\/\/doi.org\/10.1109\/TIT.2004.828070.","DOI":"10.1109\/TIT.2004.828070"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Yonina C. Eldar, Alexandre Megretski, and George C. Verghese. Designing optimal quantum detectors via semidefinite programming. IEEE Trans. Inf. Theor., 49(4):1007\u20131012, 2006. doi:https:\/\/doi.org\/10.1109\/TIT.2003.809510.","DOI":"10.1109\/TIT.2003.809510"},{"key":"14","doi-asserted-by":"publisher","unstructured":"I. Martin Isaacs. Character Theory of Finite Groups. Academic Press, Inc., 1976. doi:https:\/\/doi.org\/10.1090\/chel\/359.","DOI":"10.1090\/chel\/359"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Bases of primitive linear groups. Journal of Algebra, 252(1):95\u2013113, 2002. doi:https:\/\/doi.org\/10.1016\/S0021-8693(02)00001-7.","DOI":"10.1016\/S0021-8693(02)00001-7"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. Nonadaptive quantum query complexity. Inf. Process. Lett., 110(24):1110\u20131113, 2010. doi:https:\/\/doi.org\/10.1016\/j.ipl.2010.09.009.","DOI":"10.1016\/j.ipl.2010.09.009"},{"key":"17","doi-asserted-by":"publisher","unstructured":"David A. Meyer and James Pommersheim. Multi-query quantum sums. In TQC 2011, pages 153\u2013163, New York, NY, USA, 2014. Springer-Verlag New York, Inc. doi:https:\/\/doi.org\/10.1007\/978-3-642-54429-3_10.","DOI":"10.1007\/978-3-642-54429-3_10"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1017\/CBO9780511976667"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-1-4757-6804-6"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-1-4684-9458-7"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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\u2013367, 1998. doi:https:\/\/doi.org\/10.1109\/SFCS.1998.743486.","DOI":"10.1109\/SFCS.1998.743486"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Christof Zalka. Grover's quantum searching algorithm is optimal. Phys. Rev. A, 60:2746\u20132751, Oct 1999. doi:https:\/\/doi.org\/10.1103\/PhysRevA.60.2746.","DOI":"10.1103\/PhysRevA.60.2746"},{"key":"23","unstructured":"Mark Zhandry. Quantum oracle classification - the case of group structure. 2015. URL: http:\/\/arxiv.org\/abs\/1510.08352."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-03-07-403\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,7]],"date-time":"2021-03-07T13:17:26Z","timestamp":1615123046000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-03-07-403\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,7]]},"references-count":24,"URL":"https:\/\/doi.org\/10.22331\/q-2021-03-07-403","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,7]]},"article-number":"403"}}