Short and useful quantum proofs for sublogarithmic-space verifiers

A. C. Cem Say · 2025

Read Short and useful quantum proofs for sublogarithmic-space verifiers by A. C. Cem Say (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08462.txt.

Introduction

Cem Say opens the study of quantum Merlin-Arthur proof systems whose verifiers run in more than constant but less than logarithmic space. The paper from twenty twenty-five recalls that at logarithmic space, such quantum proofs seem to outgun classical proofs and lone quantum machines alike. Smaller bounds had only been probed at constant space, where no advantage surfaced. The in-between regime is his hunting ground.

A family of problems is built whose yes-instances carry short quantum proofs checkable in that slim space. Under standard assumptions, no classical proof system and no stand-alone quantum machine can match the feat in polynomial time. The proofs stay subpolynomial in length, a practical twist past examples. Quantum advantage may live in very small rooms.

Catalog record

CREATORA. C. Cem Say
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08462

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Short and useful quantum proofs for sublogarithmic-space verifiers A. C. Cem Say Abstract Quantum Merlin-Arthur proof systems are believed to be stronger than both their classical counterparts and “stand-alone” quantum computers when Arthur is assumed to operate in Ω ⁡ ( log ⁡ n ) \Omega(\log n) space. No hint of such an advantage over classical computation had emerged from research on smaller space bounds, which had so far concentrated on constant-space verifiers. We initiate the study of quantum Merlin-Arthur systems with space bounds in ω ⁡ ( 1 ) ∩ o ⁡ ( log ⁡ n ) \omega(1)\cap o(\log n) , and exhibit a problem family ℱ \mathcal{F} , whose yes-instances have proofs that are verifiable by polynomial-time quantum Turing machines operating in this regime. We show that no problem in ℱ \mathcal{F} has proofs that can be verified classically or is solvable by a stand-alone quantum machine in polynomial time if standard complexity assumptions hold. Unlike previous examples of small-space verifiers, our protocols require only subpolynomial-length quantum proofs. Keywords: quantum proofs, quantum Turing machines, Merlin-Arthur games, space-bounded quantum computation, sublogarithmic space complexity 1 Introduction The study of quantum advantage aims to distinguish setups where a model of quantum computation outperforms its classical counterpart from those where no such superiority is exhibited. Shor’s celebrated factorization algorithm [ 12 ] provides one hint in this regard, although an unconditional conclusion of quantum advantage would also require a proof that no polynomial-time classical algorithm exists for that problem. Another conjectured difference between the power of classical and quantum machines, formulated as \mathsf{MA}\subsetneq\mathsf{QMA} , pertains to their use as verifiers for purported proofs associated with yes-instances in promise problems. Both \mathsf{MA} and \mathsf{QMA} are generalizations of the complexity class \mathsf{NP} , which is the set of promise problems that have polynomial-time deterministic Turing machines that take an input string w and an additional certificate string c and accept if and only if c constitutes a proof that w is a yes-instance of the problem under consideration. When the verifier in the \mathsf{NP} scenario is substituted by a probabilistic Turing machine, and is allowed to output the wrong verdict with a small probability, one obtains the class \mathsf{MA} , whose name is inspired by the mighty but unreliable Merlin, who prepares the purported proof, and the resource-bounded Arthur, who attempts to verify it. Upgrading the verifier to a quantum machine and allowing the certificate to be a quantum state yields the class \mathsf{QMA} . [ 14 ] As mentioned above, it is believed that \mathsf{QMA} is a proper superset of \mathsf{MA} . The imposition of stricter space bounds on the polynomial-time verifiers in the setups described above has also been considered. Condon [ 1 ] proved that the version of \mathsf{MA} where Arthur is further restricted to use logarithmic space equals \mathsf{NP} . Recently, it was also proven [ 5 ] that the logspace restriction on the (quantum) Arthur leaves the class \mathsf{QMA} unchanged. Note that, when modeling small-space verifiers, one assumes that the ‘‘proof’’, which can be polynomially long, 1 1 1 In both the classical and quantum [ 7 , 4 , 3 ] cases, logarithmic-length proofs are useless for logspace verifiers, i.e., such a verifier can be replaced by a stand-alone algorithm that runs within O(\log n) space and solves the same problem. and therefore cannot be stored in its entirety in the verifier’s memory, is streamed bit by bit (or qubit by qubit) into the verifier from its original storage location. Our focus is on quantum verifiers with sublogarithmic space bounds. Unlike the case with s(n)\in\Omega(\log n) , one is not able to use s(n) -space uniform families of quantum circuits and s(n) -space quantum Turing machines as equivalent models of computation in this even stricter regime, and has to adopt a machine-based model. To date, studies on quantum Merlin-Arthur proof systems in this regard have only considered verifiers using O(1) space. [ 15 , 18 ] No hint of any advantage of two-way quantum finite automata over their classical counterparts has emerged from that work, and all example protocols presented by Villagra and Yamakami ( [ 15 ] , see also Lemma 5.2 in [ 9 ] ) involve languages which also have Merlin-Arthur systems with classical constant-space verifiers. 2 2 2 When one considers interactive proof systems, where Merlin and Arthur can exchange several messages, constant-space quantum verifiers allowed to run for exponential time outperform their classical counterparts. [ 2 , 17 , 11 ] [ 10 ] In this paper, we initiate the study of quantum Merlin-Arthur systems with space bounds in \omega(1)\cap o(\log n) . In Section 2 , we provide the relevant background information for our results and define a quantum Turing machine model suitable for representing verifiers under these extreme space bounds. Section 3 describes our main result, namely, a problem family \mathcal{F} , whose members have yes-instances with proofs that are verifiable by polynomial-time quantum Turing machines operating in \omega(\log\log n)\cap o(\log n) space. We obtain the members of \mathcal{F} by padding \mathsf{QMA} -complete problems in a fashion that is decodable in small space. We show that no problem in \mathcal{F} has proofs that can be verified classically or is solvable by a stand-alone quantum machine in polynomial time if a standard complexity assumption about the difficulty of \mathsf{QMA} -complete problems holds. Unlike previous examples [ 10 , 15 ] of small-space verifiers, our protocols require only subpolynomial-length quantum proofs. Section 4 is a conclusion. 2 Definitions and background Early work on quantum Merlin-Arthur systems [ 6 , 7 ] did not consider the imposition of subpolynomial space bounds on the polynomial-time verifiers. The study of space-bounded quantum computation involves additional difficulties which do not manifest themselves when one merely focuses on time complexity. A case in point is the principle of deferred measurement. [ 8 ] While it has been known for decades that making intermediate measurements during the execution of a quantum algorithm provides no time complexity advantage, this equivalence was only recently proved [ 3 ] for ( \Omega(\log n) ) space complexity. One complication that arises when sublogarithmic space bounds are considered is the breakdown of the equivalence between the uniform circuit family (UCF) and Turing machine (TM) models. Many works on quantum computation with \Omega(\log n) space are presented in terms of the quantum circuit model, which is favored by quantum complexity theorists and physicists. We shall see shortly that this framework is not suitable for modeling computation with smaller space bounds. Before proceeding with the definition of the TM model to be used in this study, we will give an overview of the UCF-based logarithmic-space verification model of Gharibian and Rudolph [ 5 ] . The fact that TM’s are able to simulate UCF’s with no space overhead will enable us to use a scaled-down version of a protocol from [ 5 ] in our main result. Gharibian and Rudolph’s definition [ 5 ] of a proof system with a verifier using s(n) space for inputs of length n stipulates the existence of an s(n) -space uniform family of quantum circuits realizing the verification. When specialized to the case s(n)\in\Theta(\log n) , this requires a deterministic

Read the complete text