# Depth-efficient proofs of quantumness

Zhenning Liu111Email<EMAIL_ADDRESS>ETH Zürich  Alexandru Gheorghiu222Email:
<EMAIL_ADDRESS>ETH Zürich

###### Abstract

A proof of quantumness is a type of challenge-response protocol in which a
classical verifier can efficiently certify the _quantum advantage_ of an
untrusted prover. That is, a quantum prover can correctly answer the
verifier’s challenges and be accepted, while any polynomial-time classical
prover will be rejected with high probability, based on plausible
computational assumptions. To answer the verifier’s challenges, existing
proofs of quantumness typically require the quantum prover to perform a
combination of polynomial-size quantum circuits and measurements.

In this paper, we show that _all_ existing proofs of quantumness can be
modified so that the prover need only perform _constant-depth quantum
circuits_ (and measurements) together with log-depth classical computation. We
thus obtain depth-efficient proofs of quantumness whose soundness can be based
on the same assumptions as existing schemes (factoring, discrete logarithm,
learning with errors or ring learning with errors).

##  1 Introduction

Quantum computation currently occupies the noisy intermediate-scale (NISQ)
regime [Pre18]. This means that existing devices have a relatively small
number of qubits (on the order of 100), perform operations that are subject to
noise and are not able to operate fault-tolerantly. As a result, these devices
are limited to running quantum circuits of small depth. Despite these
limitations, there have been two demonstrations of _quantum computational
advantage_ [AAB+19, ZWD+20]. Both cases involved running quantum circuits
whose results cannot be _efficiently_ reproduced by classical computers, based
on plausible complexity-theoretic assumptions [AA11, HM17, BFNV19]. Indeed,
with the best known classical simulations it takes several days of
supercomputing power to match the results of the quantum devices, which
required only a few minutes to produce [HZN+20].

These milestone results illustrate the impressive capabilities of existing
quantum devices and highlight the potential of quantum computation in the near
future. Yet, one major challenge still remains: how do we know whether the
results from the quantum devices are indeed correct? For the existing
demonstrations of quantum advantage, verification is achieved using various
statistical tests on the output samples from the quantum devices [AAB+19,
BIS+18, ZWD+20]. However, performing these tests either involves an
exponential-time classical computation or there is no formal guarantee that an
efficient classical adversary cannot _spoof_ the results of the test [AG19,
PR21].

The question of whether quantum computations can be verified efficiently by a
classical computer was answered in the affirmative in a breakthrough result of
Mahadev [Mah18]. Specifically, Mahadev gave a protocol that allows a
polynomial-time classical _verifier_ to delegate an arbitrary polynomial-time
quantum computation to a _prover_ and certify the correctness of the prover’s
responses. The verifier sends various challenges to the prover and the
protocol guarantees that only a prover that performed the quantum computation
correctly will succeed in these challenges, with high probability.
Importantly, this protocol works assuming the _learning with errors_ (LWE)
problem is intractable for polynomial-time quantum algorithms [Reg09]. The
intractability assumption allows for the construction of _trapdoor claw-free
functions_ (TCFs), a type of collision-resistant hash function, which form the
basis of Mahadev’s verification protocol [Mah18, BCM+18]. In essence, for the
prover to correctly answer the verifier’s challenges, one of the things it is
required to do is evaluate these functions in superposition. With the
trapdoor, the verifier is able to check whether the prover performed this
evaluation correctly. Additional checks are required for the verifier to
delegate and verify any quantum computation, but the main ingredient is the
_coherent evaluation of TCFs_.

A number of followup results also made use of TCFs in this way, allowing for
the efficient certification of randomness generation [BCM+18], remote quantum
state preparation [GV19, CCKW19, MV21], device-independent cryptography
[MDCAF20], zero-knowledge [VZ20] and others [ACGH20, CCY20, KNY20, HMNY21].
Since all of these protocols require the quantum prover to coherently evaluate
the TCFs, which are polynomial-depth classical circuits, the prover must have
the ability to perform polynomial-depth quantum circuits.

More recent results have improved upon previous constructions by either
reducing the amount of communication between the verifier and the prover
[ACGH20, CCY20], reducing both communication and circuit complexity at the
expense of having stronger computational assumptions [BKVV20] or reducing
circuit complexity and relaxing computational assumptions at the expense of
more interaction [KMCVY21]. The latter two results are known as _proof of
quantumness_ protocols. These are protocols in which the goal isn’t to verify
a specific quantum computation, but to demonstrate that the prover has the
capability of performing classically intractable quantum computations. In
essence, it is an efficient test of quantum advantage — _a quantum device can
pass the verifier’s challenges with high probability, but no polynomial-time
classical algorithm can_. Much like the verification protocol of Mahadev,
these proofs of quantumness require the prover to perform polynomial-depth
quantum computations (to evaluate the TCFs). As such, they are not well suited
for certifying quantum advantage on NISQ devices.

It is thus the case that, on the one hand, we have statistical tests of
quantum advantage that are suitable for NISQ computations but which either
require exponential runtime or do not provide formal guarantees of
verifiability. On the other hand, we have protocols for the verification of
arbitrary quantum computations, based on plausible computational assumptions,
but that are not suitable for NISQ devices, as they require running deep
quantum circuits. Is it possible to bridge the gap between the two approaches?
That is what we aim to do in our work by reducing the depth requirements in
TCF-based proofs of quantumness. Specifically, we show that in all such
protocols, the prover’s evaluation can be performed in _constant quantum
depth_ and logarithmic classical depth. For the purposes of certifying quantum
advantage, this leads to highly depth-efficient proofs of quantumness.

###  1.1 Proofs of quantumness

To explain our approach, we first need to give a more detailed overview of
TCF-based proof of quantumness protocols. As the name suggests, the starting
point is trapdoor claw-free functions. A TCF, denoted as $f$, is a type of
one-way function — a function that can be evaluated efficiently (in polynomial
time) but which is intractable to invert. The function also has an associated
trapdoor which, when known, allows for efficiently inverting $f(x)$, for any
$x$. Finally, “claw-free” means that, without knowledge of the trapdoor, it
should be intractable to find a pair of preimages, $x_{0}$, $x_{1}$, such that
$f(x_{0})=f(x_{1})$. Such a pair is known as a _claw_ 333The function is
assumed to be $2$-to-$1$, so that there are exactly two preimages
corresponding to any given image..

For many of the protocols developed so far, an additional property is required
known as the _adaptive hardcore bit property_ , first introduced in [BCM+18].
Intuitively, this says that for any $x_{0}$ it should be computationally
intractable to find even a single bit of $x_{1}$, whenever
$f(x_{0})=f(x_{1})$. As was shown in [KMCVY21], this property is not required
for a proof of quantumness protocol, provided one adds an additional round of
interaction in the protocol, as will become clear. We will refer to TCFs
having the adaptive hardcore bit property as _strong TCFs_. More formally, for
some $\lambda>0$, known as the _security parameter_ , a strong TCF, $f$, is a
$2$-to-$1$ function which satisfies the following properties:

  1. 1.

Efficient generation. There is a $poly(\lambda)$-time algorithm that can
generate a description of $f$ as well as a trapdoor,
$t\in\\{0,1\\}^{poly(\lambda)}$.

  2. 2.

Efficient evaluation. There is a $poly(\lambda)$-time algorithm for computing
$f(x)$, for any $x\in\\{0,1\\}^{\lambda}$.

  3. 3.

Hard to invert. Any $poly(\lambda)$-time algorithm has _negligible_ 444We say
that a function $\mu(\lambda)$ is negligible if
$\lim_{\lambda\to\infty}\frac{p(\lambda)}{\mu(\lambda)}=0$, for any polynomial
$p(\lambda)$. probability to invert $y=f(x)$, for $x$ chosen uniformly at
random from $\\{0,1\\}^{\lambda}$.

  4. 4.

Trapdoor. There is a $poly(\lambda)$-time algorithm that, given the trapdoor
$t$, can invert $y=f(x)$, for any $x\in\\{0,1\\}^{\lambda}$.

  5. 5.

Claw-free. Any $poly(\lambda)$-time algorithm has negligible probability to
find $(y,x_{0},x_{1})$, such that $y=f(x_{0})=f(x_{1})$, $x_{0}\neq x_{1}$.

  6. 6.

Adaptive hardcore bit. Any $poly(\lambda)$-time algorithm succeeds with
probability negligibly close to $1/2$ in producing a tuple $(y,x_{b},d)$, with
$b\in\\{0,1\\}$, such that

$y=f(x_{0})=f(x_{1}),\quad\quad\quad d\cdot(x_{0}\oplus x_{1})=0.$

Without the requirement of an adaptive hardcore bit, we recover the definition
of an ordinary or regular TCF. Note that all $poly(\lambda)$-time algorithms
mentioned above can be assumed to be classical algorithms.

We now outline the proof of quantumness protocol introduced in [BCM+18]. The
classical verifier fixes a security parameter $\lambda>0$ and generates a
strong TCF, $f$, together with a trapdoor $t$. It then sends $f$ to the
prover. The prover is instructed to create the state

$\frac{1}{2^{\lambda/2}}\sum_{(b,x)\in\\{0,1\\}\times\\{0,1\\}^{\lambda-1}}\ket{b,x}\ket{f(b,x)}$
(1)

and measure the second register, obtaining the result $y$. Note here that the
input to the function was partitioned into the bit $b$ and the string $x$, of
length $\lambda-1$. The string $y$ is sent to the verifier, while the prover
keeps the state in the first register,

$\frac{1}{\sqrt{2}}\left(\ket{0,x_{0}}+\ket{1,x_{1}}\right)$

with $f(0,x_{0})=f(1,x_{1})=y$. The string $y$ essentially _commits_ the
prover to its leftover quantum state.

The verifier will now instruct the prover to measure this state in either the
computational basis, referred to as the _preimage test_ or the Hadamard basis,
referred to as the _equation test_ , and report the result. For the preimage
test, the verifier simply checks whether the reported $(b,x_{b})$ of the
prover satisfies $f(b,x_{b})=y$. For the equation test, the prover will report
$(b^{\prime},d)\in\\{0,1\\}\times\\{0,1\\}^{\lambda-1}$ and the verifier
checks whether

$d\cdot(x_{0}\oplus x_{1})=b^{\prime}.$ (2)

In this case, the verifier has to use the trapdoor to recover both $x_{0}$ and
$x_{1}$ from $y$ in order to compute Equation 2.

It is clear that a quantum device can always succeed in this protocol by
following the steps outlined above. However, the properties of the strong TCF
make it so that no polynomial-time classical algorithm can succeed with high
probability. At a high level, the reason for this is the following. Suppose a
classical polynomial-time algorithm, $\mathcal{A}$, always succeeds in both
the preimage test and the equation test. First, run $\mathcal{A}$ in order to
produce the string $y$. Then, perform the preimage test with $\mathcal{A}$,
resulting in $(b,x_{b})$, such that $f(b,x_{b})=y$. Since $\mathcal{A}$ is a
classical algorithm, it can be _rewound_ to the point immediately after
reporting $y$ and now instructed to perform the equation test. This will
result in the tuple $(b^{\prime},d)$ such that $d\cdot(x_{0}\oplus
x_{1})=b^{\prime}$. Importantly, $f(0,x_{0})=f(1,x_{1})=y$. We therefore have
an efficient classical algorithm that yields both a hardcore bit for a claw as
well as one of the preimages in the claw. As this contradicts the adaptive
hardcore bit property, no such algorithm can exist.

As explained in [KMCVY21, BKVV20, ZNR+21], the above argument can be made
robust so that the success probabilities of any polynomial-time classical
strategy in the two tests satisfy the relation

$p_{pre}+2p_{eq}-2\leq\text{negl}(\lambda)$ (3)

where $p_{pre}$ denotes the success probability in the preimage test, $p_{eq}$
is the success probability in the equation test and $\text{negl}(\lambda)$ is
a negligible function in the security parameter $\lambda$.

The protocol described above crucially relies on the adaptive hardcore bit
property to achieve _soundness_ against classical polynomial-time algorithms.
Thus far, this property has only been shown for TCFs constructed from LWE
[BCM+18].

Is it possible to construct proof of quantumness protocols based on other
computational assumptions than the classical intractability of LWE? Yes, in
fact it is not difficult to see that simple proofs of quantumness can be based
on the classical intractability of _factoring_ or the _discrete logarithm
problem_ (DLP): ask the prover to solve multiple instances of these problems
using Shor’s algorithm [Sho94]. Since their solutions can be classically
verified efficiently and since the problems are assumed to be classically
intractable, this immediately yields a proof of quantumness. The issue with
doing this is that the prover has to run large instances of Shor’s algorithm,
which would require a fault-tolerant quantum computer [GE21]. Instead, as was
show in [KMCVY21], one can construct proofs of quantumness based on factoring
or DLP, in which the prover can implement smaller circuits than those required
for Shor’s algorithm. Such protocols would then be more amenable to
experimental implementation on near-term devices.

Let us briefly outline the approach in [KMCVY21]. The idea is to consider TCFs
that need not satisfy the adaptive hardcore bit property. Such TCFs can be
constructed from more varied computational assumptions than LWE, including
factoring, DLP or the ring-LWE problem [LPR10]. All of these are generally
considered to be _standard computational assumptions_. Having such a TCF, the
protocol then proceeds in the same way as the one outlined above: the verifier
requests that the prover prepare the state in 1, measure the function register
obtaining the string $y$ and then send it to the verifier. The prover will be
left with the state from 1. As before, the verifier will then instruct the
prover to perform either a preimage test or an equation test. The preimage
test is unchanged: the prover is asked to measure the state from 1 in the
computational basis and report back the result.

For the equation test, however, the verifier will first sample a random string
$v\in\\{0,1\\}^{\lambda}$ and send it to the prover. The prover must then
prepare the state

$\frac{1}{\sqrt{2}}\left(\ket{v\cdot x_{0}}\ket{x_{0}}+\ket{v\cdot
x_{1}}\ket{x_{1}}\right)$

The $x$ register is measured in the Hadamard basis, resulting in the string
$d\in\\{0,1\\}^{\lambda-1}$ which is sent to the verifier. Upon receiving $d$,
the verifier chooses a random $\phi\in\\{\pi/4,-\pi/4\\}$ and asks the prover
to measure its remaining qubit in the rotated basis

$\left\\{\begin{array}[]{ll}\cos\left(\frac{\phi}{2}\right)\ket{0}+&\sin\left(\frac{\phi}{2}\right)\ket{1}\\\
\cos\left(\frac{\phi}{2}\right)\ket{1}-&\sin\left(\frac{\phi}{2}\right)\ket{0}\\\
\end{array}\right\\}$

Denoting as $b\in\\{0,1\\}$ the prover’s response, the verifier uses $d$ and
the trapdoor to determine which $b$ is the likely outcome of the measurement
and accepts if that matches the prover’s response.

The last step in the protocol is reminiscent of the honest quantum strategy in
the CHSH game for violating Bell’s inequality [CHSH69]. In fact, much like in
the CHSH game, the success probability of any classical prover in this
protocol is upper bounded by $0.75+negl(\lambda)$, whereas a quantum prover
can succeed with probability $cos^{2}(\pi/8)\approx 0.85$. For this reason,
the authors of [KMCVY21] refer to the protocol as a _computational Bell test_.

The soundness against classical polynomial-time algorithms follows from a
similar rewinding argument to the one outlined for the previous protocol,
which used a strong TCF. The main difference is that in this case the verifier
introduces an additional challenge for the prover, in the form of the string
$v$ and the bit $m$, from the modified equation test. This equation test is
still checking for a hardcore bit of a claw, but unlike the previous protocol,
the hardcore bit is no longer adaptive. Intuitively, this is because the
verifier chooses which hardcore bit to request; a choice encapsulated by $v$
and $m$. For more details, we refer the reader to [KMCVY21].

###  1.2 Our results

In the proofs of quantumness outlined above, the honest quantum prover needs
to coherently evaluate a TCF in order to pass the verifier’s tests. A first
step towards making the protocol depth-efficient would be to make it so that
the prover can evaluate the TCF in constant quantum depth. In fact, all that
is required is for the prover to prepare the state from 1 in constant depth,
since the remaining operations can also be performed in constant depth. Our
main result is a generic construction allowing the prover to prepare the state
in 1, in constant depth, for all existing TCFs.

We start with the observation from [GH20] that the strong TCFs based on LWE
can be evaluated in classical logarithmic depth. In fact this also holds for
the TCFs based on factoring, DLP and ring-LWE from [KMCVY21]. As in [GH20],
one can then construct _randomized encodings_ for these TCFs, which can be
evaluated by constant depth classical circuits. A randomized encoding of some
function, $f$, is another function, denoted $\hat{f}$, which is _information-
theoretically equivalent_ to $f$. In other words, $f(x)$ can be uniquely and
efficiently decoded from $\hat{f}(x,r)$, for any $x$ and for a uniformly
random $r$. In addition, there is an efficient procedure for outputting
$\hat{f}(x,r)$, given only $f(x)$. That is to say that $\hat{f}(x,r)$ contains
no more information about $f(x)$ than $f(x)$ itself. The formal definition of
randomized encodings is given in Subsection 2.3. It was shown in [AIK04] that
all functions computable by log-depth circuits admit randomized encodings that
can be evaluated in constant depth. However, this doesn’t immediately imply
that a quantum prover can coherently evaluate these encodings in constant
depth. The reason is that these circuits will typically use gates of
_unbounded fan-out_. These are gates that can create arbitrarily-many copies
of their output. But the gate set one typically considers for quantum
computation has only gates of bounded fan-out (single-qubit rotations and the
two-qubit $CNOT$, for instance). How then can the prover evaluate the
randomized encoding in constant depth with gates of bounded fan-out?

The key observation is that we do not require the prover to be able to
evaluate $\hat{f}$ coherently on an arbitrary input, merely on _a uniform
superposition over classical inputs_. One of our main results is then the
following:

######  Theorem 1.1 (informal).

There is a strategy consisting of alternating constant depth quantum circuits
and logarithmic-depth classical circuits for preparing the state:

$\sum_{x}\ket{x}\ket{\hat{f}(x)},$ (4)

up to an isometry, for any $\hat{f}$ that can be evaluated by a constant-depth
classical circuit, potentially including unbounded fan-out gates.

To prove this result, we use an idea from the theory of _quantum error-
correction_. It is known that GHZ states cannot be prepared by a fixed
constant-depth quantum circuit [WKST19]. However, if we can interleave short-
depth quantum circuits (and measurements) with classical computation, it is
possible to prepare GHZ states in constant quantum-depth. This is akin to
performing corrections in quantum error correction, based on the results of
syndrome measurements.

In our case, this works as follows. First, prepare a _poor man’s cat state_ in
constant depth, as described in [WKST19]. This is a state of the form

$X(w)\;\frac{\ket{0}^{\otimes n}+\ket{1}^{\otimes n}}{\sqrt{2}}$

where $w$ is a string in $\\{0,1\\}^{n}$ and

$X(w)=X^{w_{1}}\otimes X^{w_{1}}\otimes...\otimes X^{w_{n}},$

with $X$ denoting the Pauli-$X$ qubit flip operation. As explained in
[WKST19], the constant-depth preparation of the poor man’s cat state involves
a measurement of the parities of neighboring qubits. In other words, the
measurement yields the string $z\in\\{0,1\\}^{n-1}$, with $z_{i}=w_{i}\oplus
w_{i+1}$, for $i\in[n-1]$. Using a log-depth classical circuit, this parity
information can be used to determine either $w$ or its binary complement. One
then applies the correction operation $X(w)$ to the poor man’s cat state, thus
yielding the desired GHZ state

$\frac{\ket{0}^{\otimes n}+\ket{1}^{\otimes n}}{\sqrt{2}}.$

Having multiple copies of GHZ states, it is possible to replicate the effect
of unbounded fan-out classical gates on a uniform input. To see why, consider
the following example. Suppose we have a classical AND gate, having fan-out
$n$. On inputs $a,b\in\\{0,1\\}$, it produces the output $c\in\\{0,1\\}^{n}$,
with $c_{i}=a\land b$, for all $i\in[n]$. To perform the same operation with
bounded fan-out gates, it suffices to have $n$ copies of $a$ and $b$. That is,
given $\bar{a},\bar{b}\in\\{0,1\\}^{n}$, with $\bar{a}_{i}=a$,
$\bar{b}_{i}=b$, for all $i\in[n]$, one can compute
$c_{i}=\bar{a}_{i}\land\bar{b}_{i}$ using $n$ parallel AND gates. This is
illustrated in Figure 1.

$c_{1}=a\land b$$c_{2}=a\land b$$\vdots$$c_{i}=a\land b$$\vdots$$c_{n}=a\land
b$AND$a$$b$$\bar{a}_{1}$$\bar{b}_{1}$AND$c_{1}=\bar{a}_{1}\land\bar{b}_{1}$$\bar{a}_{2}$$\bar{b}_{2}$AND$c_{2}=\bar{a}_{2}\land\bar{b}_{2}$$\vdots$$\bar{a}_{i}$$\bar{b}_{i}$$\vdots$AND$c_{i}=\bar{a}_{i}\land\bar{b}_{i}$$\bar{a}_{n}$$\bar{b}_{n}$AND$c_{n}=\bar{a}_{n}\land\bar{b}_{n}$
Figure 1: The left-hand side shows an AND gate with fan-out $n$. The right-
hand side is its bounded fan-out equivalent. Here $\bar{a}_{i}=a$ and
$\bar{b}_{i}=b$. Gates of unbounded fan-out can be implemented with bounded
fan-out provided sufficient copies of the inputs are provided.

In our case, each input qubit to the classical function is of the form
$\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$. Replacing it with $n$ copies is
equivalent to using a GHZ state
$\frac{1}{\sqrt{2}}(\ket{\bar{0}}+\ket{\bar{1}})$, where
$\ket{\bar{0}}=\ket{0}^{\otimes n}$, $\ket{\bar{1}}=\ket{1}^{\otimes n}$. As
mentioned, the prover can prepare GHZ states in constant depth using the
“measure-and-correct” trick. It then follows that the prover can also prepare
the state

$\sum_{x}\ket{\bar{x}}\ket{f(x)}$ (5)

where each bit of $x$ is encoded as a GHZ state having the same number of
qubits as the number of input copies required to evaluate $f$ with bounded
fan-out gates.

With the ability to prepare the state from 1 (or one equivalent to it, such as
the one from 5) in constant quantum depth, the honest prover can then proceed
to perform the rest of the steps in the proof of quantumness protocols
outlined above. It will measure the image register and report the result to
the verifier. The remaining operations can also be performed in constant
depth. For the preimage test, the prover simply measures the $x$ register in
the computational basis and reports the result. For the equation test, the
prover needs to first apply a layer of Hadamard gates to the $x$ register
before measuring it in the computational basis. Lastly, for the Bell-type
measurement required in the protocol of [KMCVY21], a slightly more involved
procedure is used to perform the measurement in constant depth. All of these
steps are described in detail in Subsection 3.1.

While we have outlined a procedure for the prover to perform its operations in
constant quantum depth, using a randomized encoding of a TCF, it is not
immediately clear if we need to also modify the verifier’s operations. Indeed,
one question that is raised by this approach is whether a randomized encoding
of a TCF preserves all the properties of a TCF. If, for instance, the trapdoor
property is not preserved, the verifier would be unable to check the prover’s
responses in the equation test. Our second result resolves this issue:

######  Theorem 1.2 (informal).

A randomized encoding of a (strong) TCF is a (strong) TCF.

This theorem implies that substituting the TCFs used in proofs of quantumness
with randomized encodings will not affect the soundness of those protocols.
The proof can be found in Subsection 3.2. A similar result was derived in
[AIK04], where the authors show that randomized encodings of cryptographic
hash functions are also cryptographic hash functions. A (strong) TCF is
different, however555A TCF has exactly two collisions for each image, it has a
trapdoor and strong TCFs additionally have the adaptive hardcore bit property.
None of these properties are satisfied by generic cryptographic hash
functions.. To prove this result, first note that most of the TCF properties
follow almost immediately from the definition of a randomized encoding. The
more challenging parts concern the existence of a trapdoor and the adaptive
hardcore bit property. To show these, we require that the randomized encoding
satisfies a property known as _randomness reconstruction_ [AIK04]. This states
that whenever there is an efficient procedure to invert the original function,
$f$, there should also be an efficient procedure for inverting $\hat{f}$. In
particular, this means that given $\hat{f}(x,r)$ it is possible to recover
both the input $x$ and the randomness $r$. In [AIK04], it’s mentioned that the
randomized encodings used to “compress” functions to constant depth do satisfy
the randomness reconstruction property, but no proof is given. We provide a
proof in Appendix B.

With the two results of Theorems 1.1 and 1.2, we have that any proof of
quantumness using a log-depth computable TCF can be compiled to constant
quantum depth for the prover. In Subection 3.3 we give a detailed account of
the resources required for the prover to perform this evaluation. All of the
results are presented in Section 3, while in Section 2 we provide the
necessary preliminaries.

###  1.3 Related work

One of the first computational tests of quantum advantage was proposed in
[SB09], for certifying that a quantum prover can perform _instantaneous
quantum polynomial-time computations_ (IQP). However, that test was based on a
non-standard hardness assumption and it was later shown that there is an
efficient classical algorithm which passes the test [KM19].

The first proof of quantumness based on LWE originated with the works of
Mahadev [Mah18] and Brakerski et al. [BCM+18]. The latter is the proof of
quantumness based on a strong TCF outlined in the introduction. A subsequent
work achieved a non-interactive version of this protocol in the _quantum
random-oracle model_ [BKVV20]. Notably, in that protocol the adaptive hardcore
bit property is not required, however the protocol does make use of a hash
function (in addition to the TCF) modeled as a random oracle.

The second proof of quantumness we outlined, based on regular TCFs, was
introduced in [KMCVY21]. There the authors achieve more efficient proofs of
quantumness by removing the requirement of the adaptive hardcore bit and using
TCFs having a lower circuit complexity compared to the ones based on LWE.
However, as mentioned, the cost of doing this is introducing additional rounds
of interaction between the verifier and the prover (in the form of the Bell-
like measurement of the equation test).

Lastly, we mention the independent work of Le Galle and Hirahara that appeared
before ours and which also gives a constant-depth proof of quantumness [HG21].
Similar to our work, they also considered one of the existing proofs of
quantumness and made it so that the prover could perform its operations in
constant quantum depth and using log-depth classical computations. In their
case, they use a technique inspired from measurement-based quantum computing
to have the prover perform the coherent evaluation of the strong TCF based on
LWE.

###  1.4 Discussion and open problems

We’ve shown how existing proof of quantumness protocols can be made to work
with a prover that performs constant-depth quantum computations and log-depth
classical computations. Thus, all protocols based on TCFs can be compiled to
constant-depth versions using randomized encodings and preparations of GHZ
states.

One potential objection to our result is the practicality of this
construction. The prover must not only run constant-depth quantum circuits,
but it must do so based on the outcomes of previous measurements or based on
instructions from the verifier. This is similar to syndrome measurements and
corrections in quantum error-correcting codes and so it might seem as if the
prover must have the capability of doing fault-tolerant quantum computations.
In fact this is not the case. For the protocol based on strong TCFs the number
of quantum-classical _interleavings_ — that is, the number of alternations
between performing a constant depth quantum circuit followed by a log-depth
classical circuit — is exactly three. The first is required for the
preparation of GHZ states. In this case, the prover simply needs to apply $X$
corrections conditioned on the outcomes of certain parity measurements. The
prover then evaluates the randomized-encoded TCF and measures one of its
registers, sending that result to the verifier. Conditioned on its response it
either measures the remaining state in the computational basis or in the
Hadamard basis. The prover, therefore, needs to perform only a very restricted
type of conditional operations ($X$ corrections and Hadamard gates) and is
only required to do this three times. Furthermore, the protocol is robust and
some degree of noise is acceptable, provided the Inequality 3 is violated. The
protocol based on regular TCFs requires two additional quantum-classical
interleavings, for a total of five. This is due to the Bell-like measurement
of that protocol. In both cases, only a small number of quantum-classical
interleavings are required, unlike in a fully fault-tolerant computation where
many such interleavings would be required [FMMC12].

It would, of course, be desirable to have a single-round proof of quantumness
with a constant-depth prover. In other words, a protocol in which the prover
has to run a single constant-depth quantum circuit and the verifier is able to
efficiently certify that the prover is indeed quantum. Such a result would
yield a weak separation between polynomial-time classical computation and
constant-depth quantum computation. Basing such a separation on just the
classical hardness of LWE seems unlikely666See the first paragraph of the “Our
results” subsection in [BKVV20].. Basing it on the classical intractability of
factoring or DLP seems more realistic, as those assumptions already yields a
separation between polynomial-time classical computation and logarithmic-depth
quantum computation [CW00]. However, it is unclear how to adapt the existing
protocols which rely on this commit-and-test approach that requires at least
two rounds of interaction. We leave answering this question as an interesting
open problem.

Finally, the computational resources required to implement our constant-depth
proofs of quantumness are likely not optimal. In particular, as outlined in
Subsection 3.3, the resulting quantum circuits can be prohibitively wide to be
implemented on existing NISQ devices. We also leave as an open problem to
optimize this construction so as to make these protocols better suited for use
on near-term devices.

## Acknowledgements

AG is supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH
Zürich Foundation.

##  2 Preliminaries

###  2.1 Notation and basic concepts

We let $[n]$ denote the set $\\{1,2,3,\;...\;n\\}$. The set $\\{0,1\\}^{n}$
denotes all binary strings of length $n$. For some binary string
$v\in\\{0,1\\}^{n}$, the $i$’th bit of $v$ is denoted $v_{i}$ (with $1\leq
i\leq n$). We denote as $|v|$ the _Hamming weight_ of $v$, which is defined as
the number of 1’s in $v$, or

$|v|=\sum_{i=1}^{n}v_{i}.$

The $xor$ of two bits $a$, $b$ is $a\oplus b=a+b\;mod\;2$. This extends to
strings so that for $v,w\in\\{0,1\\}^{n}$, $v\oplus w$ is their bitwise xor.
We also use the bitwise inner product:

$v\cdot w=\sum_{i=1}^{n}v_{i}\cdot w_{i}\;mod\;2.$

For a bit $b\in\\{0,1\\}$, we will use $\bar{b}$ to denote a binary string
consisting of copies of $b$. That is, $\bar{b}=bbb...b$. The number of copies
will generally be clear from the context and will otherwise be specified. We
also extend this notation to binary strings. For some string
$v\in\\{0,1\\}^{n}$, $\bar{v}$ will denote a string in which each bit of $v$
has been repeated. That is,
$\bar{v}=v_{1}v_{1}...v_{1}v_{2}...v_{2}v_{3}...v_{n-1}v_{n}...v_{n}$.

For any finite set $X$, we let $x\leftarrow_{r}X$ denote an element drawn
uniformly at random from $X$. The _total variation distance_ between two
density functions $f_{1},f_{2}:X\to[0,1]$ is

$TVD(f_{1},f_{2})=\frac{1}{2}\sum_{x\in X}|f_{1}(x)-f_{2}(x)|.$

The _Hellinger distance_ between $f_{1}$ and $f_{2}$ is

$H^{2}(f_{1},f_{2})=1-\sum_{x\in X}\sqrt{f_{1}(x)f_{2}(x)}.$

We let $\mathbb{N}$ denote the set of natural numbers, and $\mathbb{R}$ the
set of real numbers. We let $negl(x)$ denote a _negligible function_. A
function $\mu:\mathbb{N}\rightarrow\mathbb{R}$ is negligible if for any
positive polynomial $p(x)$ there exists an integer $N>0$ such that for all
$x>N$ it’s the case that

$|\mu(x)|<\frac{1}{p(x)}.$

We sometimes abbreviate polynomial functions as $poly$. Throughout the paper,
$\lambda$ will denote the _security parameter_. This will be polynomially-
related to the input size of all functions we consider. Consequently, all
polynomial and negligible functions will scale in $\lambda$.

In terms of quantum information, we follow the usual formalism as outlined,
for instance, in [NC02]. All Hilbert spaces are finite dimensional. We use
serif font to label spaces that correspond to certain quantum registers. For
instance, $\mathsf{X}$ will correspond to an $n$-qubit Hilbert space of inputs
to a function. We also extend the bar notation from strings to quantum states.
So, for instance $\ket{\bar{0}}=\ket{00...0}$. The multi-qubit _GHZ state_ can
then be written as
$\ket{\psi}=\frac{1}{\sqrt{2}}(\ket{\bar{0}}+\ket{\bar{1}})$.

We now recall some standard notions of classical and quantum computation. For
more details, we refer the reader to [AB09, NC02].

  * •

The notion of computational efficiency will refer to algorithms or circuits
that run in polynomial time.

  * •

We say that an algorithm (or Turing machine) is PPT if it uses randomness and
runs in polynomial time. We say it is QPT if it is a quantum algorithm running
in polynomial time.

  * •

Most of the Boolean functions we consider admit a circuit representation. All
Boolean circuits will be comprised of AND, OR, XOR and NOT gates.

  * •

We say that a classical gate has _bounded fan-out_ if the number of output
wires is constant (independent of the length of the input to the circuit).
Otherwise, we say it has _unbounded fan-out_.

  * •

For quantum computation we assume the standard circuit formalism with the gate
set $\\{R_{X},R_{Y},R_{Z},H,CZ,CNOT,CCNOT\\}$ and computational basis
measurements. Here, $R_{X}$, $R_{Y}$, $R_{Z}$ denote rotations along the $X$,
$Y$ and $Z$ axes of the Bloch sphere. More precisely,
$R_{W}(\theta)=exp(-i\theta W/2)$, with $W\in\\{X,Y,Z\\}$, the set of Pauli
matrices. The allowed rotation angles can be assumed to be multiples of
$\pi/4$. In addition, $H$ is the Hadamard operation, $CZ$ is a controlled
application of a Pauli-$Z$ gate, $CNOT$ is a controlled application of a
Pauli-$X$ gate and $CCNOT$ is a doubly-controlled Pauli-$X$ operation, also
known as a Toffoli gate. It should be noted that, apart from $CCNOT$, a number
of the existing quantum devices can indeed perform all of these gates natively
[AAB+19, AAA+19, WBD+19].

We say that a computational problem is _intractable_ if there is no
polynomial-time algorithm solving that problem. Throughout this paper we are
only concerned with computational intractability for PPT algorithms. We give a
simplified description of some candidate intractable problems of interest:

  * •

Factoring. Given a composite integer $N$, find its prime-factor decomposition.
For the specific case of semiprime $N=p\cdot q$, the task is to find primes
$p$ and $q$.

  * •

Discrete logarithm problem (DLP). For some abelian group $\mathbb{G}$, given
$g\in\mathbb{G}$ and $g^{k}$, with $k>0$, find $k$.

  * •

Learning with errors (LWE). Letting $\mathbb{F}_{q}$ be a finite field of
order $q>0$, given the matrix $A\in\mathbb{F}^{m\times n}_{q}$ and the vector
$y=As+e$, with $s\in\mathbb{F}_{q}^{n}$ and $e$ sampled from a discrete
Gaussian distribution over $\mathbb{F}_{q}^{m}$, find $s$.

  * •

Ring learning with errors (Ring-LWE). Letting $R_{q}$ be a quotient ring
$R_{q}=R/qR$, for some (cyclotomic) ring $R$ over the integers, given $m>0$
pairs $(a_{i},y_{i})$ with $a_{i}\in R_{q}$ and $y_{i}=a_{i}\cdot s+e_{i}$,
$i\leq m$, $s\in R_{q}$ and each $e_{i}$ sampled independently from a discrete
Gaussian distribution over $R_{q}$, find $s$.

LWE and Ring-LWE are also conjectured to be QPT-intractable [Reg09, LPR10].

###  2.2 Proof of quantumness protocols

####  2.2.1 Trapdoor claw-free functions

Most proof of quantumness protocols are based on trapdoor claw-free (TCF)
functions or noisy trapdoor claw-free functions (NTCF). We start with
definition of a TCF, taken from [KMCVY21].

######  Definition 2.1 (TCF family [KMCVY21]).

Let $\lambda$ be a security parameter, $K$ a set of keys, and $X_{k}$ and
$Y_{k}$ finite sets for each $k\in K$. A family of functions

$\mathcal{F}=\\{f_{k}:X_{k}\to Y_{k}\\}_{k\in K}$

is called a trapdoor claw free (TCF) family if the following conditions hold:

  1. 1.

Efficient Function Generation. There exists a PPT algorithm Gen which
generates a key $k\in K$ and the associated trapdoor data $t_{k}$:

$(k,t_{k})\leftarrow\textsc{Gen}(1^{\lambda})$

  2. 2.

Trapdoor Injective Pair. For all keys $k\in K$, the following conditions hold:

    1. (a)

Injective pair: Consider the set $R_{k}$ of all tuples $(x_{0},x_{1})$ such
that $f_{k}(x_{0})=f_{k}(x_{1})$. Let $X_{k}^{\prime}\subseteq X_{k}$ be the
set of values $x$ which appear in the elements of $R_{k}$. For all $x\in
X_{k}^{\prime}$, $x$ appears in exactly one element of $R_{k}$; furthermore,
$\lim_{\lambda\to\infty}|X_{k}^{\prime}|/|X_{k}|=1$.

    2. (b)

Trapdoor: There exists a polynomial-time deterministic algorithm INVF such
that for all $y\in Y_{k}$ and $(x_{0},x_{1})$ such that
$f_{k}(x_{0})=f_{k}(x_{1})=y$, INV${}_{\mathcal{F}}(t_{k},b,y)=x_{b}$, with
$b\in\\{0,1\\}$.

  3. 3.

Claw-free. For any non-uniform probabilistic polynomial time (nu-PPT)
classical algorithm $\mathcal{A}$, there exists a negligible function
$\mu(\cdot)$ such that

$\Pr\left[f_{k}(x_{0})=f_{k}(x_{1})\land x_{0}\neq
x_{1}|(x_{0},x_{1})\leftarrow\mathcal{A}(k)\right]<\mu(\lambda)$

where the probability is over both the choice of $k$ and the random coins of
$\mathcal{A}$.

  4. 4.

Efficient Superposition. There exists a polynomial-size quantum circuit that
on input a key $k$ prepares the state

$\frac{1}{\sqrt{|X_{k}|}}\sum_{x\in X_{k}}\ket{x}\ket{f_{k}(x)}$

Next, we define the notion of a noisy TCF, first introduced in [Mah18,
BCM+18]. These are TCFs for which the efficient superposition is allowed to be
approximate, rather than exact. The outputs of these functions are
additionally assumed to be distributions over binary strings, rather than just
binary strings. NTCFs, as defined in [BCM+18], also satisfy a property known
as the _adaptive hardcore bit_ which is independent of the “noisy” aspect of
the TCF. As we want to distinguish between TCFs which satisfy this property
and those that do not satisfy it, we shall refer to the former as _strong_
TCFs and the latter as ordinary TCFs, as per Definition 2.1. Thus, the NTCFs
we consider will be referred to as strong NTCFs:

######  Definition 2.2 (Strong NTCF Family [BCM+18]).

Let $\lambda$ be a security parameter. Let $\mathcal{X}$ and $\mathcal{Y}$ be
finite sets and $\mathcal{D}_{\mathcal{Y}}$ a collection of distributions over
$\mathcal{Y}$. Let $\mathcal{K}_{\mathcal{F}}$ be a finite set of keys. A
family of functions

$\mathcal{F}\,=\,\big{\\{}f_{k,b}:\mathcal{X}\rightarrow\mathcal{D}_{\mathcal{Y}}\big{\\}}_{k\in\mathcal{K}_{\mathcal{F}},b\in\\{0,1\\}}$

is called a strong noisy trapdoor claw-free (strong NTCF) family if the
following conditions hold:

  1. 1.

Efficient Function Generation. Same as in Definition 2.1.

  2. 2.

Trapdoor Injective Pair. Same as in Definition 2.1.

  3. 3.

Efficient Range Superposition. For all keys $k\in\mathcal{K}_{\mathcal{F}}$
and $b\in\\{0,1\\}$ there exists a function
$f^{\prime}_{k,b}:\mathcal{X}\mapsto\mathcal{D}_{\mathcal{Y}}$ such that

    1. (a)

For all $(x_{0},x_{1})\in\mathcal{R}_{k}$ and
$y\in\textsc{Supp}(f^{\prime}_{k,b}(x_{b}))$,
INV${}_{\mathcal{F}}(t_{k},b,y)=x_{b}$ and INV${}_{\mathcal{F}}(t_{k},b\oplus
1,y)=x_{b\oplus 1}$.

    2. (b)

There exists an efficient deterministic procedure CHKF that, on input $k$,
$b\in\\{0,1\\}$, $x\in\mathcal{X}$ and $y\in\mathcal{Y}$, returns $1$ if
$y\in\textsc{Supp}(f^{\prime}_{k,b}(x))$ and $0$ otherwise. Note that CHKF is
not provided the trapdoor $t_{k}$.

    3. (c)

For every $k$ and $b\in\\{0,1\\}$,

$\textsc{E}_{x\leftarrow_{U}\mathcal{X}}\big{[}\,H^{2}(f_{k,b}(x),\,f^{\prime}_{k,b}(x))\,\big{]}\,\leq\,\mu(\lambda)\;,$

for some negligible function $\mu(\cdot)$. Here $H^{2}$ is the Hellinger
distance. Moreover, there exists an efficient procedure SAMPF that on input
$k$ and $b\in\\{0,1\\}$ prepares the state

$\frac{1}{\sqrt{|\mathcal{X}|}}\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\sqrt{(f^{\prime}_{k,b}(x))(y)}\ket{x}\ket{y}\;.$

  4. 4.

Adaptive Hardcore Bit. For all keys $k\in\mathcal{K}_{\mathcal{F}}$ the
following conditions hold, for some integer $w$ that is a polynomially bounded
function of $\lambda$.

    1. (a)

For all $b\in\\{0,1\\}$ and $x\in\mathcal{X}$, there exists a set
$G_{k,b,x}\subseteq\\{0,1\\}^{w}$ such that
$\Pr_{d\leftarrow_{U}\\{0,1\\}^{w}}[d\notin G_{k,b,x}]$ is negligible, and
moreover there exists an efficient algorithm that checks for membership in
$G_{k,b,x}$ given $k,b,x$ and the trapdoor $t_{k}$.

    2. (b)

If

$\displaystyle H_{k}$ $\displaystyle=$
$\displaystyle\big{\\{}(b,x_{b},d,d\cdot(x_{0}\oplus
x_{1}))\,|\;b\in\\{0,1\\},\;(x_{0},x_{1})\in\mathcal{R}_{k},\;d\in
G_{k,0,x_{0}}\cap G_{k,1,x_{1}}\big{\\}}\;,$ $\displaystyle\overline{H}_{k}$
$\displaystyle=$ $\displaystyle\\{(b,x_{b},d,c)\,|\;(b,x,d,c\oplus 1)\in
H_{k}\big{\\}}\;,$

then for any quantum polynomial-time procedure $\mathcal{A}$ there exists a
negligible function $\mu(\cdot)$ such that

$\Big{|}\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\mathcal{A}(k)\in
H_{k}]-\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\mathcal{A}(k)\in\overline{H}_{k}]\Big{|}\,\leq\,\mu(\lambda)\;.$
(6)

As a point of clarification, note that a noisy TCF (NTCF) is a TCF with a
modified efficient range superposition property. A strong NTCF is a NTCF with
the adaptive hardcore bit property. As mentioned, in [Mah18, BCM+18] NTCFs are
not distinguished from strong NTCFs. As an abuse of notation, we will use NTCF
and strong NTCF interchangeably.

####  2.2.2 The BCMVV protocol

The first protocol we introduce is the one from [BCM+18], which relies on the
adaptive hardcore bit property and so the function family used is NTCF. We
outlined the protocol in the introduction, while here we give a step-by-step
description of its workings, in Figure 2.

BCMVV protocol

Let $\mathcal{F}$ be an NTCF family of functions. Let $\lambda$ be a security
parameter and $N\geq 1$ a number of rounds. The parties taking part in the
protocol are a PPT machine, known as the verifier and a QPT machine, known as
the prover. They will repeat the following steps $N$ times:

  1. 1.

The verifier generates $(k,t_{k})\leftarrow\textsc{Gen}(1^{\lambda})$. It
sends $k$ to the prover.

  2. 2.

The prover uses $k$ to run SAMPF and prepare the state:

$\frac{1}{\sqrt{|\mathcal{X}|}}\sum_{b\in\\{0,1\\},x\in\mathcal{X},y\in\mathcal{Y}}\sqrt{(f^{\prime}_{k,b}(x))(y)}\ket{b}_{\mathsf{B}}\ket{x}_{\mathsf{X}}\ket{y}_{\mathsf{Y}}\;.$

It then measures the $\mathsf{Y}$ register, resulting in the string
$y\in\\{0,1\\}^{poly(\lambda)}$ which it sends to the verifier.

  3. 3.

The verifier selects a uniformly random challenge $c\leftarrow_{R}\\{0,1\\}$
and sends $c$ to the prover.

  4. 4.

    1. (a)

(Preimage test:) When $c=0$, the prover is expected to measure in the standard
basis the $\mathsf{BX}$ registers of the state leftover in step 2. It obtains
the outcomes $b\in\\{0,1\\}$ and $x\in\\{0,1\\}^{n}$, with
$n(\lambda)=poly(\lambda)$, which it sends to the verifier. If
$\textsc{Chk}_{\mathcal{F}}(k,b,x,y)=0$ the verifier aborts, otherwise it
continues.

    2. (b)

(Equation test:) When $c=1$, the prover is expected to apply Hadamard gates to
each qubit in the $\mathsf{BX}$ registers and measure them in the standard
basis (equivalently, measure all qubits in the Hadamard basis). It obtains the
outcomes $b^{\prime}\in\\{0,1\\}$ and $d\in\\{0,1\\}^{n}$ which it sends to
the verifier. The verifier computes
$(x_{0},x_{1})=\textsc{Inv}_{\mathcal{F}}(t_{k},y)$ and rejects if
$d\cdot(x_{0}\oplus x_{1})\neq b^{\prime}$.

At the end of the $N$ rounds, if the verifier has not aborted it accepts.

Figure 2:  The BCMVV proof of quantumness protocol based on NTCFs [BCM+18].

The protocol is complete, in the following sense:

######  Theorem 2.1 ([BCM+18]).

A QPT prover, $\mathcal{P}$, following the honest strategy in the BCMVV
protocol is accepted with probability $1-negl(\lambda)$.

The soundness of the protocol against classical provers follows from the
following theorem:

######  Theorem 2.2 ([BCM+18, ZNR+21]).

For any PPT prover, $\mathcal{P}$, in the BCMVV protocol, it is the case that

$p_{\mathrm{pre}}+2p_{\mathrm{eq}}-2\leq negl(\lambda)$ (7)

where $p_{\mathrm{pre}}$ is $\mathcal{P}$’s success probability in the
preimage test and $p_{\mathrm{eq}}$ is $\mathcal{P}$’s success probability in
the equation test.

Thus, in any run of the protocol, as long as Inequality 7 is violated, we
conclude that the prover is quantum.

One known instantiation of the BCMVV protocol, as is described by [BCM+18], is
based on the LWE problem. The LWE-based construction is currently the only
known instance of a strong NTCF family of functions.

####  2.2.3 KMCVY protocol

The BCMVV protocol relies on the adaptive hardcore bit property of NTCFs in
order to be sound. However, this property is only known to be true for NTCFs
based on LWE. The authors of [KMCVY21] addressed this fact by introducing a
proof of quantumness protocol that can use any TCF. As mentioned in the
introduction, their protocol is a sort of computational Bell test. We outline
it in Figure 3.

KMCVY protocol

Let $\mathcal{F}$ be a TCF family of functions. Let $\lambda$ be a security
parameter, $N\geq 1$ a number of rounds and $T=1/poly(\lambda)$ a threshold
parameter. The parties taking part in the protocol are a PPT machine, known as
the verifier and a QPT machine, known as the prover. Before interacting with
the prover, the verifier initializes two counters $N_{s}=0$, $N_{t}=0$. The
two will then repeat the following steps $N$ times:

  1. 1.

The verifier generates $(k,t_{k})\leftarrow\textsc{Gen}(1^{\lambda})$. It
sends $k$ to the prover.

  2. 2.

The prover uses $k$ to prepare the state:

$\frac{1}{\sqrt{|X_{k}|}}\sum_{x\in
X_{k}}\ket{x}_{\mathsf{X}}\ket{f_{k}(x)}_{\mathsf{Y}}$

It then measures the $\mathsf{Y}$ register, resulting in the string
$y\in\\{0,1\\}^{poly(\lambda)}$ which it sends to the verifier.

  3. 3.

The verifier selects a uniformly random challenge $c\leftarrow_{R}\\{0,1\\}$
and sends $c$ to the prover.

  4. 4.

    1. (a)

(Preimage test:) When $c=0$, the prover is expected to measure in the standard
basis the $\mathsf{X}$ register of the state leftover in step 2. It obtains
the outcome $x\in\\{0,1\\}^{n}$, with $n(\lambda)=poly(\lambda)$, which it
sends to the verifier. If $f_{k}(x)\neq y$ the verifier aborts, otherwise it
continues.

    2. (b)

(Computational Bell test:) When $c=1$,

      1. i.

The verifier sends a random bitstring $v\leftarrow_{R}\\{0,1\\}^{n}$ to the
prover.

      2. ii.

The prover creates the state

$\frac{1}{\sqrt{2}}\left(\ket{v\cdot
x_{0}}_{\mathsf{A}}\ket{x_{0}}_{\mathsf{X}}+\ket{v\cdot
x_{1}}_{\mathsf{A}}\ket{x_{1}}_{\mathsf{X}}\right)$

with $f_{k}(x_{0})=f_{k}(x_{1})=y$.

      3. iii.

The prover applies Hadamard gates to all qubits in the $\mathsf{X}$ register
and measures them in the standard basis. The measurement outcome is denoted
$d\in\\{0,1\\}^{n}$ and is sent to the verifier.

      4. iv.

The verifier computes $(x_{0},x_{1})=\textsc{Inv}_{\mathcal{F}}(t_{k},y)$.
Together with $d$, the verifier can determine the current state
$\ket{\gamma}_{\mathsf{A}}\in\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}$ in the
prover’s $\mathsf{A}$ register. It then chooses a random
$\phi\in\\{\pi/4,-\pi/4\\}$ and sends it to the prover.

      5. v.

The prover is expected to measure the qubit in the $\mathsf{A}$ register in
the basis:

$\left\\{\begin{array}[]{ll}\cos\left(\frac{\phi}{2}\right)\ket{0}+&\sin\left(\frac{\phi}{2}\right)\ket{1}\\\
\cos\left(\frac{\phi}{2}\right)\ket{1}-&\sin\left(\frac{\phi}{2}\right)\ket{0}\\\
\end{array}\right\\}\;.$

      6. vi.

The verifier sets $N_{s}\leftarrow N_{s}+1$ if the measurement outcome was the
likely one.

If the verifier has not aborted, it will accept if
$\frac{N_{s}}{N_{t}}-0.75\geq T$.

Figure 3:  The KMCVY proof of quantumness protocol based on TCFs [KMCVY21].

The protocol is complete, in the following sense:

######  Theorem 2.3 ([KMCVY21]).

A QPT prover, $\mathcal{P}$, following the honest strategy in the KMCVY
protocol is accepted with probability $1-negl(\lambda)$.

The soundness of the protocol against classical provers follows from the
following theorem:

######  Theorem 2.4 ([KMCVY21]).

For any PPT prover, $\mathcal{P}$, in the KMCVY protocol, it is the case that

$p_{\mathrm{pre}}+4p_{\mathrm{Bell}}-2\leq negl(\lambda)$ (8)

where $p_{\mathrm{pre}}$ is $\mathcal{P}$’s success probability in the
preimage test and $p_{\mathrm{Bell}}$ is $\mathcal{P}$’s success probability
in the computational Bell test.

Thus, in any run of the protocol, as long as Inequality 8 is violated, we
conclude that the prover is quantum.

In [KMCVY21], the authors provide the following candidate TCFs:

  * •

Rabin’s function, or $x^{2}\;mod\;n$. The TCF properties are based on the
computational intractability of factoring.

  * •

A Diffie-Hellman-based function. The TCF properties are based on the
computational intractability of DLP.

  * •

A ring-LWE-based function. The TCF properties are based on the computational
intractability of ring-LWE.

Of course, the NTCF family based on LWE can also be used.

###  2.3 Randomized encodings

Randomized encodings (also known as _garbled circuits_ [Yao86]) are
probabilistic encodings of functions that are information-theoretically
equivalent to the functions they encode. The idea of constructing randomized
encodings which can be evaluated in constant depth originated with [AIK04]. We
restate here the essential definitions and results from that paper.

######  Definition 2.3 (Randomized encoding [AIK04]).

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{l}$ be a function and
$r\leftarrow_{R}\\{0,1\\}^{m}$ be $m$ bits sampled uniformly at random from
$\\{0,1\\}^{m}$. We say that a function
$\hat{f}:\\{0,1\\}^{n}\times\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{s}$ is a
$\delta$-correct, $\epsilon$-private randomized encoding of $f$ if it
satisfies the following properties.

  * •

Efficient generation. There exists a deterministic polynomial-time algorithm
that, given a description of the circuit implementing $f$, outputs a
description of a circuit for implementing $\hat{f}$.

  * •

$\delta$-correctness. There exists a deterministic polynomial-time algorithm
Dec, called a decoder such that for every input $x\in\\{0,1\\}^{n}$,
$Pr[\textsc{Dec}(\hat{f}(x,r))\neq f(x)]\leq\delta$.

  * •

$\epsilon$-privacy. There exists a PPT algorithm $S$, called a simulator, such
that for every $x\in\\{0,1\\}^{n}$, $TVD(S(f(x)),\hat{f}(x,r))\leq\epsilon$.

A _perfect randomized encoding_ is one for which $\delta=0$ (perfect
correctness) and $\epsilon=0$ (perfect privacy). Note that for perfect
encodings $f(x)$ can always be reconstructed from $\hat{f}(x,r)$.
Additionally, perfect privacy means that $\hat{f}(x,r)$ encodes as much
information about $x$ as $f(x)$. An important property of perfect encodings
that we will use is that of _unique randomness_ :

######  Theorem 2.5 (Unique randomness [AIK04]).

Suppose $\hat{f}$ is a perfect randomized encoding of $f$. Then for any input
$x$, the function $\hat{f}(x,\cdot)$ is injective; namely, there are no
distinct $r$,$r^{\prime}$ such that $\hat{f}(x,r)=\hat{f}(x,r^{\prime})$.
Moreover, if $f$ is a permutation, then so is $\hat{f}$.

The main result in [AIK04] is the following:

######  Theorem 2.6 ([AIK04]).

Any Boolean function that can be computed by a log-depth circuit, admits a
perfect randomized encoding that can be computed in constant depth.

In fact a more general result is shown in [AIK04], however the result of the
above theorem is sufficient for our purposes. We also require the following
result:

######  Lemma 2.1 (Randomness reconstruction).

Given $x$ and $\hat{f}(x,r)$, where $\hat{f}$ is a randomized encoding
following the construction from [AIK04], there is a deterministic polynomial-
time algorithm, denoted Rrc, for computing the randomness $r$.

Note that this property is not universal to randomized encodings, in that it
cannot be derived from the definition of randomized encodings. However, the
property is satisfied by the specific encodings defined in [AIK04]. This fact
is mentioned in [AIK04], however no formal proof is provided. We outline their
construction in Appendix A and prove the randomness reconstruction property in
Appendix B.

Finally, we show the following fact concerning randomized encodings of
functions that may have collisions:

######  Lemma 2.2 (Collision preservation).

If there exist $x_{1}$ and $x_{2}$ such that $f(x_{1})=f(x_{2})$, then for
every $r_{1}$, there must exist a unique $r_{2}$ such that
$\hat{f}(x_{1},r_{1})=\hat{f}(x_{2},r_{2})$.

###### Proof.

Perfect privacy says that there exists a polynomial-time simulator $S$, such
that for all $x$, it should be that $TVD(S(f(x)),\hat{f}(x,r))=0$, where $TVD$
is the total variation distance and $r$ is sampled uniformly at random.
Essentially, $S$ should always be able to sample from the set of randomized
encoding values that can be decoded to $f(x)$ (i.e. all $\hat{f}(x,r)$, for
all $r$).

But now suppose we have $x_{1}$ and $x_{2}$ such that $f(x_{1})$ = $f(x_{2})$.
By perfect privacy it must be that $TVD(S(f(x_{1})),\hat{f}(x_{1},r_{1}))=0$
and $TVD(S(f(x_{2})),\hat{f}(x_{2},r_{2}))=0$, for uniform $r_{1}$ and
$r_{2}$. Since $f(x_{1})=f(x_{2})$, it must be that
$TVD(\hat{f}(x_{1},r_{1}),\hat{f}(x_{2},r_{2}))=0$. In other words,
$\hat{f}(x_{1},r_{1})$ and $\hat{f}(x_{2},r_{2})$ are the same distribution
and so the randomized encodings that can be decoded to $f(x_{1})=f(x_{2})$ are
the same for both $x_{1}$ and $x_{2}$.

Finally, from unique randomness, we have that whenever $f(x_{1})=f(x_{2})$,
for every $r_{1}$ there exists a unique $r_{2}$ such that
$\hat{f}(x_{1},r_{1})=\hat{f}(x_{2},r_{2})$. Hence, the collisions of the
original function are exactly preserved by the encoding. ∎

##  3 Proofs of quantumness in constant quantum depth

We now have all the tools for taking the two proof of quantumness protocols
from Section 3 and mapping them to equivalent protocols in which the prover’s
operations require only constant quantum depth and logarithmic classical
depth. The idea is the following: provided the (N)TCF of the original protocol
can be evaluated in log depth, simply _replace it with a constant-depth
randomized encoding_ , as follows from Theorem 2.6. In other words, $y=f(x)$
should be replaced by $\hat{y}=\hat{f}(\hat{x})$ where $\hat{x}=(x,r)$ and $r$
denotes the randomness of the encoding. As mentioned, it was shown in [GH20,
KMCVY21] that the (N)TCFs of the two proofs of quantumness considered here,
can indeed be performed in classical logarithmic depth. Thus, to show that our
construction works, we prove two things:

  1. 1.

The prover can evaluate $\hat{f}$ coherently in constant quantum depth (as
well as perform its remaining operations in constant depth). This is the
completeness condition of the protocol shown in Subsection 3.1.

  2. 2.

A randomized encoding of a (N)TCF is itself a (N)TCF. This means that the
modified protocol is sound against classical polynomial-time provers. We show
this in Subsection 3.2.

###  3.1 Completeness

To show completeness, we give a strategy for an honest prover, that
interleaves constant-depth quantum circuits and log-depth classical circuits,
to succeed in the proofs of quantumness described in Section 3. We assume that
the (N)TCFs used in those protocols can be evaluated in constant classical
depth and denote the corresponding function as $\hat{f}_{k}$. These circuits
are allowed to contain gates of unbounded fan-out. We can always map such a
circuit to one that uses only gates of bounded fan-out, provided multiple
copies of the input bits are provided. The intuition for this was mentioned in
the Introduction and in Figure 1. We will assume each input bit of the initial
circuit has been copied $k$ times.

The first step is preparing the state corresponding to a coherent evaluation
of the (N)TCF over a uniform superposition of inputs:

$\ket{\psi}=\sum_{b\in\\{0,1\\}}\sum_{\hat{x}\in\\{0,1\\}^{poly(\lambda)}}\ket{b}_{\mathsf{B}}\ket{x}_{\mathsf{X}}\ket{\hat{f}_{k}(b,x)}_{\mathsf{Y}},$
(9)

where the $\mathsf{B}$ and $\mathsf{X}$ registers store the inputs of
$\hat{f}$ and the $\mathsf{Y}$ register will store the computed value of
$\hat{f}$. As a slight abuse of notation, we omit the normalization term and
assume the state is an equal superposition.

Instead of preparing the state in Equation 9, we will prepare a state that is
essentially equivalent to it, namely:

$\ket{\psi}=\sum_{b\in\\{0,1\\}}\sum_{\hat{x}\in\\{0,1\\}^{poly(\lambda)}}\ket{\bar{b}}_{\mathsf{B}}\ket{\bar{x}}_{\mathsf{X}}\ket{\hat{f}_{k}(b,x)}_{\mathsf{Y}},$
(10)

where $\ket{\bar{b}}=\ket{b}^{\otimes k}$ and $\ket{\bar{x}}=\ket{x}^{\otimes
k}$. We view the $\mathsf{X}$ register as consisting of multiple sub-
registers, one for each bit in $x$. In other words777Note that this is the
only place where a subscript on $x$ is used to denote a bit of $x$. Throughout
the rest of the section, $x_{b}$ will denote a specific $x$ _string_ , and
_does not_ refer to the $b$’th bit of the string $x$., if
$x=x_{1}x_{2}...x_{n}$, with $n(\lambda)=poly(\lambda)$, and
$\bar{x}=\bar{x}_{1}\bar{x}_{2}...\bar{x}_{n}$, we assume
$\mathsf{X}=\mathsf{X}_{1}\otimes\mathsf{X}_{2}\otimes...\otimes\mathsf{X}_{n}$.
Here, $\mathsf{X}_{i}$ holds the state
$\sum_{x_{i}\in\\{0,1\\}}\ket{\bar{x}_{i}}$.

The prover starts by preparing:

$\ket{\psi_{0}}=\sum_{b,\hat{x}}\ket{\bar{b}}_{\mathsf{B}}\ket{\bar{x}}_{{\mathsf{X}}}\ket{0}_{{\mathsf{Y}}}.$
(11)

Note that the $\mathsf{B}$ and $\mathsf{X}$ registers contain GHZ states.
These can be prepared in constant quantum depth, together with logarithmic
classical depth. As outlined in the introduction, the idea is to first prepare
a poor man’s cat state in constant depth, as described in [WKST19]. The prover
then uses the parity information from the prepared poor man’s cat state to
perform a correction operation consisting of Pauli-$X$ gates. Determining
where to perform the $X$ gates from the parity information requires
logarithmic classical depth. The $X$ corrections will map the poor man’s cat
states to GHZ states.

Next, the function $\hat{f}$ needs to be evaluated and the outcome will be
stored in $\mathsf{Y}$ register. With multiple copies of the input, the
circuit evaluating $\hat{f}$ consists only of gates with bounded fan-out. It
can therefore be mapped to an equivalent constant depth quantum circuit
(having twice the depth, so as to perform the operations reversibly)
consisting of Toffoli, Pauli-$X$ and $CNOT$ gates. Evaluating this circuit on
the state from 11 will result in the state from 10, as intended.

The prover is then required to measure the $\mathsf{Y}$ register and report
the outcome to the verifier. This adds one more layer to the circuit. The
measured state will collapse to

$\ket{\psi_{y}}=\sum_{b\in\\{0,1\\}}\ket{\bar{b}}_{\mathsf{B}}\ket{\bar{x}_{b}}_{\mathsf{X}}\ket{y}_{\mathsf{Y}}.$

In the preimage test, the prover will also measure this state in the
computational basis and report the outcome to the verifier.

The next steps will differ for the two protocols.

  1. 1.

For the BCMVV protocol: In the equation test, the prover applies a layer of
Hadamard gates on the qubits in $\mathsf{B}$ and $\mathsf{X}$. It then
measures them in the computational basis, denoting the results as
$b^{\prime}\in\\{0,1\\}^{k}$ and $d\in\\{0,1\\}^{n\cdot k}$. In the original
protocol, $b^{\prime}$ was one bit and $d$ was $n$ bits and they satisfy the
relation $d\cdot(x_{0}\oplus x_{1})=b^{\prime}$. To arrive at that result, the
prover will xor all the bits in $b^{\prime}$ and all bits in each $k$-bit
block of $d$ and report those results to the verifier. Note that the
distributions of these xor-ed outcomes is the same as the distribution over
the outcomes of a Hadamard-basis measurement of:

$\sum_{b\in\\{0,1\\}}\ket{b}_{\mathsf{B}}\ket{x_{b}}_{\mathsf{X}}.$

  2. 2.

For the KMCVY protocol: In the computational Bell test, the prover receives
the string $v$ from the verifier. The original protocol has the prover use an
ancilla qubit to store the bitwise inner product $v\cdot x_{b}$. However, such
a multiplication requires _serial_ $CNOT$ gates which cannot be performed in
constant depth. We therefore use a multi-qubit ancila register initalized as a
GHZ state $\ket{a}_{\mathsf{A}}=\frac{\ket{0}^{\otimes n}+\ket{1}^{\otimes
n}}{\sqrt{2}}$. For every bit $v_{i}$, in $v$, if $v_{i}=1$, the prover
applies a controlled-Z ($CZ$) gate with control qubit any of the qubits in
$\mathsf{X}_{i}$ and target qubit $\ket{a}_{i}$. The resulting state will be

$\sum_{b\in\\{0,1\\}}\frac{\ket{0}^{\otimes n}_{\mathsf{A}}+(-1)^{v\cdot
x_{b}}\ket{1}^{\otimes
n}_{\mathsf{A}}}{\sqrt{2}}\ket{\bar{x}_{b}}_{\mathsf{X}}=\sum_{b\in\\{0,1\\}}\ket{(-1)^{v\cdot
x_{b}}}_{\mathsf{A}}\ket{\bar{x}_{b}}_{\mathsf{X}}$

where we denote $\ket{(-1)^{v\cdot
x_{b}}}=\sum_{b\in\\{0,1\\}}\frac{\ket{0}^{\otimes
n}_{\mathsf{A}}+(-1)^{v\cdot x_{b}}\ket{1}^{\otimes
n}_{\mathsf{A}}}{\sqrt{2}}$. Next, the prover is required to measure
$\mathsf{X}$ in the Hadamard basis yielding the result $d\in\\{0,1\\}^{n\cdot
k}$. Once again, in the original protocol $d$ is an $n$-bit string. As in the
BCMVV protocol, this is “fixed” by having the prover xor each $k$-bit block of
$d$ and report those outcomes to the verifier. The verifier can then use this
result to determine the state in the ancilla register.

After the measurement, the ancilla register will be in the state
$\ket{\gamma}_{\mathsf{A}}\in\\{\ket{\bar{0}},\ket{\bar{1}},\ket{\bar{+}},\ket{\bar{-}}\\}$
where $\ket{\bar{\pm}}=\frac{\ket{\bar{0}}\pm\ket{\bar{1}}}{\sqrt{2}}$888Note
that here the bar notation, $\ket{\bar{a}}$, refers to an $n$-fold repetition,
rather than a $k$-fold one as in the previous case. That is, here
$\ket{\bar{a}}=\ket{a}^{\otimes n}$.. As the last step, the prover receives
$\phi\in\\{-\pi/4,\pi/4\\}$. The original protocol requires him to measure the
ancilla register in the rotated basis

$\left\\{\begin{array}[]{lr}\cos(\phi/2)\ket{\bar{0}}+\sin(\phi/2)\ket{\bar{1}}\\\
\cos(\phi/2)\ket{\bar{1}}-\sin(\phi/2)\ket{\bar{0}}\end{array}\right.$

and report the result, $b^{\prime}$. But how does the prover perform this
measurement in constant depth? We give an approach that requires one more
round of interleaving constant-depth quantum circuits and a log-depth
classical computation. The basic idea is to reduce the multi-qubit state in
the ancilla to a single-qubit state, i.e.
$\\{\ket{\bar{0}},\ket{\bar{1}},\ket{\bar{+}},\ket{\bar{-}}\\}\rightarrow\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}$.
This reduction needs to be done in such a way that
$\\{\ket{\bar{0}},\ket{\bar{1}}\\}\to\\{\ket{0},\ket{1}\\}$ and
$\\{\ket{\bar{+}},\ket{\bar{-}}\\}\to\\{\ket{+},\ket{-}\\}$. Once this is
done, the resulting qubit can be measured in the rotated basis.

To perform the reduction, the prover first measures all but one qubit of
$\ket{\gamma}_{\mathsf{A}}$ in the Hadamard basis. Denote this $(n-1)$-bit
outcome as $w$. If the initial state was $\ket{\bar{0}}$ or $\ket{\bar{1}}$,
the unmeasured qubit will be $\ket{0}$ or $\ket{1}$ respectively. If the
initial state was $\ket{\bar{\pm}}$, it can be re-expressed as

$\begin{split}\ket{\bar{\pm}}&\propto\ket{0}\ket{00...0}\pm\ket{1}\ket{11...1}\\\
&\propto\ket{0}(\ket{+}+\ket{-})^{\otimes
n-1}\pm\ket{1}(\ket{+}-\ket{-})^{\otimes n-1}\\\
&\propto\sum_{w}\left(\ket{0}\pm(-1)^{|w|}\ket{1}\right)\ket{w}\\\
&\propto\sum_{w}Z^{|w|\;mod\;2}\ket{\pm}\ket{w}\end{split}$

Thus, the qubit after the measurement will be $Z^{|w|\;mod\;2}\ket{\pm}$. The
prover will apply the $Z^{|w|\;mod\;2}$ operation to this qubit. In this way,
the state $\ket{\bar{\pm}}$ is reduced to $\ket{\pm}$.

Finally, the prover has to measure the qubit in the rotated basis and report
the outcome. This can be done in constant depth by rotating the qubit
appropriately and measuring in the standard basis. As in the original
protocol, this prover will pass the verifier’s checks with probability
$\cos(\pi/8)^{2}\approx 85\%$.

###  3.2 Soundness

We do not need to prove soundness from scratch for our modified protocols.
Instead, since our only change was to replace the (N)TCFs used in the
protocols with randomized encodings, we will have the same soundness as the
original constructions provided randomized encodings of (N)TCFs are still
(N)TCFs. That is what we show here.

######  Theorem 3.1.

A perfect randomized encoding of a (N)TCF, satisfying the randomness
reconstruction property, is still a (N)TCF.

###### Proof.

We show this result for NTCFs specifically, since the TCF case is subsumed.
The idea of the proof is to show that every property of a NTCF is also
satisfied by its randomized encoding.

  1. 1.

Efficient Function Generation. By definition, randomized encodings can be
efficiently generated given a description of the function to be encoded. In
this case, the description is given by the public key produced by the PPT
algorithm $\textrm{GEN}_{\mathcal{F}}$. More precisely,
$\textrm{GEN}_{\mathcal{F}}$ generates the key $k\in\mathcal{K}_{\mathcal{F}}$
together with a trapdoor $t_{k}$. The generating procedure for the encoding
will run $\textrm{GEN}_{\mathcal{F}}$ and output $k$, the efficient circuit
for generating a randomized encoding and the trapdoor $t_{k}$. Schematically,

$(\hat{f}_{t_{k},b},t_{k})\xleftarrow{\textrm{randomized
encoding}}(f_{tk,b},t_{k})\equiv(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})\;.$

  2. 2.

Trapdoor Injective Pair.

    1. (a)

Trapdoor: Due to perfect correctness,
$\textsc{Supp}(\hat{f}_{pk,b}(x_{0},r_{0}))\cap\textsc{Supp}(\hat{f}_{pk,b}(x_{1},r_{1}))=\emptyset$
is satisfied since if
$\textsc{Supp}(\hat{f}_{pk,b}(x_{0},r_{0}))\cap\textsc{Supp}(\hat{f}_{pk,b}(x_{1},r_{1}))\neq\emptyset$,
then perfect correctness leads to
$\textsc{Supp}(f_{pk,b}(x_{0}))\cap\textsc{Supp}(f_{pk,b}(x_{1}))\neq\emptyset$
which violates the trapdoor injective pair property of the original function
$f$. The efficient deterministic algorithm of inverting the randomized
encoding also exists and is defined as
$\textsc{Inv}_{\hat{\mathcal{F}}}(tk,b,\hat{y})=\textsc{Rrc}\circ\textsc{Inv}_{\mathcal{F}}\circ\textsc{Dec}(tk,b,\hat{y})$,
i.e. the composition of decoding operation for the encoding, the original
$\textsc{Inv}_{\mathcal{F}}$ procedure of the NTCF and the randomness
reconstruction procedure (see Lemma 2.1).

    2. (b)

Injective pair: this is guaranteed by the collision-preservation property 2.2
and the injective pair of $\mathcal{F}$.

  3. 3.

Efficient Range Superposition. The efficient range superposition property of
the original function $f$ means there’s an efficient quantum procedure to
create a state approximating a superposition over the range of $f$. Assume we
add an additional register, $\mathcal{R}$, to represent the randomness of the
encoding, $\hat{f}$, and initialize it as a uniform superposition over
computational basis states. We can now combine the efficient procedure for
generating $\hat{f}$ with the procedure for generating the range superposition
of $f$ and apply them coherently on $\mathcal{R}$. This will then yield the
desired state

$\sum_{x,r,y}\sqrt{(\hat{f}^{\prime}_{k,b}(x,r))(y)}\ket{x}\ket{r}\ket{y}\;,$

suitably normalized.

  4. 4.

Adaptive Hardcore Bit. We prove this property by contradiction. Assume there
exists a QPT adversary $\hat{\mathcal{A}}$ that breaks the adaptive hardcore
bit property for the randomized encoding. This means that there exists a non-
negligible function $p(\lambda)$ that satisfies

$\Big{|}\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\hat{\mathcal{A}}(k)\in\hat{H}_{k}]-\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\hat{\mathcal{A}}(k)\in\overline{\hat{H}}_{k}]\Big{|}\,\geq\,p(\lambda)\;$

where

$\hat{H}_{k}=\big{\\{}(b,\hat{x}_{b},\hat{d},\hat{d}\cdot(\hat{x}_{0}\oplus\hat{x}_{1}))\,|\;b\in\\{0,1\\},\;(\hat{x}_{0},\hat{x}_{1})\in\hat{\mathcal{R}}_{k},\;\hat{d}\in\hat{G}_{k,0,x_{0}}\cap\hat{G}_{k,1,x_{1}}\big{\\}}\;$

and

$\overline{\hat{H}}_{k}=\\{(b,\hat{x}_{b},\hat{d},c)\,|\;(b,\hat{x},\hat{d},c\oplus
1)\in\hat{H}_{k}\big{\\}}\;.$

By definition $\hat{x}_{b}=(x_{b},r_{b})$, therefore $\hat{d}$ can be split
into $(d_{x},d_{r})$ such that

$\hat{x}_{b}\cdot\hat{d}=(x_{b}\cdot d_{x})\oplus(r_{b}\cdot d_{r})$

which implies that

$\hat{d}\cdot(\hat{x}_{0}\oplus\hat{x}_{1})=(d_{x}\cdot(x_{0}\oplus
x_{1}))\oplus(d_{r}\cdot(r_{0}\oplus r_{1})).$

Note that the output of $\hat{\mathcal{A}}$ is a tuple
$(b,\hat{x}_{b},\hat{d},\hat{d}\cdot(\hat{x}_{0}\oplus\hat{x}_{1}))$. One can
now define a new QPT adversary $\mathcal{A}$ which runs $\mathcal{\hat{A}}$
and then outputs
$(b,x_{b},d_{x},\hat{d}\cdot(\hat{x}_{0}\oplus\hat{x}_{1})\oplus(d_{r}\cdot(r_{0}\oplus
r_{1})))$. This then implies that

$\Big{|}\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\mathcal{A}(k)\in
H_{k}]-\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\mathcal{A}(k)\in\overline{H}_{k}]\Big{|}\,\geq\,p(\lambda)\;.$

Hence, the adaptive hardcore bit of the original NTCF family is violated. We
conclude that the randomized encoding must also satisfy the adaptive hardcore
bit property.

∎

###  3.3 Resource estimation

In this section, we give some estimates of the resources required to run our
modified protocols. We summarize this information in Table 1 and proceed to
explain the results. The functions listed in the table are the same as the
ones from [KMCVY21], as these are the existing candidate TCFs used in proof of
quantumness protocols.

Function | Adaptive H.C. | # of quantum-classical interleaving | Depth | Width
---|---|---|---|---
LWE | ✓ | 3 | 14 | $\mathcal{O}(\lambda l^{4})$
Ring-LWE | ✗ | 4 | 18 | $\mathcal{O}(\lambda l^{4})$
$x^{2}\mod n$ | ✗ | 4 | 18 | $\mathcal{O}(\lambda l^{4})$
Diffie-Hellman | ✗ | 4 | 18 | $\mathcal{O}(\lambda l^{4})$
Table 1: The table of resource estimations for each type of (N)TCF function
that may be used. Here H.C. means hardcore bit. The number of quantum-
classical interleaving refers to the instances where the prover performs a
constant-depth quantum circuit followed by a classical computation. This is
done, for instance, in the preparation of GHZ states as well as when it
responds to one of the verifier’s challenges. Depth refers to the total number
of layers of quantum gates that the prover has to perform. Width refers to the
width of the quantum circuits the prover has to implement. Here, $\lambda$
denotes the security parameter and $l$ is the size of the branching program
implementing the randomized encoding, as described in Appendix A.

####  3.3.1 Quantum depth and quantum-classical interleavings

In this subsection we explain the overall quantum depth that the prover has to
perform in our modified proofs of quantumness. Depth here represents the
number of layers of quantum gates or measurements (as described in Section 2)
that the prover will perform throughout the protocol, in the worst case. As
mentioned, the prover’s operations consist of alternating between constant-
depth quantum circuits and log-depth classical computation. This latter step
we referred to as a quantum-classical interleaving.

For the NTCF-based protocol which uses LWE, the total quantum depth is 14 and
3 quantum-classical interleavings are performed, whereas for the TCF-based
approaches the depth is 17 and the number of interleavings is 4. Let us
explain where these numbers come from:

  1. 1.

Preparation of GHZ states. As mentioned, we prepare GHZ states by interleaving
a constant depth quantum circuit with a log-depth classical computation,
followed by another quantum circuit. The exact steps are outlined in [WKST19],
while here we just summarize the gates performed in each step. The procedure
starts with a layer of Hadamard gates followed by two layers of $CNOT$ gates.
Some of the qubits are then measured in the computational basis. The remaining
qubits will collapse to a poor man’s cat state, while the measured qubits
contain the parity information for that state. To “correct” the state to a GHZ
state, the parity information is used to compute a Pauli-$X$ correction. This
is one quantum-classical interleaving. The final quantum layer consists of
Pauli-$X$ gates. Thus, the total depth will be 5 and we have 1 quantum-
classical interleaving. This applies to all GHZ states, as they can be
prepared in parallel.

  2. 2.

Evaluation of the randomized encoded function. As illustrated can see in
Figure 5, the classical circuit for a randomized encoding has depth 3. In the
quantum case, the AND gates are implemented by Toffoli gates and the XOR gate
is a $CNOT$. As the quantum gates are reversible, one needs to _uncompute_ any
auxiliary results and so the quantum depth will be double that of the
classical circuit. Hence, for this step the quantum depth is 6 and there are
no quantum-classical interleavings.

  3. 3.

Measurement of the $\mathsf{Y}$ register. Measuring the image register
requires a layer of computational basis measurements and so the depth is 1.
The results are read out and sent to the verifier, which we count as 1
quantum-classical interleaving.

  4. 4.

Preimage test or equation/Bell test. If a preimage test is performed, the
prover only needs to measure the $\mathsf{X}$ register in the computational
basis and report the result. This counts as depth 1 and 1 interleaving. In the
NTCF protocol, if an equation test is performed, then the prover is expected
to apply a layer of Hadamard gates to the $\mathsf{X}$ register and measure
them. This counts as depth 2 and 1 interleaving. In the TCF protocol, when the
computational Bell test is performed, the prover’s operations (as outlined in
Subsection 3.1) will consist of a layer of $CZ$ gates, a layer of Hadamard
gates together with a computational basis measurement, a classical computation
and reporting the results to the verifier, a Pauli-$Z$ operation, a rotation
gate and finally another measurement and reporting the results to the
verifier. This counts as depth 6 and 2 interleavings.

We can see that for the NTCF-based protocol the worst-case depth is
$5+6+1+2=14$ and the number of interleavings is $1+0+1+1=3$. For the TCF-based
one, the depth is $5+6+1+6=18$ and the number of interleavings is $1+0+1+2=4$.

####  3.3.2 Circuit width

The constant-depth versions of the proof of quantumness protocols require
larger numbers of qubits than the original version. As explained, most of this
is due to the use of GHZ states, which effectively copy the input and allow us
to apply a constant depth circuit with bounded fan-out gates. That circuit is
a randomized encoding of the original TCF. Following the construction of
randomized encodings from [AIK04] and described in Appendix A, the width of
the constant-depth circuit will depend on the size of the branching program
used to evaluate the original function. In Appendix A we explain how, as a
result of _Barrington’s theorem_ , the size of this branching program is
exponential in the depth of the original TCF. As all TCFs considered here can
be evaluated in logarithmic depth, the resulting branching programs will have
sizes polynomial in the security parameter $\lambda$. Giving a precise account
of the size of the branching program, as a function of $\lambda$, for each
TCF, is beyond the scope of this paper. Instead, we find in Appendix A that
the overall circuit width for the prover’s quantum circuit is
$\mathcal{O}(\lambda l^{4})$, where $l$ is the size of the branching program
used to evaluate the TCF. The $\lambda$ factor comes from having to repeat the
branching program construction in parallel $\mathcal{O}(\lambda)$ times. This
is because one branching program computes a single output bit of the TCF and
so one has to consider a different branching program (of the same size) for
each output bit.

As a rough estimate, we can relate the width to the security parameter for the
LWE-based NTCF of [Mah18, BCM+18]. There we know from [GH20] that the
functions can be evaluated in depth $\propto 4\log{\lambda}$. From
Barrington’s theorem, the size $l$ of the corresponding branching program is
on the order of $\lambda^{8}$. As the width is $\mathcal{O}(\lambda l^{4})$,
we find that the prover requires $\mathcal{O}(\lambda^{33})$ qubits. This is a
discouraging result for the purposes of implementing these protocols on near-
term devices. However, it should be noted that this was merely a rough
calculation based on existing asymptotic estimates. We conjecture that these
estimates are not optimal and can be improved with a tighter analysis, better
circuit implementations and more compact branching programs. Additionally, for
a fixed-size implementation (say $\lambda=50$), it is likely that additional
optimizations are possible that could further reduce the number of required
qubits.

## References

  * [AA11] Scott Aaronson and Alex Arkhipov.  The computational complexity of linear optics.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333–342, 2011.
  * [AAA+19] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Eli Arbel, Arijit02, Abraham Asfaw, Artur Avkhadiev, Carlos Azaustre, AzizNgoueya, Abhik Banerjee, Aman Bansal, Panagiotis Barkoutsos, et al.  Qiskit: An open-source framework for quantum computing, 2019.
  * [AAB+19] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [AB09] Sanjeev Arora and Boaz Barak.  Computational complexity: a modern approach.  Cambridge University Press, 2009.
  * [ACGH20] Gorjan Alagic, Andrew M Childs, Alex B Grilo, and Shih-Han Hung.  Non-interactive classical verification of quantum computation.  In Theory of Cryptography Conference, pages 153–180. Springer, 2020\.
  * [AG19] Scott Aaronson and Sam Gunn.  On the classical hardness of spoofing linear cross-entropy benchmarking.  arXiv preprint arXiv:1910.12085, 2019.
  * [AIK04] B. Applebaum, Y. Ishai, and E. Kushilevitz.  Cryptography in $\textsf{NC}^{0}$.  In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 166–175, 2004.
  * [Bar89] David A Barrington.  Bounded-width polynomial-size branching programs recognize exactly those languages in nc1.  Journal of Computer and System Sciences, 38(1):150–164, 1989.
  * [BCM+18] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick.  A cryptographic test of quantumness and certifiable randomness from a single quantum device.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 320–331. IEEE, 2018.
  * [BFNV19] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani.  On the complexity and verification of quantum random circuit sampling.  Nature Physics, 15(2):159–163, Feb 2019.
  * [BIS+18] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, 14(6):595–600, 2018.
  * [BKVV20] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick.  Simpler proofs of quantumness.  arXiv preprint arXiv:2005.04826, 2020.
  * [CCKW19] Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden.  Qfactory: classically-instructed remote secret qubits preparation.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 615–645. Springer, 2019.
  * [CCY20] Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa.  Classical verification of quantum computations with efficient verifier.  In Theory of Cryptography Conference, pages 181–206. Springer, 2020\.
  * [CHSH69] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt.  Proposed experiment to test local hidden-variable theories.  Physical review letters, 23(15):880, 1969.
  * [CW00] Richard Cleve and John Watrous.  Fast parallel circuits for the quantum fourier transform.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 526–536. IEEE, 2000.
  * [FMMC12] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland.  Surface codes: Towards practical large-scale quantum computation.  Physical Review A, 86(3):032324, 2012.
  * [GE21] Craig Gidney and Martin Ekerå.  How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits.  Quantum, 5:433, 2021.
  * [GH20] Alexandru Gheorghiu and Matty J Hoban.  Estimating the entropy of shallow circuit outputs is hard.  arXiv preprint arXiv:2002.12814, 2020.
  * [GV19] Alexandru Gheorghiu and Thomas Vidick.  Computationally-secure and composable remote state preparation.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1024–1033. IEEE, 2019.
  * [HG21] Shuichi Hirahara and François Le Gall.  Test of quantumness with small-depth quantum circuits.  arXiv preprint arXiv:2105.05500, 2021.
  * [HM17] Aram W Harrow and Ashley Montanaro.  Quantum computational supremacy.  Nature, 549(7671):203–209, 2017.
  * [HMNY21] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa.  Quantum encryption with certified deletion, revisited: Public key, attribute-based, and classical communication.  arXiv preprint arXiv:2105.05393, 2021.
  * [HZN+20] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, et al.  Classical simulation of quantum supremacy circuits.  arXiv preprint arXiv:2005.06787, 2020.
  * [KM19] Gregory D Kahanamoku-Meyer.  Forging quantum data: classically defeating an iqp-based quantum test.  arXiv preprint arXiv:1912.05547, 2019.
  * [KMCVY21] Gregory D Kahanamoku-Meyer, Soonwon Choi, Umesh V Vazirani, and Norman Y Yao.  Classically-verifiable quantum advantage from a computational bell test.  arXiv preprint arXiv:2104.00687, 2021.
  * [KNY20] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Secure software leasing from standard assumptions.  arXiv preprint arXiv:2010.11186, 2020.
  * [LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.  On ideal lattices and learning with errors over rings.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 1–23. Springer, 2010.
  * [Mah18] Urmila Mahadev.  Classical verification of quantum computations.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267. IEEE, 2018.
  * [MDCAF20] Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman.  Device-independent quantum key distribution from computational assumptions.  arXiv preprint arXiv:2010.04175, 2020.
  * [MV21] Tony Metger and Thomas Vidick.  Self-testing of a single quantum device under computational assumptions.  In 12th Innovations in Theoretical Computer Science (ITCS), 2021\.
  * [NC02] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.
  * [PR21] AS Popova and AN Rubtsov.  Cracking the quantum advantage threshold for gaussian boson sampling.  arXiv preprint arXiv:2106.01445, 2021.
  * [Pre18] John Preskill.  Quantum computing in the NISQ era and beyond.  Quantum, 2:79, 2018.
  * [Reg09] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  Journal of the ACM (JACM), 56(6):1–40, 2009.
  * [SB09] Dan Shepherd and Michael J Bremner.  Temporally unstructured quantum computation.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465(2105):1413–1439, 2009.
  * [Sho94] Peter W Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994.
  * [VZ20] Thomas Vidick and Tina Zhang.  Classical zero-knowledge arguments for quantum computations.  Quantum, 4:266, 2020.
  * [WBD+19] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, J-S Chen, NC Pisenti, M Chmielewski, C Collins, et al.  Benchmarking an 11-qubit quantum computer.  Nature communications, 10(1):1–6, 2019.
  * [WKST19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal.  Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 515–526, 2019.
  * [Yao86] Andrew Chi-Chih Yao.  How to generate and exchange secrets.  In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162–167. IEEE, 1986.
  * [ZNR+21] Daiwei Zhu, Crystal Noel, Andrew Risinger, Laird Egan, Debopriyo Biswas, Qingfeng Wang, Yunseong Nam, Gregory Meyer, Umesh Vazirani, Norman Yao, Alexandru Gheorghiu, Laura Lewis, Thomas Vidick, Marko Cetina, and Christopher Monroe.  Demonstration of interactive protocols for classically-verifiable quantum advantage.  In preparation, 2021.
  * [ZWD+20] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al.  Quantum computational advantage using photons.  Science, 370(6523):1460–1463, 2020.

##  Appendix A Randomized encoding construction from [AIK04]

The construction of randomized encodings from [AIK04] is based on _branching
programs_. We are only interested in mod-2 branching programs, which we define
here:

######  Definition A.1 (Branching programs [AIK04]).

A branching program (BP) is defined by a tuple $BP=(G,\phi,s,t)$ where
$G=(V,E)$ is a directed acyclic graph, $\phi$ is a labeling function assigning
each edge either a positive literal $x_{i}$ or a negative literal
$\neg{x_{i}}$. An input binary vector $\vec{w}$ determines a subgraph $G_{w}$
where an edge labeled as $x_{i}$ is preserved if and only if $w_{i}=1$. In a
(counting) mod-2 BP, the BP computes the number of paths from $s$ to $t$
modulo 2. The size, $l$, of a BP is defined as the number of vertices, $|V|$.

As an example, Figure 4 shows a mod-2 branching program of size $l=4$ and
having three inputs $x=(x_{0},x_{1},x_{2})$.

$ⓢ$$ⓣ$$①$$②$$1$$x_{0}$$x_{1}$$\neg{x}_{1}$$x_{2}$ Figure 4: This size-4 mod-2
branching program consists of 5 edges whose connectivity is decided by the
value of the input bits. Note that $\neg{x}_{1}$ means that this edge is
available if and only if $x_{1}=0$. As an example, when the input
$x=(x_{0},x_{1},x_{2})=(0,1,1)$, there is only one path from $s$ to $t$ which
is $ⓢ-①-②-ⓣ$. Thus the output of this mod-2 BP will be 1.

We now state one of the most important results concerning branching programs,
due to Barrington:

######  Theorem A.1 (Barrington’s theorem [Bar89]).

If $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ can be computed by a circuit of depth
$d$, then it can be computed by a branching program of width 5 and length
$\mathcal{O}(4^{d})$.

The above theorem ensures that the log-depth (N)TCFs used in proof of
quantumness protocols can be transformed into polynomial-size branching
program. Given that branching programs output a single bit, this construction
has to be performed for every output bit of a (N)TCF.

A size-$l$ mod-2 BP for a binary function $f$ can be represented by an
adjacency matrix since BPs are directed acyclic graphs. Let $A(x)$ denote the
$l\times l$ adjacency matrix of a BP with input $x$. We also denote as $L(x)$
the $(l-1)\times(l-1)$ submatrix of $A(x)-I$ obtained by deleting the first
column and the last row. It turns out that the following fact holds:

######  Lemma A.1 ([AIK04]).

$f(x)=\det(L(x))\;mod\;2.$

This lemma is the basis for constructing a randomized encoding for $f$. The
goal will be to “garble” $L(x)$ through products with certain random matrices.
The garbling should be done in such a way that the determinant of the
resulting matrix matches that of $L(x)$, thus preserving the correctness of
the construction.

To that end, let $r^{(1)}\leftarrow_{R}\\{0,1\\}^{{l-1\choose 2}}$ and
$r^{(2)}\leftarrow_{R}\\{0,1\\}^{l-2}$. Use these to construct matrices
$R^{(1)}$ and $R^{(2)}$ of dimensions $(l-1)\times(l-1)$. Both matrices have
all diagonal elements equal to $1$. The right upper-diagonal elements of
$R^{(1)}$ (that is, the entries $R^{(1)}_{i,j}$ with $j>i$) are filled with
the entries of $r^{(1)}$. The last column of $R^{(2)}$, except for the last
element, (that is, the entries $R^{(2)}_{i,l-1}$, $1\leq i\leq l-2$) is filled
with the elements of $r^{(2)}$. All other entries of $R^{(1)}$ and $R^{(2)}$
are $0$. The following can be shown:

######  Lemma A.2 ([AIK04]).

$\det(L(x))=\det(R^{(1)}L(x)R^{(2)})$

This is not too difficult to see, as both $R^{(1)}$ and $R^{(2)}$ have
determinant $1$. One now defines the randomized encoding
$\tilde{f}(x,r^{(1)},r^{(2)})=R^{(1)}L(x)R^{(2)}$. It follows that:

######  Lemma A.3 ([AIK04]).

$\tilde{f}$ is a perfect randomized encoding of $f$.

By construction, every entry of $\tilde{f}$ is a degree-$3$ polynomial in its
input variables. However, computing this function (i.e. computing every matrix
entry of $R^{(1)}L(x)R^{(2)}$) cannot be done in constant-depth. The reason is
that some of the input variables are involved in a linear number of monomials
of the output. To compute the function in constant depth, it must be that each
input variable appears in only a constant number of monomials. The authors of
[AIK04] remedy this by considering a randomized encoding for $\tilde{f}$.
Before doing so, note that

######  Lemma A.4 ([AIK04]).

The composition of perfect randomized encodings is still a perfect randomized
encoding of the original function.

Thus, a randomized encoding for $\tilde{f}$ will also be a randomized encoding
for $f$. Denote the $i,j$ entry of $\tilde{f}$ as $\tilde{f}_{i,j}$. We can
see that

$\tilde{f}_{i,j}(x,r^{(1)},r^{(2)})=T_{1}(x,r^{(1)},r^{(2)})\oplus
T_{2}(x,r^{(1)},r^{(2)})\oplus...\oplus T_{k}(x,r^{(1)},r^{(2)})$ (12)

where each $T_{m}$ is a monomial in the input variables. Finally, define
$\hat{f}$ as

$\hat{f}_{i,j}(x,r^{(1)},r^{(2)},r,r^{\prime})=(T_{1}\oplus r_{1},T_{2}\oplus
r_{2},...,T_{k}\oplus r_{k},r_{1}\oplus r_{1}^{\prime},r_{1}^{\prime}\oplus
r_{2}\oplus r_{2}^{\prime},...,r_{k-1}^{\prime}\oplus r_{k})$ (13)

where $r$ and $r^{\prime}$ are newly introduced vectors of random bits. Note
that adding all entries in 13 results in the summation from Equation 12. Thus,
$\hat{f}$ contains all of the information required to compute $\tilde{f}$ and
moreover,

######  Lemma A.5 ([AIK04]).

$\hat{f}$ is a perfect randomized encoding of $f$ with output locality $4$.

Here, output locality $4$ means that each output bit depends on at most $4$
input bits, which immediately implies that the function can be evaluated in
constant depth. The classical circuit computing an entry of $\hat{f}$ is shown
in Figure 5. Detailed proofs of all these results can be found in [AIK04].

$r^{(1)}_{i}$$x_{j}$$r^{(2)}_{k}$$r_{m}$ANDANDXOR$\hat{f}_{m}(x)$ Figure 5:
The circuit for evaluating each entry in the randomized encoding $\hat{f}$.
The circuit shown here computes the $m$’th entry, with $m\leq k$, consisting
of the monomial $r_{i}^{(1)}x_{j}r_{k}^{(2)}$ xored with $r_{m}$. For the
entries with $m>k$, note that a single XOR gate is required.

##  Appendix B Reconstruction of randomness

In our modified proofs of quantumness, the prover is instructed to evaluate a
randomized encoding of a TCF. The verifier must still be able to use the
trapdoor in order to invert an output of the randomized encoding. As mentioned
in Subsection 3.2, this is true provided the encoding satisfies the randomness
reconstruction property. Here we prove this fact for the construction of
[AIK04].

###### Proof of Lemma 2.1.

We would like to show that given an instance of
$\hat{f}_{i,j}(x,r^{(1)},r^{(2)},r,r^{\prime})$, as shown in Equation 13, as
well as $x$, it is possible to efficiently recover the randomness
$r^{(1)},r^{(2)},r,r^{\prime}$. First note that if the terms $T_{k}$ were
known as well as $r^{(1)},r^{(2)}$, it is straightforward to recover $r$ and
$r^{\prime}$. We will therefore focus on that case. From Equation 13 it is
possible to efficiently compute the result of Equation 12, since $\hat{f}$ is
a randomized encoding of $\bar{f}$: simply xor all the terms in Equation 13.
We will then focus on randomness reconstruction for $\bar{f}$ as that will
then yield randomness reconstruction for $\hat{f}$.

Denote as $M=\tilde{f}(x,r^{(1)},r^{(2)})=R^{(1)}L(x)R^{(2)}$. Given $M$ and
$x$ we wish to recover $r^{(1)},r^{(2)}$. This boils down to solving a
specific quadratic system of equations. To see why, take $l=4$ as an example,

$M=R^{(1)}L(x)R^{(2)}=\left[\begin{matrix}1&r^{(1)}_{1}&r^{(1)}_{3}\\\
0&1&r^{(1)}_{2}\\\
0&0&1\end{matrix}\right]\left[\begin{matrix}x_{1}&x_{4}&x_{6}\\\
-1&x_{2}&x_{5}\\\
0&-1&x_{3}\end{matrix}\right]\left[\begin{matrix}1&0&r^{(2)}_{1}\\\
0&1&r^{(2)}_{2}\\\ 0&0&1\end{matrix}\right]$

$M=\left[\begin{matrix}x_{1}-r^{(1)}_{1}&r^{(1)}_{1}x_{2}-r^{(1)}_{3}+x_{4}&r^{(2)}_{1}(x_{1}-r^{(1)}_{1})+r^{(2)}_{2}(r^{(1)}_{1}x_{2}-r^{(1)}_{3}+x_{4})+r^{(1)}_{3}x_{3}+r^{(1)}_{1}x_{5}+x_{6}\\\
-1&x_{2}-r^{(1)}_{2}&r^{(2)}_{2}(x_{2}-r^{(1)}_{2})+r^{(1)}_{2}x_{3}-r^{(2)}_{1}+x_{5}\\\
0&-1&x_{3}-r^{(2)}_{2}\end{matrix}\right]$

Note that the main diagonal of $M$ is just a linear system of $3$ equations
with $3$ unknowns. It can therefore be solved, yielding $r_{1}^{(1)}$,
$r_{2}^{(1)}$ and $r_{2}^{(2)}$. Plugging these values into the second
diagonal (the one above the main diagonal), yields another system of linear
equations with an equal number of unknowns. By repeating the process and
solving all of these systems, all bits in $r^{(1)}$ and $r^{(2)}$ are
recovered.

We now show that this strategy works for arbitrary $l$. Start by observing
that:

$\left\\{\begin{array}[]{lr}R^{(1)}_{i,j}=1,&i=j\\\
R^{(1)}_{i,j}=0,&i>j,\end{array}\right.$

$\left\\{\begin{array}[]{lr}L_{i,j}=-1,&i=j+1\\\
L_{i,j}=0,&i>j+1,\end{array}\right.$

$\left\\{\begin{array}[]{lr}R^{(2)}_{i,j}=1,&i=j\\\
R^{(2)}_{i,j}=0,&(i>j)\vee(i<j<l-2).\end{array}\right.$

The entries of $M$ can then be expressed as:

$M_{i,j}=\sum_{k_{1},k_{2}}R^{(1)}_{i,k_{1}}L_{k_{1},k_{2}}R^{(2)}_{k_{2},j}.$

Consider the entries on the main diagonal, excluding the last element:

$M_{i,i}=\sum_{k_{1}}R^{(1)}_{i,k_{1}}L_{k_{1},i}=R^{(1)}_{i,i}L_{i,i}+\sum_{k_{1}>i}R^{(1)}_{i,k_{1}}L_{k_{1},i}=L_{i,i}-R^{(1)}_{i,i+1}$

with $i<l-2$ and where $R^{(1)}_{i,i+1}$ are the elements of the second
diagonal of $R^{(1)}$ and the $L_{i,i}$’s are already known (as they only
involve entries of $x$). This gives us a simple linear system which we can
solve to recover the $R^{(1)}_{i,i+1}$ values. Then, for $i=l-2$:

$M_{l-2,l-2}=\sum_{k_{2}}L_{l-2,k_{2}}R^{(2)}_{k_{2},l-2}=L_{l-2,l-3}R^{(2)}_{l-3,l-2}+L_{l-2,l-2}R^{(2)}_{l-2,l-2}=R^{(2)}_{l-3,l-2}+L_{l-2,l-2}.$

From this we also recover $R^{(2)}_{l-3,l-2}$, i.e. the last entry in
$r^{(2)}$. Note that the unknowns here consisted of the entries in the second
diagonal of $R^{(1)}$ and the last element of $r^{(2)}$. This matches the
number of equations and so all values could be recovered.

We now claim that the $k$’th diagonal of $M$ is a linear system which depends
_only_ on the $k+1$ diagonal of $R^{(1)}$ and the $k$’th last element of
$r^{(2)}$ given the solutions to the previous $k-1$ diagonals of $M$. Writing
out the elements, we have:

$M_{i,i+j}=\sum_{k_{1},k_{2}}R^{(1)}_{i,k_{1}}L_{k_{1},k_{2}}R^{(2)}_{k_{2},i+j}.$

with $j=k-1$. For $i+j\neq l-2$:

$M_{i,i+j}=\sum_{k_{1}}R^{(1)}_{i,k_{1}}L_{k_{1},i+j}=-R^{(1)}_{i,i+j+1}+L_{i,i+j}+\sum_{i<k_{1}<i+j+1}R^{(1)}_{i,k_{1}}L_{k_{1},i+j}$

where the first term is from the $(k+1)$’th diagonal of $R^{(1)}$ and the
remaining terms are known from solving the equations for the previous
diagonals. Thus, we have a linear system, which we can solve, with unknowns
comprising the elements of the $(k+1)$’th diagonal of $R^{(1)}$.

For $i+j=l-2$:

$M_{l-2-j,l-2}=\sum_{k_{2}=l-2-j-1}^{l-2}L_{l-2-j,k_{2}}R^{(2)}_{k_{2},l-2}+\sum_{k_{1}=l-2-j+1}^{l-2}R^{(1)}_{l-2-j,k_{1}}\sum_{k_{2}=k_{1}-1}^{l-2}L_{k_{1},k_{2}}R^{(2)}_{k_{2},l-2}.$

The first term is a linear combination of the last $k+1$ entries of $R^{(2)}$,
i.e. the last $k$ elements of $r^{(2)}$, and only the $k$’th element is
unknown. The remaining terms are known from solving the systems corresponding
to the previous diagonals.

We can therefore proceed in this fashion, starting from the first diagonal of
$M$ and going upwards solving all systems of linear equations and thus
recovering all values of $r^{(1)}$ and $r^{(2)}$. This procedure is clearly
efficient and we have shown that it is also correct. To conclude the proof, we
also need to make sure that there is a unique solution to the system. This is
guaranteed by the unique randomness property of randomized encoding (Theorem
2.5). ∎