Unconditional Proofs of Quantumness Between Small-Space Machines

It is hoped that sufficiently advanced quantum computers will be able to solve problems that are impossible for classical computers employing comparable amounts of resources. This brings up interesting questions about how such a claim of “quantum advantage” can be verified by a classical machine: How can a device check the correctness of a claimed solution for a problem that is too difficult for it to solve on its own? Furthermore, even if the “weak” device can verify that the problem has been solved correctly, is this sufficient to conclude that the “strong” device is indeed a quantum computer, rather than a classical one implementing a fast algorithm unknown to the verifying party?

Brakerski et al. [1] define a proof of quantumness as “a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot.” All approaches to providing such protocols listed in [1] depend on unproven assumptions about a particular task being difficult for computational machines of a particular model. For instance, in one such approach, a “strong” computer can factorize a given composite number, the verifier can quickly check that the factors are correct, and then “conclude” that it is faced with a computer that has run an efficient quantum algorithm like [2], based on the belief that polynomial-time factorization is impossible for classical machines. As another example, Mahadev's protocol [3] for a classical computer to interactively verify the result of an efficient quantum computation is based on the assumption that the Learning with Errors problem [4] is intractable for polynomial-time quantum machines, and, of course, can provide a framework for proofs of quantumness only if the conjecture BPP ⊊ BQP is true.

More recently, Zhan [5] and Girish et al. [6] have focused on proofs between logarithmic-space bounded machines. They have shown that, for any language in the class BQL, such a quantum machine can prove its work (on deciding about the membership of the common input string in the language) to a classical logspace verifier by transmitting a “proof string” of polynomial length. Considered as a framework for proofs of quantumness, this approach is also based on the (as yet unproven) assumption that BQL is a proper superset of BPL, the corresponding class for classical logspace machines.

In this paper, we present the first framework for proofs of quantumness where the conclusion of the verifier is not conditional on an unproven presupposition about a weakness of a family of machines, by studying the case where both interacting computers have drastically small (o(log logn)) memory budgets. It is known [7,8] that certain separation problems are impossible for probabilistic Turing machines (PTM) using o(log logn) space, even if they are allowed to employ uncomputable numbers as their transition probabilities. On the other hand, two-way finite automata with quantum and classical states (2QCFA's), which are, essentially, constant-space Turing machines which have been augmented with a fixed-size quantum register, are known [9,10,11,12] to be able to perform some language recognition tasks that are beyond the capabilities of classical small-space machines. We combine these facts with techniques stemming from the study of interactive proof systems with finite-state verifiers [7,13,14,15,16] and quantum finite automata [17,18] to construct setups where a polynomial-time interaction between the two space-bounded automata ends with the verifier accepting with very high probability only if it is faced with a genuinely quantum machine obeying the communication protocol. Note that the memory sizes of presently realizable quantum computers also justify the consideration of extremely small space bounds in this context.

The paper is structured as follows: Section 2 presents the building blocks to be used to construct our framework. The small-space Turing machine models that represent the classical and quantum computers which take part in the tests of quantumness are defined. We allow our classical machines to use the largest realistic set of transition probabilities, namely, efficiently computable reals between 0 and 1, naturally impose the same computability restriction on the transition amplitudes of the quantum machines. ⁽¹⁾ A list of tasks that are known or presumed to be difficult for small-space PTMs, but are solvable by 2QCFA algorithms, is given in Section 2.1. Section 2.2 describes how we pair a classical verifier with a (quantum or classical) “prover” in our protocols and presents a method by which a constant-space prover can convince a similarly bounded verifier about the membership of their common input string in any language recognized by two-way deterministic two-head finite automata possessing a property that we define. To our knowledge, this is the first step in the characterization of the power of interactive proof systems with such severely constrained provers.

We give a formal definition of what we mean by “checking a proof of quantumness” in Section 3. Intuitively, one describes a verifier V which accepts with high probability if it is faced with a genuinely quantum prover P^Q that can convince V that it is able to solve any given instance of a computational problem P, and every classical prover P^C that attempts to convince V is guaranteed to be less successful than P^Q on an infinite set of common input strings W_P^C. Constructing such a verifier therefore requires identifying a problem P that has the following properties:

• P should be solvable for a polynomial-time QTM.

• P should be provably impossible to solve for a PTM within the same time and space bounds.

• The solution of each instance of P should be “provable” by a QTM to a PTM, both operating within the same time and space bounds, through a polynomial-time interaction where only classical messages are exchanged.

As noted above, we are able to identify problems that satisfy all these properties where the common space bound is very small. In Section 4, we present a specific family of such problems and describe a template for proof-of-quantumness protocols for each member of that family.

In Section 5, we give another protocol based on a problem that seems to be beyond the capability of the provers described in Section 4. That verifier, which employs a version of Freivalds' celebrated (exponential-time) probabilistic finite-state algorithm [20] for recognizing a nonregular language, can be considered to be checking a proof of quantumness on the condition that the underlying problem is classically difficult. Section 6 lists several remaining open questions. Appendix A presents a generalization of a theorem by Dwork and Stockmeyer [21] that may provide a starting point for future proof-of-quantumness protocols.

We start by establishing some key strengths and weaknesses of the machine models that underlie the “proof of quantumness” setup to be studied. Section 2.1 presents the “stand-alone” versions of the classical (probabilistic) and quantum machines that will be relevant in our discussion, and lists the quantum advantage results under the considered common space bounds. In Section 2.2, we describe how those stand-alone machines can be put together to form interactive proof systems and present a technique that will be used by the provers to be presented in Section 4.

In the following, we assume that the reader is familiar with the fundamental notions of quantum computation and the theory of computational complexity [22]. Let 𝒞_[0,1] denote the set of efficiently computable numbers (i.e., those which are associated with deterministic Turing machines that can compute them to b-bit precision within time polynomial in [0, 1].

2.1.

Basic Models and Quantum Advantage

The two basic computational models considered in this paper are probabilistic and quantum Turing machines. In both cases, the machine has a read-only input tape. For any input string w, this tape will contain the string ▹ w ◃, where ▹ and ◃ are special endmarker symbols. Details about the work tapes differ among models, as will be seen.

Definition 1

A probabilistic Turing machine (PTM) ⁽²⁾ is a 7-tuple (S_c, Σ, K, δ, c₀, c_acc, c_rej), where

• S_c is the finite set of states,

• Σ is the finite input alphabet, not containing ▹ and ◃,

• K is the finite work alphabet, including the blank symbol ␣,

• δ : (S_c ∖ {c_acc, c_rej}) × (Σ ∪ {▹, ◃}) × K × S_c × K × {−1, 0, 1} × {−1, 0, 1} → 𝒞_{[0, 1]}, such that, for each fixed c, σ, and κ, ∑_{c′, κ′, di, dw} δ(c, σ, κ, c′, κ′, d_i, d_w) = 1, is the transition function,

• c₀ ∈ S_c is the start state, and

• c_acc, c_rej ∈ S_c, such that c_acc ≠ c_rej, are the accept and reject states, respectively.

A PTM has a single read-write work tape, which is initially blank, with the work head positioned on the leftmost cell. The computation of a PTM M on input w ∈ Σ^∗ begins with the input head positioned on the first symbol of the string ▹w◃, and the machine in state c₀. In every computational step, if M is in some state c ∉ {c_acc, c_rej} with the input head scanning some symbol σ at the ith tape position and the work head scanning some symbol κ at the jth tape position, it switches to state c′, sets the scanned work symbol to κ′, and locates the input and work heads at the (i + d_i)th and (j + d_w)th positions respectively with probability δ(c, σ, κ, c′, κ′, d_i, d_w). We assume that δ is defined such that the input head never moves beyond the tape area delimited by the endmarkers. If M is in state c_acc (c_rej), it halts and accepts (rejects).

A PTM is said to run within space s(n) if, on any input of length n, at most s(n) work tape cells are scanned throughout the computation. We are going to focus on machines that run within space bounds that are o (log log n). A computation performed by a machine that runs within O(1) space can also be performed by a machine which does not use its work tape at all and encodes all the workspace in its state set. The definition of this constant-space model, known as the two-way probabilistic finite automaton (2PFA), is easily obtained from Definition 1 by removing the components related to the work tape. A two-way deterministic finite automaton (2DFA) is simply a 2PFA whose transition function is restricted to the range { 0, 1 }.

Our protocols in Sections 4 and 5 will make use of the well-known capability of 2PFA's to implement “alarm clocks” that can be set to any desired polynomial time bound. A detailed proof of the following fact can be found, for example, in [16]:

Fact 1. For any pair of positive integers k_p, t > 0 and desired “error” bound ε_p > 0, there exists a 2PFA with expected runtime in O(n^t+1), such that the probability that this machine halts in fewer than k_pn^t steps is ε_p.

For our quantum Turing machine (QTM) model, we adopt the definition of Watrous [23]. This model is best visualized as a deterministic Turing machine (with a classical work tape) which has been augmented by adding a finite quantum register and a quantum work tape, each cell of which holds a qubit. The randomness in the behavior of a QTM is a result of the operations performed on the quantum part of the machine at intermediate steps. A QTM is said to run within space s(n) if, on any input of length n, at most s(n) cells are scanned on both the classical and quantum work tapes during the computation.

It turns out that all the QTMs that we need in our results in this paper are constant-space machines. As described above, machines obeying this restriction can be modeled in a simpler way by removing the work tapes from the definition. Doing this to the QTMs of [23] yields the well-studied quantum finite automaton model due to Ambainis and Watrous [9], which we describe in detail below. ⁽³⁾ The following definition, which can be viewed as a 2DFA augmented with a quantum register of constant size, is somewhat more involved than Definition 1, because of the way it breaks down each computational step into two stages for evolving the quantum state and the remaining classical part of the machine separately:

Definition 2

A two-way finite automaton with quantum and classical states (2QCFA) is a 9-tuple (S_q, S_c, Σ, δ_q, δ_c, q₀, c₀, c_acc, c_rej), where

• S_q is the finite set of basis states of the quantum part of the machine,

• S_c is the finite set of classical states,

• Σ is the finite input alphabet, not containing ▹ and ◃,

• δ_q is the quantum transition function, which, for any c ∈ (S_c ∖ {c_acc, c_rej}) and σ ∈ (Σ ∪ {◃, ▹}), maps the pair (c, σ) to an action that will be performed on the quantum part of the machine, as will be described below,

• δ_c is the classical transition function, which determines the input head movement direction and resulting classical state associated with the current computational step, as will be described below,

• q₀ ∈ S_q is the initial quantum state,

• c₀ ∈ S_c is the classical start state, and

• c_acc, c_rej ∈ S_c, such that c_acc ≠ c_rej, are the accept and reject states, respectively.

Just like in the classical case, the input string to a 2QCFA is delimited by endmarkers (beyond which the machine does not attempt to move its head) on the read-only tape. At the start of the computation, the input head is located on the left endmarker, the state of the quantum register is described by the vector |q₀〉, and the classical state is c₀. Every computational step begins with the action δ_q(c, σ) determined by the current classical state c and the currently scanned tape symbol σ being performed on the quantum register. Each such action is either a unitary transformation or a projective measurement of the quantum state, resulting in some outcome τ with an associated probability. The second and final stage of the computational step is a classical transition that determines the pair (c′, d) of the resulting classical state and head movement direction of this step: If δ_q(c, σ) was a unitary transformation, this pair is simply δ_c(c, σ), depending again only on c and σ. If, on the other hand, δ_q(c, σ) was a measurement with outcome τ, the pair (c′, d) is δ_c(c, σ, τ), which also depends on that outcome. Computation halts with acceptance (rejection) when the 2QCFA reaches the classical state c_acc (c_rej).

Since we want our classical and quantum machine models to be “comparable” in all respects except the fact that one is classical and the other is quantum, we restrict all entries of all matrices describing the transitions of 2QCFAs to be complex numbers whose real and imaginary parts are efficiently computable. ⁽⁴⁾

Let A, B ⊆ Σ^* with A ∩ B = ∅. We say that a (classical or quantum) machine M separates A and B (with error bound ε) if there exists a number ε<12 \varepsilon < {1 \over 2} such that

• for all w ∈ A, M accepts input w with probability at least 1 − ε, and

• for all w ∈ B, M rejects input w with probability at least 1 − ε.

Equivalently, one says that M solves the promise problem (A, B). We say that M recognizes A if M separates A and the complement of A.

For any given 2PFA M^C recognizing some language L, it is trivial to construct a 2QCFA that recognizes L by mimicking M^C step by step. 2QCFAs are, in fact, strictly more powerful computational machines than 2PFAs. We review the relevant facts below.

Although some nonregular languages like EQab = {aⁿbⁿ | n ≥ 0 } are known [20] to have exponential-time 2PFAs that recognize them, no o(log log n)-space PTM can recognize a nonregular language in polynomial expected time, as proven by Dwork and Stockmeyer [21]. On the other hand, Ambainis and Watrous [9] describe a polynomial-time 2QCFA that recognizes EQab. Naturally, polynomial-time 2QCFAs also exist for infinitely many other languages whose recognition is reducible to determining whether two different symbols appear equally many times in the input string, e.g., EQ = { w | w ∈ { a, b }^∗ and w contains equally many a's and b's} [12] and POWER-EQ={aba7ba7⋅8ba7⋅82⋯ba7⋅8n|n≥0}, {\rm{POWER}} - {\rm{EQ}} = \{{aba}^7{ba}^{7 \cdot 8}b{a^{7 \cdot {8^2}}} \cdots {ba}^{7 \cdot {8^n}}|n \ge 0\}, studied in [10]. More recently, Remscrim [11] has shown that any language corresponding to the word problem of a finitely generated virtually abelian group can be recognized in cubic time by some bounded-error 2QCFA. EQ is one of the “simplest” members of this set of languages. Let BQTISP_∗(t(n), s(n)) denote the class of languages recognizable by QTMs that run in at most t(n) expected time and within at most s(n) space on all inputs of length at most n, so that such a QTM recognizing the corresponding language exists for any desired positive error bound. All languages mentioned in this paragraph are known to be in BQTISP_∗(n^k, 1) for some constant k depending on the specific language.

In their seminal paper, Ambainis and Watrous [9] also gave an exponential-time 2QCFA algorithm for PAL, the language of palindromes on a binary alphabet. This provided another early example of quantum superiority over classical machines, since it is known [7,8] that no sublogarithmic-space PTM can recognize PAL in any amount of time.

A rational 1PFA [25] is a 2PFA whose transition function is restricted to contain only rational numbers in its range, and not to assign positive probabilities to transitions that do not move the head to the right. A language L is said to belong to the class Sℚ= {\rm{S}}_{\mathbb Q}^ = [25,26] if there exists a rational 1PFA that accepts all and only the members of L with probability 12 {1 \over 2} . Sℚ≠ {\rm{S}}_{\mathbb Q}^ \ne is the class of languages whose complements are in Sℚ= {\rm{S}}_{\mathbb Q}^ = .

Using a technique developed in [17], Yakaryılmaz and Say have proven [18] that all languages in Sℚ=∪Sℚ≠ {\rm{S}}_{\mathbb Q}^ = \cup {\rm{S}}_{\mathbb Q}^ \ne can be recognized by 2QCFAs [12]. Combining this result with Remscrim's work on word problems [11], Table 1 lists some other interesting languages known to have 2QCFAs that recognize them in 2^O(n) expected time for inputs of length n. ⁽⁵⁾ For each of those languages, and for any desired small positive value of ε, there exists a 2^kn-time 2QCFA (with a correspondingly large k) recognizing the language with error bound ε.

Table 1.

Language	Description
PAL	{ w ∣ w = wR }
TWIN	{ w#w ∣ w ∈ { a, b }∗ }
MULT	{ x#y#z | x, y, z are natural numbers in binary notation and x ⋅ y = z }
SQUARE	{ aibi2 ∣ i > 0 }
POWER	{ aib2i ∣ i > 0 }
any “polynomial language”	A polynomial language [27] is defined as {a1n1…aknkb1p1(n1,…,nk)…brpr(n1,…,nk)|pi(ni,…,nk)≥0}, \{a_1^{{n_1}} \ldots a_k^{{n_k}}b_1^{{p_1}({n_1}, \ldots,{n_k})} \ldots b_r^{{p_r}({n_1}, \ldots,{n_k})}|{p_i}({n_i}, \ldots,{n_k}) \ge 0\}, , where a1, …, ak, b1, …, br are distinct symbols, and each pi is a polynomial with integer coefficients.
WG	the word problem for G, where G is any finitely generated virtually free group

2.2.

Interactive Proof Systems with Small-Space Provers

An interactive proof system consists of two entities called the verifier and the prover that share a common finite input alphabet Σ and a finite communication alphabet Γ. The verifier definition in our setup will essentially be a version of Definition 1 that has been augmented to enable the machine to communicate with the prover.

Definition 3

A verifier is a 9-tuple (S_silent, S_com, Σ, K, Γ, δ, c₀, c_acc, c_rej), where

• S_silent is the finite set of noncommunicating states,

• S_com is the finite set of communicating states, such that S_silent ∩ S_com = ∅,

• Σ is the finite input alphabet, not containing ▹ and ◃,

• K is the finite work alphabet, including the blank symbol ␣,

• Γ is the finite communication alphabet,

• δ is the transition function, described below,

• c₀ ∈ S_silent is the start state, and

• c_acc, c_rej ∈ S_silent, such that c_acc ≠ c_rej, are the accept and reject states, respectively.

The main difference between this verifier model and the “stand-alone” PTM model of Definition 1 is the communication cell, through which the messages to and from the prover will be conveyed. When a verifier V starts execution, the communication cell contains the blank symbol ␣. The transition function δ is defined in two parts. In any computational step starting with V at some state c ∈ S_silent with its input head scanning some symbol σ at the i th tape position, its work head scanning some symbol κ at the jth tape position, and the communication cell containing the symbol γ, δ(c, σ, κ, γ, c′, κ′, d_i, d_w) is the probability with which V will switch to state c′, write κ′ in the scanned work tape cell, and then locate the input and work heads at the (i + d_i)th and (j + d_w)th tape positions, respectively.

Each communication state c is associated with a symbol γ_s ∈ Γ. Whenever the machine enters a state c ∈ S_com, the symbol γ_s is written in the communication cell. As will be described below, the prover is supposed to respond to this communication with some symbol γ′ in its next computational step. If this response is not received by the time V starts its next step, it rejects immediately. Otherwise, V transitions from state c to state c′, replaces the scanned work tape symbol with κ′, and moves its heads in the directions associated with d_i and d_w, respectively, with probability δ(c, σ, κ, γ′, c′, κ′, d_i, d_w), having received the communication symbol γ′ in response to its message while scanning the input symbol σ and the work tape symbol κ.

Note that both the runtime and the acceptance probability of a verifier reading a particular input string and communicating with a particular prover may depend on the messages of the prover provided as responses during this communication.

In the study of interactive proof systems where computationally limited verifiers are faced with provers of unbounded power, one has no need to commit to a specific machine definition for the role of the prover. In the context of this paper, the prover is known to be a o(log log n)-space machine, and it is the verifier's task to determine whether the prover is indeed quantum (i.e., a QTM augmented with a communication cell) as it claims to be, or just a classical probabilistic Turing machine as the verifier itself. In the following definitions of these two types of provers, we obey the convention [7] that the prover sends a symbol through the communication cell only at the steps in which it detects that a new communication symbol has just been written by the verifier. As mentioned above, the QTM algorithms we will describe require only O(1) space, so our definition of a quantum prover is just a properly augmented version of Definition 2:

Definition 4

A (constant-space) quantum prover is a 9-tuple (S_q, S_c, Σ, Γ, δ_q, δ_silent, δ_com, q₀, c₀), where

• S_q is the finite set of basis states of the quantum part of the machine,

• S_c is the finite set of classical states,

• Σ is the finite input alphabet, not containing ◃ and ▹,

• Γ is the finite communication alphabet,

• δ_q is the quantum transition function, which, for any c ∈ (S_c ∖ { c_acc, c_rej }) and σ ∈ (Σ ∪ {◃,▹}), maps the pair (c, σ) to an action (a unitary transition or a measurement) that will be performed on the quantum part of the machine, exactly as in Definition 2,

• δ_silent is the “silent” classical transition function, which determines the input head movement direction and resulting classical state associated with the current computational step when no new incoming symbol has been detected in the communication cell, as the function δ_c in Definition 2,

• δ_com is the classical transition function to be employed when a new message from the verifier has been detected in the communication cell, as described below,

• q₀ ∈ S_q is the initial quantum state, and

• c₀ ∈ S_c is the classical start state.

Any such quantum prover P^Q has access to a communication cell that it shares with the verifier. Just like the stand-alone 2QCFAs we saw in Section 2.1, P^Q performs each computational step in two stages. In addition to the quantum and classical transition functions δ_q and δ_silent, which serve the same purpose as their counterparts in Definition 2, P^Q also has a second classical transition function δ_com, which is employed instead of δ_silent only at the steps where a new communication symbol written by the verifier is detected in the communication cell. Each such step starting from classical state c and with symbol σ being scanned in the input tape shared by the verifier first performs the quantum transition indicated by δ_q(c, σ) as described in Section 2.1, but continues with a classical transition (that also depends on the symbol γ in the communication cell) from δ_com, rather than δ_silent. In more detail, if δ_q(c, σ) was a unitary transition, δ_com(c, σ, γ) is a triple (c′, d, γ′), specifying the resulting classical state c′ and input head direction d of P^Q, as well as the symbol γ′ that P^Q will write in the communication cell, overwriting its previous content. If δ_q(c, σ) dictated a measurement with outcome τ, δ_com(c, σ, τ, γ) is similarly a triple indicating the new state, head direction, and response of P^Q.

We define a classical prover analogously. Since we will aim to prove that the verifiers to be presented in Sections 4 and 5 reject the “quantumness” claims of any classical prover whose space bound is (a possibly increasing function of n) within o(log log n), we base this model on the general PTM with the work tape (Definition 1).

Definition 5

• A classical prover is a 7-tuple (S_c, Σ, Γ, K, δ_silent, δ_com, c₀), where

• S_c is the finite set of states,

• Σ is the finite input alphabet, not containing ◃ and ▹,

• K is the finite work alphabet, containing the blank symbol ␣,

• Γ is the finite communication alphabet,

• δ_silent : (S_c ∖ { c_acc, c_rej }) × (Σ ∪ {◃,▹}) × K × S_c × K × { −1, 0, 1 } × { −1, 0, 1 } → 𝒞_[0,1], such that, for each fixed c, σ, and κ, Σ_{c′,κ′,di,dw} δ(c, σ, κ, c′, κ′, d_i, d_w) = 1, is the “silent” transition function, as in Definition 1,

• δ_com : (S_c ∖ { c_acc, c_rej }) × (Σ ∪ {◃,▹}) × K × Γ × S_c × K × Γ × { −1, 0, 1 } × { −1, 0, 1 } → 𝒞_[0,1], such that, for each fixed c, σ, κ, and γ, Σ_{c′,κ′,γ′,di,dw} δ(c, σ, κ, γ, c′, κ′, γ′, d_i, d_w) = 1, is the transition function to be employed at steps where a fresh message from the verifier is detected in the communication cell, as described below, and

• c₀ ∈ S_c is the start state.

The difference between Definitions 3 and 5, which both describe 2PFAs augmented with a communication cell, is caused by the need to follow the convention that a prover only “talks” in response to a communication from the corresponding verifier. As in Definition 4, we specify two different transition functions, δ_silent and δ_com: δ_com(c, σ, κ, γ, c′, κ′, γ′, d_i, d_w) is the probability with which the classical prover will switch to state c′, write κ′ on the work tape, write γ′ in the communication cell, and move the input and work tape heads in directions d_i and d_w, respectively, at a step where it has detected a fresh communication symbol γ while it is in state c and its input and work heads are scanning the symbols σ and κ, respectively. δ_silent, which is identical in function to its counterpart in Definition 1, is employed at steps where no “news” has been received from the verifier.

For any verifier V and prover P running on a common input string w, we let Pr_acc(V, P, w) (resp. Pr_rej(V, P, w)) denote the probability that V accepts (resp. rejects) and halts as a result of the interaction. We will also be considering the possibility that V is “tricked” into running forever without reaching a halting state.

In a standard interactive proof system (IPS) as in [28], the prover's aim is to convince the verifier to accept with high probability that their common input string is a member of some language L, and we say that L has an IPS with error bound ɛ if there exists a verifier that succeeds in making use of the communication with the prover to accept every member of L, and avoiding being tricked into looping on or accepting any non-member of L with probability at least 1 − ɛ, for some ε<12 \varepsilon < {1 \over 2} . In the next section, we will show how to modify this setup so that the end result of the dialogue between the verifier and the prover can be interpreted as a verdict about whether the prover is a quantum machine or not. In the remainder of this section, we present a technique that can be used by a small-space prover faced with a similarly bounded verifier in a standard IPS. This technique will be employed by the quantum provers to be described in Section 4.

A two-head two-way deterministic finite automaton (2DFA(2)) [29] can be visualized as a 2DFA with not one, but two heads. Both heads are positioned on the left endmarker at the beginning of the computation. The transition function governs the two heads separately. At any step of the computation, the next move (i.e., the next state and the movement directions of the two heads) is determined by the current internal state and the symbol pair scanned by the two heads. The class of languages that can be recognized by 2DFA(2)s, designated by ℒ(2DFA(2)), is known to contain many interesting nonregular languages. We will concentrate on a subclass associated with a more restricted machine definition.

In the following, we will construct a verifier algorithm for simulating a given 2DFA(2) M on a given input. At each step of the simulation, the verifier, which has only one input head, will receive the symbol which is purportedly scanned by one of the heads of M from the prover. This will give the prover a chance to “lie” about the reading of that head in order to trick the verifier to accept the input string, even if it is not a member of the language recognized by M. We now define a property of heads that will be important in this regard.

Definition 6

The ith head (H_i) of a 2DFA(2) M is said to be supersafe ⁽⁶⁾ if and only if there exists a 2DFA N_i such that the following are true for any input string w:

• 1.

  N_i's head follows a finite trajectory (i.e., a sequence of head position indices) T_w, after which N_i halts, when given the input w.

• 2.

  If a (single-head) verifier simulates M by using its own head to imitate the movements of H_i on the input w and receiving information about the other head from a prover, the trajectory of the verifier's head is guaranteed to be some prefix of T_w (after which the simulation ends by arriving at a halting state of M), regardless of whether the readings of the other head are provided consistently with the input string or are made up arbitrarily at every step by the prover.

Intuitively, the transition function of such a 2DFA(2) renders the supersafe head's trajectory insensitive to the readings of the other head.

The runtime of a 2DFA(2) M with a supersafe head must have a linear upper bound, since the 2DFA N_i corresponding to the supersafe head is guaranteed to halt for all inputs, any 2DFA running on an input of length n can attain O(n) different configurations, and Definition 6 guarantees that M's runtime is not longer than that of N_i.

As an example, consider the following 2DFA(2) for EQ: The first head, which is supersafe, walks over the input from the left endmarker to the right, and then back towards the left. The second head moves one step to the right for every a that the first head scans during its left-to-right phase, and attempts to move one step to the left for every b scanned by the first head in its right-to-left phase. The machine rejects if the second head fails to return to the left endmarker or attempts to move beyond it in that last phase. Otherwise, it accepts.

The class of languages that can be recognized by 2DFA(2)s with at least one supersafe head will be denoted by ℒ(2DFA(2_s)). It is easy to see that many other languages (e.g., EQab, POWER-EQ, PAL, and TWIN) are also in ℒ(2DFA(2_s)). We do not know if ℒ(2DFA(2)) = ℒ(2DFA(2_s)).

Theorem 1

For any ɛ > 0, every language in ℒ(2DFA(2_s)) has an IPS with error bound ɛ comprising of a constantspace (classical or quantum) prover and a constant-space verifier that halts with probability at least 1 − ɛ within expected polynomial time, and may fail to halt with the remaining probability.

Proof

Let M be a 2DFA(2) with a supersafe head H₁ and another head H₂, recognizing language L. In relation to M and H₁, let N₁ be the corresponding 2DFA described in Definition 6.

Consider the constant-space verifier V described in Figure 1. The setting of the values of parameters m and p in that algorithm will be discussed later. The algorithm consists of m rounds. In each round, the prover P that communicates with V is supposed to report the readings of the head of N₁ at each step of N₁'s computation on the input string w, and V randomly decides whether to use this information to simulate M or to check the correctness of P 's messages by simulating N₁. If, in any round, V discovers that P is lying about those readings, or a simulation of M ends in rejection, V rejects. Otherwise, it accepts.

V does not trust P, which may lie about H₁'s readings in attempts to trick V into accepting or even looping forever without reaching a halting state when the input is not in L. V will therefore rely on P 's messages with a very low probability p ∈ (0, 0.5), and validate that P is indeed transmitting N₁'s head readings with the remaining high probability, 1 − p.

Figure 2 depicts an “honest” prover algorithm that leads V to acceptance with probability 1 whenever the input string w is in L: No matter what sequence of random choices is made by V, all rounds will be completed without rejection, since the prover is faithful to N₁, and simulations of M based on its transmissions for the readings of H₁ end in acceptance by M. The runtime of V in this case is polynomially bounded, since the simulations of both N₁ and M will take linear time.

It remains to conclude the proof by showing that no prover algorithm P^∗ can make V fail to reject (i.e., cause it to accept or loop) with probability more than ɛ > 0, where we can tune ɛ to be as small as we desire by setting m and p appropriately, and also that the probability of V halting in polynomial expected time can be tuned similarly.

V rejects any prover which does not provide a sequence of purported head readings of N₁ in response to its requests in Stages SIM-N₁ and SIM-M. At those stages, the symbols that P^∗ provides will either match or not match the actual readings of N₁. In the following analysis, let t_i denote the probability of the event that the symbols provided by P^∗ match the readings of N₁ when V is in its ith round of verification.

If the input w is not a member of L, one of the following four combinations will occur in each round i of V 's processing of P^∗'s transmissions:

• V simulates N₁, and determines that P^∗'s transmissions about the head readings are correct. In this case, V will advance to the next round in O(n) steps. The probability of this event is (1 − p)t_i.

• V simulates N₁, and determines that P^∗'s transmission about the head readings do not match what V sees for itself. In this case, V will reject in O(n) steps. The probability of this event is (1 − p)(1 − t_i).

• V simulates M while P^∗ transmits the correct head readings for N₁. In this case, V will reject in O(n) steps. The probability of this event is pt_i.

• V simulates M while P^∗ transmits fictitious head readings for N₁. In this case, V can reach an incorrect conclusion that M accepts w and pass this round, or it can be fooled into “simulating” a nonexistent computation of M forever. The probability of this event is at most p(1 − t_i).

Based on this, the probability that V will reject, i.e., Pr_rej(V, P^∗, w), is at least f(1), where the function f is defined recursively as follows: f(i)={(1−p)tif(i+1)+(1−p)(1−ti)+ptifor i<m(1−p)(1−tm)+ptmfor i=m f(i) = \left\{{\matrix{{(1 - p){t_i}f(i + 1) + (1 - p)(1 - {t_i}) + p{t_i}} \hfill & {{\rm{for}}\,i < m} \hfill \cr {(1 - p)(1 - {t_m}) + p{t_m}} \hfill & {{\rm{for}}\,i = m} \hfill \cr}} \right.

Consider the following series of observations:

• f(i)|_{ti = 0} = 1 − p.

• f(i)|ti=1={f(i+1)+p(1−f(i+1))for i<mpfor i=m. f(i){|_{{t_i} = 1}} = \left\{{\matrix{{f(i + 1) + p(1 - f(i + 1))} \hfill & {{\rm{for}}\,i < m} \hfill \cr p \hfill & {{\rm{for}}\,i = m.} \hfill \cr}} \right.

• f(i) is linear in terms of t_i, and t_i is between 0 and 1. Thus, f(i) is between the above two extremes. This implies that f(i)≥{min{1−p,f(i+1)+p(1−f(i+1))}for i<mmin{1−p,p}for i=m. f(i) \ge \left\{{\matrix{{\min \{1 - p,f(i + 1) + p(1 - f(i + 1))\}} \hfill & {{\rm{for}}\,i < m} \hfill \cr {\min \{1 - p,p\}} \hfill & {{\rm{for}}\,i = m.} \hfill \cr}} \right.

• Observation 3 implies that if some f(i) is greater than or equal to 1 − p, then so are all f(j) for j < i, and in particular, f(1) ≥ 1 − p.

• Finally, for all p > 0, there exists an m that forces there to exist an f(i) ≥ 1 − p. To prove this by contradiction, assume that there exists a p > 0 such that for all m, f(i) < 1 − p (equivalently, 1 − f(i) > p) holds for all f(i). However, then, for such a p and in conjunction with Observation 3, we get 1−p>f(i)≥f(i+1)+p(1−f(i+1)) 1 - p > f(i) \ge f(i + 1) + p(1 - f(i + 1)) for i < m. Applying this inequality repeatedly, and then using the assumption once again, we get f(1)≥f(m)+∑i=2mp(1−f(i))>f(m)+(m−1)p2. f(1) \ge f(m) + \sum\limits_{i = 2}^m p(1 - f(i)) > f(m) + (m - 1){p^2}. Regardless of what p > 0 is, a large enough m (say, 2⌈1p2⌉+1 2\left\lceil {{1 \over {{p^2}}}} \right\rceil + 1 ) results in f(1) > 1, a contradiction.

We therefore conclude that the error bound ɛ for V failing to reject with P^∗ can be brought arbitrarily close to 0: For any desired value of ɛ, setting p = ɛ and fixing m to an accordingly large value that exists by the argument above guarantees that Pr_rej(V, P^∗, w) ≥ 1 − ɛ.

The probability that V can be tricked to loop is also bounded by ɛ. With the remaining probability, V 's runtime will be bounded by O(n).

Figure 1.

A verifier V for a language recognized by 2DFA(2) M.

Figure 2.

A prover that simulates N₁ on its input and reports its head readings in each round.

We now present a framework where a classical verifier in an interactive proof system can distinguish whether the prover it is communicating with is a quantum machine or not. Although we will see that one can presently obtain “unconditional” conclusions about quantumness for very slowly growing space bounds, our definition also accommodates similar protocols between bigger machines by allowing the verifier and the prover larger space bounds.

In the following, we consider a space-bounded verifier (Definition 3) which halts with high probability within polynomial expected runtime, and which can be paired by any quantum or classical prover operating under the same space bound to form an interactive proof system.

Intuitively, V expects the prover to prove that it can solve a problem instance encoded in their common input string w correctly. As we will see below, one can start the construction of such a protocol by picking the underlying computational problem to be one that is provably impossible for an o(log log n)-space PTM, but feasible for a 2QCFA. This will mean that there exist infinitely many input strings (set W_P^C in Definition 7) for which a particular classical prover P^C claiming to be able to solve the problem will have to “make up” an answer, which will be incorrect, (and whose purported proof will therefore be “caught” as erroneous) by V with a significant probability. On the other hand, the quantum prover employing the correct algorithm to solve the problem is also supposed to prove its result to V. We will note that not all of the problems with quantum advantage listed in Section 2.1 seem to be associated with such “proofs” that can be generated and communicated between machines with so small resource bounds. For the problems which do accommodate such proofs, V will accept the claim (to quantumness) of a genuine quantum prover running the correct algorithm with considerably higher probability than that of any small-space PTM P^C with the same claim when running on strings in W^P_C. ⁽⁷⁾

Let us take a moment to consider the ordering of the quantifiers in Definition 7. At first sight, one may wonder whether we can use the same set of strings to distinguish between the “correct” (quantum) prover (which is supposed to succeed on all members of all such “test sets” anyway) and all classical provers, and move the quantifier for the input strings to the left accordingly. This is, however, impossible for the following reason: We will be presenting many example protocols where, as mentioned above, the prover is supposed to first solve a problem that is difficult for small-space PTMs and then generate and transmit a proof of correctness of the obtained answer. In those protocols, once an answer to the original problem is at hand, this second stage of communicating the proof is an “easy” task (for even a 2PFA) to realize. Therefore, if the test set (say, W) is fixed, then for any one of its finite subsets, say, W′, there exists a classical prover P′ which is “hardwired” to respond to inputs in W′ by communicating the correct answers and their proofs to the verifier. Such a prover would succeed with very high probability on members of W′, and so the success gap required by the inequality at the end of the definition would not be achieved.

We would like Definition 7 to represent a realistic framework for testing some device for quantumness in a reasonable amount of time. This necessitates us to clarify an aspect about the runtimes of the provers appearing in the interactive proof protocols to be described below. In most of the early work on interactive proof systems, the prover was modeled as a magically powerful entity which could compute anything (including uncomputable functions) in a single step. The limitations that later papers [32,33] did impose on the prover are different than ours in an important respect: Condon and Ladner [32] study provers that are restricted to have polynomial-size strategies, but this still means that any actual machine in the role of the prover would need superpolynomial runtime under standard complexity assumptions. Goldwasser et al. [33] do impose a polynomial time bound on the prover, but their model clearly does not require the prover to run simultaneously with the verifier, whose runtime is significantly shorter. In our model, the understanding is that the prover and the verifier start working simultaneously, at which point they access the input tape for the first time, and the process ends when the verifier halts by accepting or rejecting. In our examples, the verifier will be imposing a polynomial time limit on the prover to declare its answer to the problem instance, so the prover will not be able to run an exponential-time algorithm to completion for many inputs. On the other hand, the small-space restriction introduces a complication that verifiers with Ω(log n) memory do not face: Our protocols will allow some malicious provers to fool the corresponding verifier, which is not able to measure the runtime while simultaneously checking a purported proof, to run forever without reaching a verdict, with nonzero probability. This is why Definition 7 requires a gap between the minimum acceptance probability caused by a quantum prover and the maximum probability that any classical prover can trick the verifier either to announce acceptance or to run forever instead of rejecting.

We will use the following common template when constructing verifiers that check proofs of quantumness: One starts with a promise problem P = (P_Yes, P_No) that is impossible for small-space polynomial-time probabilistic machines, but computable by quantum machines within those resource bounds. P should also have the property that each question's correct answer has an interactive proof where both sides are small-space machines. We build a protocol where a verifier first runs a polynomial-time “clock” to give the prover time to compute and announce the answer to the common input string. The prover is then supposed to prove the correctness of this answer to the verifier with high probability in polynomial time. We say that a verifier built according to this template checks proofs of quantumness based on P.

In this section, we will demonstrate a method to convert some of the exponential-time 2QCFA algorithms for the languages in Table 1 to (polynomial-time) tests of quantumness. An important tool to be used in that regard is the following theorem proved by Freivalds and Karpinski [8], building on work by Dwork and Stockmeyer [7].

We note that it is impossible for a PTM running in space o(log log n) to determine whether its input is in this form with the relationship prescribed in Definition 8 between the length of the core and the padding in polynomial time: The set of strings of the form xy, where x ∈ Σ^∗ and y = ★^2|x|−|x| is nonregular, and no such small-space machine can recognize a nonregular language in polynomial expected time [21]. ⁽⁸⁾ (We do not know if this task of checking for an exponential-length padding in the input is also impossible for small-space polynomial-time QTMs. ⁽⁹⁾ )

To exemplify the way we will use Theorem 2, let us consider the languages PAD(PAL) and PAD(PAL), where PAL is the set of palindromes on the alphabet Σ = { a, b }. In the template of Theorem 2, let I be a set containing only even numbers, g(m) = m, h(m) = 2^m, and Wm=Σm2 {W_m} = {\Sigma^{{m \over 2}}} . For every w, w′ ∈ W_m, let the corresponding u be the empty string, and the corresponding v be the string w^R★^2m−m. It follows that no PTM with a space bound in o(log log n) can separate PAD(PAL) and .

PAL is just one of a number of interesting languages that lead to this kind of impossibility result. Call any separation problem (A, B) that matches the pattern specified in Theorem 2 with the functions g and h respectively set to be m ↦ m and m ↦ 2^m (as in the above example) a DS-FK problem. ⁽¹⁰⁾ All DS-FK problems are impossible for o(log log n)-space PTMs. In the following, we note a few more DS-FK problems based on languages we saw in Table 1. λ denotes the empty string.

To see that (PAD(TWIN), ) is a DS-FK problem, set I to be the set of all odd numbers greater than 1, and Wm={a,b}m−12 {W_m} = {\{a,b\}^{{{m - 1} \over 2}}} . For any pair of distinct elements w, w′ ∈ W_m, let u = λ, and v = #w★^2m−m.

To see that (PAD(MULT), ) is a DS-FK problem, set I to be the set of all odd numbers greater than 5, and Wm={1}{0,1}m−52 {W_m} = \{1\} {\{0,1\}^{{{m - 5} \over 2}}} . For any pair of distinct elements w, w′ ∈ W_m, let u = λ, and v = #1#w★^2m−m.

It is easy to see that (PAD(EQ), ) is not a DS-FK problem, by considering the following 2PFA M that performs the separation: On an input of the form xy, where x is the core, M simply runs Freivalds' 2PFA algorithm for recognizing EQ [20] by treating x as the sole input. The resulting algorithm's runtime is exponential in |x|, but only polynomial in the overall input length.

We are now ready to present our first proof-of-quantumness protocol.

Figure 3.

A verifier based on a DS-FK problem (PAD(L), ), where L ∈ ℒ(2DFA(2_s)).

Figure 4.

A quantum prover based on (PAD(L), ), where L ∈ BQTISP_∗(2^kn, s(n)) ∩ ℒ(2DFA(2_s)).

Since PAL and TWIN are known to satisfy all the requirements of Theorem 3, the associated problems (PAD(PAL), ) and (PAD(TWIN), ) are suitable for testing claims to quantumness by small-space machines without relying on unproven assumptions about the impossibility of a particular problem for a specific model of computation.

The verifier template described in the proof of Theorem 3 can be modified to support protocols based on problems with different properties. Consider the language SQUARE, which is described in Table 1. For any error bound ɛ_Q > 0, this language is recognized by a 2QCFA whose expected runtime on all inputs of sufficient length n is at most 2^kn for some k > 0 corresponding to ɛ_Q. It is not known whether SQUARE is recognizable by either a 2DFA(2) or a sublogarithmic-space PTM. Let SUBSQUARE = { aⁱb^j ∣ j < i² }. We will describe a protocol whereby a quantum prover can demonstrate its ability to solve the separation problem (PAD(SQUARE), PAD(SUBSQUARE)) to a classical verifier V, depicted in Figure 5.

Figure 5.

A verifier V based on (PAD(SQUARE), PAD(SUBSQUARE)).

The parameters k, ɛ_p, k_p, c_F, d_F, p, and h_V in the description of V allow us to tune the success gap of the protocol, as will be explained below. On an input string of the form aⁱb^j★^∗, this verifier expects a prover to first announce its claim about the input string's membership in the allotted time, and then to repeatedly transmit segments composed of i symbols. One probabilistic branch of V verifies that each segment (in a sufficiently long prefix of this transmission) is indeed of the required length, while another branch uses this “ruler” provided by the prover to determine whether the block of b's in the input consists of i mini-blocks of length i, i.e., has length i₂. For this purpose, V compares the number of segment separator symbols transmitted by the prover in the time it takes V to scan the segment of b's in the input with the number of a's in the input, using the technique invented by Freivalds [20] to build a 2PFA that recognizes EQab. A detailed analysis will follow the description of the quantum prover below.

The first stage of the quantum prover P^Q in Figure 6 runs the 2QCFA algorithm Q_SQUARE for recognizing SQUARE on the core of the form aⁱb^j in the same fashion as the prover in Figure 4. Since the CLOCK stage of the verifier in Figure 5 is identical with that of Figure 3, the first stage of P^Q will have sufficient time to finish Q_SQUARE and report a correct Yes/No answer with a probability that can be set to be as close to 1 as one desires by choosing an appropriately low-error version of Q_SQUARE, and plugging in the values of k, k_p, and ɛ_p accordingly, by the analysis we presented in the proof of Theorem 3. In the remainder of its execution, the prover responds to the symbol requests from the verifier by sending an infinitely long sequence zⁱ⁻¹#zⁱ⁻¹#zⁱ⁻¹# … made up of segments of length i. Note that the “proof” transmitted by P^Q does not depend on the answer that it announces earlier.

Figure 6.

A quantum prover based on (PAD(SQUARE), PAD(SUBSQUARE)).

In the CHOOSE stage of Figure 5, V will choose to execute the control in the CHECK-RULER stage with probability p. Since P^Q transmits the proper symbol sequence dictated by the protocol, V 's CHECK-RULER stage will accept with probability 1 within expected runtime i2^h_Vi when faced with P^Q. If V chooses to execute the FREIVALDS stage, ⁽¹⁴⁾ V simply runs a modified version of Freivalds' algorithm for EQab, which has been codified to compare the number of a's in the core with the number of #'s transmitted by P^Q while V 's input head is on the b-block of the core. Since P^Q is honest to its mission, it will transmit the same number of #'s during every sweep of the core. As proven by Freivalds [20], one can set the parameters c_F and d_F to guarantee that the FREIVALDS stage arrives at the correct decision about whether the two numbers being compared are equal or not with probability 1 − ɛ_F, for any desired value of ɛ_F > 0. That stage rejects P^Q only if V 's conclusion about the core disagrees with the answer previously sent by P^Q. We have already established that we can make that answer's correctness probability as close to 1 as we wish, and the parameters c_F and d_F can be set to tune the probability of a disagreement with that correct answer to a value below any desired positive bound as long as the correct ruler is transmitted. We conclude that inf{ Pr_acc(V, P^Q, w) ∣ w ∈ W } can be arranged to be arbitrarily close to 1 for an infinite set W containing all padded strings that are sufficiently long.

Note that, if it chooses to execute the FREIVALDS stage, V bases its decision on the assumption that the prover P that it is communicating with will send a proper sequence of segments, each of length i. The runtime of Freivalds' algorithm, which V executes in this case, supplies a bound on the number of symbols that V will request from P. That algorithm's expected runtime is O(m2_r), where m is the length of the string it is working on, r is the number of coins it tosses during a single pass of that string, and the parameters c_F and d_F determine the constant of proportionality “hidden” by the big-O notation [21]. In this case, the promise of the problem guarantees that m ≤ i + i² and r ≤ 2i. We can thefore say that, for sufficiently long inputs, this procedure has expected runtime under 2^k_Fi, for a sufficiently large number k_F that depends on the desired ɛ_F. Consider a parameter K > 1. The probability of the runtime of the FREIVALDS stage exceeding K2^k_Fi is at most 1K {1 \over K} , by Markov's inequality. Since i > 0, 1K {1 \over K} is also an upper bound for the probability that V will request more than iK2^k_Fi symbols from the prover during this stage.

Let us now consider a classical prover P^C interacting with V. Note that V will reject any prover that fails to return a Yes/No answer, or to respond to a symbol request promptly, with probability 1. Assume that P^C has reported a Yes/No answer within the time allotted by the CLOCK stage of V. We will analyze P^C 's chances of being accepted in the cases where it adopts one of the following strategies about which symbols to transmit in response to the verifier's subsequent requests:

• Strategy 1: Transmit a sequence which fails to match the “expected” pattern (zⁱ⁻¹#)⁺ in at least one position among the first iK2^k_Fi symbols

• Strategy 2: Transmit a sequence whose first iK2^k_Fi symbols match the “expected” pattern (zⁱ⁻¹#)⁺

If P^C employs Strategy 1 and V chooses (with probability p) to execute the CHECK-RULER stage, V will reject the prover, unless that stage terminates before P^C attempts to transmit the first “defect” in the pattern. In this stage, V repeatedly sweeps the block of a's in the input from end to end, and decides to halt and accept with probability 2^−h_Vi after each such sweep. The probability that this stage will perform more than K2^k_Fi sweeps (and therefore will request more than iK2^k_Fi symbols from the prover) is (1 − 2^−h_Vi)^K2k_Fi. So the probability p₁ that P^C will be accepted by employing Strategy 1 is at most 1 − p(1 − 2^−h_Vi)^K2k_Fi.

If P^C employs Strategy 2, it will be accepted if one of the following events occur:

• V selects the CHECK-RULER stage, which accepts P^C. The probability of this event is at most p.

• V selects the FREIVALDS stage, which reaches the same conclusion about the core as previously announced by P^C, after requesting more than iK2^kFⁱ symbols from the prover. Since P^C can “lie” after some point during its transmission to direct V to reach a conclusion consistent with its previous claim, an upper bound for the probability of this event is (1−p)(1K) (1 - p)\left({{1 \over K}} \right) .

• V selects the FREIVALDS stage, which reaches the same conclusion about the core as previously announced by P^C, after requesting no more than iK2^kFi symbols from the prover. The probability of this event is not more than (1 − p)p_agree, where we define p_agree as the probability that those two conclusions agree.

Assuming that P^C is unable to separate PAD(SQUARE) and PAD(SUBSQUARE), there will be a set WPC′⊆W W_{{P^C}}^{'} \subseteq W containing infinitely many input strings for which it will send the correct answer with probability at most 12 {1 \over 2} during the CLOCK stage of V. For any such input, p_agree, which is the sum of two terms corresponding to the events where P^C and V agree on the correct and wrong answer, respectively, is at most 12(1−εF)+12(εF)=12, {1 \over 2}(1 - {\varepsilon_F}) + {1 \over 2}({\varepsilon_F}) = {1 \over 2}, where we recall that ɛ_F is the (very small) probability that V comes to the wrong conclusion about the core as a result of running Freivalds' algorithm. Therefore, the probability p₂ that P^C will be accepted when it employs Strategy 2 is at most p+(1−p)(1K)+1−p2 p + (1 - p)\left({{1 \over K}} \right) + {{1 - p} \over 2} for infinitely many inputs.

As one of the two “pure” strategies that we considered must yield the highest acceptance probability possible for P^C, ⁽¹⁵⁾ this probability is bounded by max{1−p(1−2−hVi)K2kFi,p+(1−p)(1K)+1−p2}. \max \left\{{1 - p{{(1 - {2^{- {h_V}i}})}^{K{2^{{k_F}i}}}},p + (1 - p)\left({{1 \over K}} \right) + {{1 - p} \over 2}} \right\}.

One wishes this probability to be as low as possible, so consider setting the value of K to a very large number, forcing p₂ to be below a value that is as near to 1+p2 {{1 + p} \over 2} as one desires. For any given value of K, one can then set h_V to a correspondingly large value that will force p₁ to be as near to 1 − p as desired for all sufficiently long strings that form an infinite subset W_P^C of WPC′ W_{{P^C}}^{'} . ⁽¹⁶⁾ We fix p to the value 13 {1 \over 3} that minimizes max{1−p,1+p2} \max \left\{{1 - p,{{1 + p} \over 2}} \right\} , and conclude that the probability that P^C can be accepted by V can be pulled down to any value above 23 {2 \over 3} , obtaining a success gap inf{Pracc(V,PQ,w)|w∈WPC}−sup{1−Prrej(V,PC,w)|w∈WPC} \inf \{{\Pr_{{\rm{acc}}}}(V,{P^Q},w)|w \in {W_{{P^C}}}\} - \sup \{1 - {\Pr_{{\rm{rej}}}}(V,{P^C},w)|w \in {W_{{P^C}}}\} that can be set to be greater than any desired value Δ<13 \Delta < {1 \over 3} .

Note that V runs in expected polynomial time only on input strings satisfying the promise that the core's length is logarithmic in the length of the input, ⁽¹⁷⁾ and is guaranteed to halt with probability 1, unlike the verifiers of Theorem 3. V can be said to distinguish quantum provers from classical ones only on the condition that no 2PFA can separate PAD(SQUARE) and PAD(SUBSQUARE). If that assumption is not true, a classical prover can achieve the same performance as the 2QFA in Figure 6. Of course, V can also be seen as a framework enabling a party who has invented any fast (classical or quantum) constant-space algorithm for solving the separation problem (PAD(SQUARE), PAD(SUBSQUARE)) to demonstrate this to another party without revealing the source code.

As we noted in Section 2.1, there exist recognition problems which are known to be solvable in polynomial expected time by 2QCFAs and at least exponential expected time by 2PFAs. This proven power difference between classical and quantum models suggests a variant of the protocol described in Theorem 3, where the underlying problem is simply the recognition of such a language. However, neither Dwork and Stockmeyer's result [21] establishing that any small-space PTM recognizing a nonregular language must run in superpolynomial expected time, nor our generalization (in Appendix A) of that theorem to machines which do not necessarily halt with probability 1 is strong enough to guarantee that the resulting verifier will reject every classical prover with higher probability than the genuine quantum prover for that problem. Those theorems do not preclude a classical machine (say, a 2PFA) which recognizes EQ and runs within a polynomial time bound with probability (n − 1)/n, and spends exponential time with probability 1/n for inputs of length n. If such a machine P^C exists, it will be able to perform the recognition task with very high probability within some polynomially large time given by the verifier, and the argument used to demonstrate the success gap in the proof of Theorem 3 will not work for a verifier faced with P^C. This line of thought about the search for more proof-of-quantumness protocols raises the following questions:

• Is there a 2PFA that recognizes a nonregular language and runs within a polynomial time bound with probability 1 − o(1) as a function of the input length?

• Do there exist interactive proof systems (like the ones presented in Theorem 1) for languages other than PAL and TWIN in Table 1?

• Which, if any, languages in Table 1 (in addition to PAL, TWIN, MULT, and “word problems,” which are closely connected to PAL) yield DS-FK problems when one considers separating their padded versions from those of their complements?

• Is ℒ(2DFA(2)) = ℒ(2DFA(2_s))?

In Section 1, we mentioned the recent result [6] that every language in BQL has an IPS through which a quantum logspace prover can prove the membership of a string in that language to a classical logspace verifier. ⁽¹⁸⁾ Although our work can be seen as a step toward a similar framework for the small-space case, the construction in [6] requires space to be at least logarithmic in time, and we conjecture that the answer to the following question is negative:

• Is there a general small-space IPS framework (e.g., for all languages in BQTISP^∗(t(n), s(n)) where t(n) is some polynomial in n and s(n) ∈ o(log log n)) through which a quantum s(n)-space prover can prove the membership of a string in a language that it can recognize to a classical verifier with the same space bound?