2026-08-14T15:28:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9608 2024-03-06T10:44:31Z ddc:004 open_access

Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups Le Gall, François Morimae, Tomoyuki Nishimura, Harumichi Takeuchi, Yuki Quantum computing interactive proofs group-theoretic problems In this paper we consider what can be computed by a user interacting with a potentially malicious server, when the server performs polynomial-time quantum computation but the user can only perform polynomial-time classical (i.e., non-quantum) computation. Understanding the computational power of this model, which corresponds to polynomial-time quantum computation that can be efficiently verified classically, is a well-known open problem in quantum computing. Our result shows that computing the order of a solvable group, which is one of the most general problems for which quantum computing exhibits an exponential speed-up with respect to classical computing, can be realized in this model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik François Le Gall and Tomoyuki Morimae and Harumichi Nishimura and Yuki Takeuchi 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.26 urn:nbn:de:0030-drops-96087 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.26 eng https://creativecommons.org/licenses/by/3.0/legalcode