INTRODUCTION

High depth circuits are believed to be strictly more powerful than low depth circuits, in the sense that having deeper circuits allows one to solve a larger set of problems. Indeed, this is a well established fact for both classical and quantum circuits of depth sub-logarithmic in the size of the input [5,6,30,32,41]. However, for circuits of (poly)logarithmic depth and general polynomial depth, proving any sort of unconditional separation is challenging [39]. In fact, there is not even an unconditional proof that the set of problems that can be solved by polylog-depth classical circuits, NC, is a strict subset of the set of problems solvable by poly-depth classical circuits, P (or BPP when allowing for randomness). The same is believed to be the case for the quantum analogues of these classes, QNC and BQP, respectively. Nevertheless, the strict containments NC ⊊ P and QNC ⊊ BQP are known to hold in the oracle setting and, in particular, relative to a random oracle [35]. 1 This is a strong indication that there are problems in P (BQP) which cannot be parallelised so as to be solvable in NC (QNC). Under the random oracle heuristic, by replacing the random oracle with a cryptographic hash function, one can even provide concrete instantiations of such problems. A further indication of the separation between low and high depth computations is provided by certain inherently sequential cryptographic constructions such as time-lock puzzles and verifiable delay functions [16,40].

The study of circuit depth can also yield insights into the subtle relationship between quantum and classical computation by considering hybrid circuit models that combine quantum and classical computation [11,21,28,31]. In this setting, one can ask the question: how powerful are poly-depth classical circuits, when augmented with polylog-depth quantum circuits? Could it be the case that interspersing BPP with QNC computations captures the full power of BQP computations? Jozsa famously conjectured that the answer is yes [33]. Indeed, there is some evidence to support this conjecture, as the quantum Fourier transform, a central building block for many quantum algorithms, was shown to be implementable with log-depth quantum circuits [25]. This also implies that Shor's algorithm can be performed by a BPP QNC machine, a polynomialtime classical computer having the ability to invoke a (poly)log depth quantum computer. 2 Moreover, in the oracle setting, a number of problems yielding exponential separations between quantum and classical computation require only constant quantum-depth to solve, providing further support for Jozsa's conjecture [1,3,42].

Despite the evidence in support of Jozsa's conjecture, it was recently shown that, in the oracle setting, the conjecture is false [21,28]. Specifically, the results of [21] (hereafter referred to as CCL) and [28] (hereafter referred to as CM) considered two ways of interspersing poly-depth classical computation with 𝑑-depth quantum computation. The first is BPP QNC d , denoting problems solvable by a BPP machine that can invoke 𝑑-depth quantum circuits (whose outputs are measured in the computational basis). The second, QNC d BPP , denotes problems solvable by a 𝑑-depth quantum circuit that can invoke a BPP machine at each layer in the computation. 3 Later, borrowing terminology from [11,21], we will refer to the former circuit model as CQ d and the latter as QC d . However, for the purposes of this introduction, we will stick to the more familiar notation using complexity classes. Intuitively, BPP QNC d captures the setting of a classical computer that can invoke a 𝑑-depth quantum computer several times. Examples of this include quantum machine learning algorithms such as VQE or QAOA [29,37], though as mentioned, Shor's algorithm is also of this type. On the other hand, QNC d BPP captures a 𝑑-depth measurement-based quantum computation [18,38], where intermediate measurements are performed after each layer in the quantum computation. The outcomes of those measurements are processed by a poly-depth classical computation and the results are "fed" into the next quantum layer. CCL and CM showed that there exists an oracle relative to which BPP QNC d ∪ QNC d BPP ⊊ BQP, for any 𝑑 = polylog(𝑛), with 𝑛 denoting the size of the input. Notably, each work considered a different oracle for showing the separation. For CM, the oracle is the same one as for Childs' glued trees problem [23]. For CCL, the oracle is a modified version of the oracle used for Simon's problem [42], where the modification involves performing a sequence of permutations, allowing them to enforce high quantum depth.

CCL and CM were the first results to provide a convincing counterpoint to Jozsa's conjecture. However, the main drawback of the CCL and CM results is that they are relative to oracles that are highly structured and it is unclear if they can be explicitly instantiated based on some cryptographic assumptions. Indeed, in his "Ten Semi-Grand Challenges for Quantum Computing Theory", Aaronson emphasizes this important distinction, and asks whether there is some instantiatable function that separates the hybrid models from BQP. In this work, we resolve Aaronson's question in the affirmative for the search variants of these classes.

In contrast to separations between different models of computation running in polynomial time, such as P and NP or BPP and BQP, where several plausible candidates exist for separating the classes, the case for depth separations is much more subtle. As was already observed in [14], no standard cryptographic assumption is known to yield a separation between NC and P. The best candidates for such a separation are sequential compositions of hash functions (under the random oracle heuristic) as shown in [35] and the iterated exponentiation scheme of Rivest, Shamir and Wagner [40]. Thus, informally, the best we could hope for in terms of an instantiatable separation between the hybrid models and BQP is a separation in the random oracle model which could then be instantiated using cryptographic hash functions. We note that while there are known counterexamples to the random oracle heuristic [20], these are generally contrived and do not apply to protocols where the random oracle heuristic has been used in practice (and, in particular, are not known to apply to the setting we consider here). Indeed, it has been shown that certain protocols proven secure with respect to a random oracle can also be concretely instantiated using correlation intractable hash functions [19,34]. We also note that separating the hybrid models from BPP, rather than BQP, in the random oracle model already follows from Aaronson's Fourier Fishing problem [1]. That problem, of sampling from the Fourier spectrum of the random oracle, is solvable in 4 QNC but not in BPP. Implicitly, this means that the hybrid search classes BPP QNC and QNC BPP are strictly larger than BPP relative to a random oracle.

Our work is concerned not only with separations between the hybrid models and BQP in the random oracle model, but also with giving a comprehensive characterization of quantum depth in that model. To that end, we first re-examine Jozsa's conjecture and argue that the natural class associated to "𝑑-depth quantum computation combined with polynomial-time classical computation" is not BPP QNC d ∪ QNC d BPP , but BPP QNC d BPP . This is because, if one has the ability to perform QNC d BPP computations, certainly it should also be possible to repeat this polynomiallymany times as well as perform classical processing in between the runs. Note that BPP QNC d ∪ QNC d BPP ⊆ BPP QNC d BPP (in fact, we show strict containment). The separation we then obtain, relative to a random oracle, is BPP QNC d BPP ⊊ BQP, for any fixed 𝑑 ≤ poly(𝑛). Going beyond this separation, we also show that the hybrid models BPP QNC d and QNC d BPP are separate from each other in both directions, relative to a random oracle (in fact, we show that BPP QNC O(1) ⊈ QNC d BPP and QNC BPP O(1) ⊈ BPP QNC d ), illustrating the subtle interplay between short-depth quantum computation and classical computation. Lastly, by combining the techniques that we develop with previous results on proof of quantumness protocols, we obtain proof of quantum depth protocols-protocols in which a BPP verifier, exchanging 2 messagesfoot_4 with an untrusted quantum prover, can certify that the prover has the ability to perform quantum computations of a minimum depth.

Main Results

We now state our results more formally and provide some intuition about the proofs. We abuse the notation slightly and use the

(a) Illustration of QNC 𝑑 and QNC BPP 𝑑 circuits. standard decision complexity class names to refer to their search variants.

1.1.1 Lower Bounds on Quantum Depth. We first show the following separation.

Theorem 1 (informal). Fix any function 𝑑 ≤ poly(𝑛). Then, relative to a random oracle, 6 it holds that BPP QNC BPP 𝑑 ⊊ BQP.

As motivated earlier, we take the class BPP QNC d BPP to capture computations performed by a combination of 𝑑-depth quantum computation and polynomial-depth classical computation. The interpretation of our result is that BPP QNC d BPP can be separated from BQP using the least structured oracle possible, a random oracle. Together with the (quantum) random oracle heuristic, by instantiating the oracle with a cryptographic hash function like SHA-2 or SHA-3, this yields the first plausible instantiation of a problem solvable in BQP but not in BPP QNC d BPP . This provides a resolution to Aaronson's challenge. The main technical innovation that allows us to achieve the separation is a general lifting lemma that takes any problem separating BPP from BQP in the random oracle model, which additionally satisfies a property that we call classical query soundness, and constructs a problem separating BPP QNC d BPP and BQP. We show that several known problems satisfy this property. Our lifting lemma is inspired by [21], and crucially extends their analysis beyond highly structured oracles. We describe this lifting lemma more precisely in Subsection 1.2.1.

1.1.2 Proofs of Quantum Depth. It is natural to wonder whether Theorem 1 yields an efficient test to certify quantum depth, i.e. a proof of quantum depth. A proof of quantum depth is a more fine-grained version of a proof of quantumness: rather than distinguishing between quantum and classical computation, a proof of quantum depth protocol can distinguish between provers having large or small quantum depth. We show that instantiating our lifting lemma with a problem whose solution is efficiently verifiable immediately yields a proof of quantum depth. One such problem 7is due to Yamakawa and Zhandry [43]. More precisely, we have the following.

Theorem 2 (informal). Let 𝑛 be the security parameter and fix any function 𝑑 ≤ poly(𝑛). In the random oracle model, there exists a two-message protocol between a poly-time classical verifier and a quantum prover such that,

• Completeness: There is a BQP prover which makes the verifier accept with probability at least 1 -negl(𝑛) • Soundness: No malicious BPP QNC BPP 𝑑 prover can make the verifier accept with probability greater than negl(𝑛).

We emphasise that considering protocols with more than two messages leads to difficulties in formalising the notion of quantum depth. For instance, one can construct protocols where the prover is forced to hold 𝑟 single qubit states and subsequently measures them. Information about the basis in which to measure each of these qubits is sent one at a time by the verifier over 𝑟 messages (the verifier waits for the response to each measurement, before sending the next basis). The measurement results are used by the verifier to ensure soundness (each qubit is measured in its preparation basis and so the outcomes are completely determined). It is not hard to show that if the prover measures these qubits without knowing the measurement basis, it cannot succeed except with negligible probability. If one attempts to model the prover as a BPP QNC 𝑑 or QNC BPP 𝑑 circuit, then, because of the delay between messages, it appears that 𝑑 ≥ 𝑟 is necessary. However, this can be seen as an artefact of the modelling choice: in practice, the prover only needs 𝑑 single qubit quantum computers with quantum depth 1 where the last gate can be delayed until the appropriate message is received in order to pass the test. Essentially, this approach only tests the prover's ability to maintain the coherence of the qubits it received, without actually testing the depth of the circuit it has to perform. In Subsection 1.3, we discuss a possible resolution that captures quantum depth in the interactive setting.

1.1.3 Tighter Bounds. While Theorem 1 establishes that BPP QNC BPP 𝑑 does not capture the computational power of BQP for any fixed 𝑑 ≤ poly(𝑛), it is not a priori clear if, for instance,

BPP QNC BPP

2𝑑+O (1) is strictly larger than BPP QNC BPP 𝑑 . Indeed, we show that the answer is affirmative.

Theorem 3 (informal). Fix any function 𝑑 ≤ poly(𝑛). Relative to a random oracle, it holds that 8 BPP QNC BPP 𝑑 ⊊ BPP QNC BPP 2𝑑+O (1) .

Formally, the theorems treat a call to the quantum random oracle as a depth-1 quantum gate. In practice, if instead the gate requires depth ℓ, then 𝑑 can be replaced by 𝑑ℓ. We remark that there exist hash functions that are thought to be quantum-secure which require only logarithmic depth to evaluate [7,36]. Further, there is reason to believe that such hash functions could also be constructed in ℓ = O(1) depth. In particular, if one is only concerned with specific cryptographic properties (such as collision resistance), then generic constructions are known which convert log-depth hash functions into ones that require only constant depth [9]. 1.1.4 Separations between Hybrid Quantum Depth Classes. While both BPP QNC and QNC BPP capture some notion of a hybrid between efficient classical computation and shallow quantum computation, the relationship between the two is not immediately clear. To get a slightly better intuition about the two models, one can think of BPP QNC as capturing an efficient computation that contains polynomially many shallow quantum circuits (separated by measurements and classical computation). On the other hand, one can think of QNC BPP as a single shallow quantum circuit, where one is allowed to make partial measurements of some of the wires, and choose the next gates adaptively. While it may not be surprising that there exist problems that can be solved in BPP QNC but not in QNC BPP , it turns out that the two classes are in fact incomparableeach class contains problems that the other does not, relative to a random oracle.

Theorem 4 (informal). Fix any function 𝑑 ≤ poly(𝑛). Relative to a random oracle, it holds that

The second separation is arguably more surprising. It says that, relative to a random oracle, there are problems that can be solved by a single shallow (in fact, constant-depth) quantum circuit with adaptive measurements but cannot be solved by circuits with polynomially many shallow quantum circuits without adaptive measurements. The problem that shows QNC BPP O(1) ⊈ BPP QNC 𝑑 is a variant of the proof of quantumness from [17]. The key technical innovation to achieve this separation is a theorem that characterises the 8 and more generally, that QNC 2𝑑+O(1) ⊈ BPP QNC BPP 𝑑 . structure of strategies that succeed in the protocol of [17] (this is discussed further in Section 1.2.2 ). This "structure theorem" crucially strengthens a similar theorem from [26], and may be of independent interest.

Finally, we examine the relationship between BPP

Main Technical Contributions

1.2.1 Lifting Lemmas. One of the main technical contributions of our work is to prove two general lifting lemmas. These lemmas take problems, defined relative to a random oracle, that are classically hard (in a stronger sense, defined next) and create new problems which are, in addition, hard for specific hybrid quantum depth classes. We describe these lifting lemmas a bit more precisely.

We say that a problem (defined with respect to the random oracle) is classical query sound if the following holds: any (potentially unbounded time) algorithm which makes only polynomially many classical queries to the random oracle (i.e. no superposition queries), succeeds at solving the problem with at most negligible probability. It turns out that the problem introduced by YZ satisfies this property. Another problem which satisfies this property is inspired by the proof of quantumness protocol defined by Brakerski et al. [17] (hereafter referred to as BKVV). 9 For such problems, the following holds.

Lemma 6 (informal, simplified).

There is a procedurefoot_8 that takes a classical query sound problem P ∈ BQP and creates a new problem

Observe that this lemma makes the problem hard for the most general notion of quantum depth we have considered. To give some intuition about how it is derived, suppose we have a problem P which is classical query sound and denote the random oracle as 𝐻 . Then P ′ = 𝑑-Rec[P] is the same problem, defined with respect to a sequential composition of 𝑑 + 1 random oracles,

In essence, we have substituted 𝐻 with H . This new problem will retain classical query soundness, as H behaves like a random oracle. But in addition, we have now made it so that querying H effectively requires depth 𝑑 + 1. As QNC 𝑑 has depth 𝑑, only the BPP parts

Fine grained advantage of quantum depth Table 2: (Simplified) Separations of hybrid quantum depth with respect to the random oracle. The results hold, not only for log but for any fixed polynomially-bounded function.

Result Physical Interpretation

BPP QNC O(1) ⊈ QNC BPP Running poly many constant depth quantum circuits (with no adaptive measurements) cannot be simulated by running a single log depth quantum circuit with adaptive measurements.

QNC BPP

O(1) ⊈ BPP QNC Running a single constant depth quantum circuit with adaptive measurements cannot be simulated by running poly many log depth quantum circuits (with no adaptive measurements).

BPP QNC BPP

O(1) ⊈ BPP QNC ∪ QNC BPP Evidence that it is not enough to consider BPP QNC and QNC BPP when studying quantum depth.

Running poly many constant depth quantum circuits with adaptive measurements cannot be simulated using either (a) poly many log depth quantum circuits with no adaptive measurements, or by (b) a single log depth quantum circuit with adaptive measurements.

of BPP QNC BPP 𝑑 will be able to query H . We can therefore simulate the BPP QNC BPP 𝑑 algorithm with an exponential time algorithm that is limited to polynomially many queries to H . By classical query soundness, such an algorithm cannot solve P ′ , which yields the desired result.

This was a simplified description of our result. In fact, we show a more refined statement that relates the depth required to solve P ′ to the depth required to solve P. In addition, arguing that H behaves like a random oracle and that QNC 𝑑 cannot query H requires a careful and more involved analysis. We use Lemma 6 to establish Theorem 3.

Our second lifting lemma produces a problem that is hard for QNC BPP 𝑑 , starting from a problem that satisfies what we call offline soundness. Consider a two phase algorithm consisting of: an online phase which is a poly-time classical algorithm with access to the random oracle followed by an offline phase which is an unbounded(time) algorithm with no access to the random oracle. Then, offline soundness requires that no such two phase algorithm succeeds at solving the problem with non-negligible probability. It turns out, again, that both YZ and BKVV satisfy this property.

Lemma 7 (informal).

There is a procedure 11 which takes a problem P ∈ QNC O(1) with offline soundness and creates a new problem P ′ := 𝑑-Ser[P] such that P ′ ∉ QNC BPP 𝑑 and P ′ ∈ BPP QNC O (1) .

Again, we actually show a slightly more general upper bound which depends on the depth required to solve P. We use Lemma 7 11 𝑑-Ser[ •] is meant to be short for 𝑑-Serial.

to establish BPP QNC O(1) ⊈ QNC BPP 𝑑 (first separation of Theorem 4). Establishing the other direction (QNC BPP O(1) ⊈ BPP QNC 𝑑 ) is quite involved and relies heavily on the structure of the problem we consider (explained below). Consequently, it is unclear whether there exists a general lifting lemma that yields hardness for BPP QNC 𝑑 .

We remark that, by using Lemma 7 to lift the problem that yields [17]. Another technical contribution of this work, which may be of independent interest, is to prove a theorem characterizing the structure of strategies that are successful at the proof of quantumness from [17]. This theorem is a crucial strengthening of a theorem from [26]. We employ this theorem as an intermediate step to establish the hybrid separation,

Recall, informally, that the proof of quantumness from [17] requires the prover to succeed at the following task: given access to a 2-to-1 function 𝑔, and to a random oracle 𝐻 with a one-bit output, find a pair (𝑦, 𝑟 ) such that

where {𝑥 0 , 𝑥 1 } = 𝑔 -1 (𝑦). This can be solved in QNC O(1) as follows:

(i) Evaluate 𝑔 on a uniform superposition of inputs, yielding 𝑥 |𝑥⟩ |𝑔(𝑥)⟩, (ii) Measure the image register obtaining some outcome 𝑦 and a state

(iii) Query a phase oracle for 𝐻 to obtain ((-1) 𝐻 (𝑥 0 ) |𝑥 0 ⟩ + (-1) 𝐻 (𝑥 1 ) |𝑥 1 ⟩) |𝑦⟩, (iv) Make a Hadamard basis measurement of the first register, obtaining outcome 𝑟 . Informally, our structure theorem establishes that querying at a superposition of pre-images is essentially the only way to succeed (provided finding a collision for 𝑔 is hard-this is the case when 𝑔 is a trapdoor claw-free function, as in [17], but more generally our theorem also holds e.g. when 𝑔 is a uniformly random 2-to-1 function). Denote by 𝑛 the bit-length of strings in the domain of 𝑔.

Theorem 8 (informal). Let 𝑃 be any BQP prover that succeeds with 1 -negl(𝑛) probability at the proof of quantumness protocol from [17], by making 𝑞 queries to the oracle 𝐻 . Then, with 1 -negl(𝑛) probability over pairs (𝐻, 𝑦), the following holds. Let 𝑝 𝑦 |𝐻 be the probability that 𝑃 𝐻 outputs 𝑦, and let 𝑥 0 ,𝑥 1 be the pre-images of 𝑦. Then, for all 𝑏 ∈ {0, 1}, there exists 𝑖 ∈ [𝑞] such that the state of the query register of 𝑃 𝐻 right before the 𝑖-th query has weight

Note that a version of the above theorem that applies to provers who win with probability non-negligibly greater than 1 2 also holds (but we stated the close-to-ideal version for simplicity). We provide a sketch of how this theorem is used in the proof of

Discussion and Open Problems

Separations of decision classes and going beyond the random oracle model. Our separations are with respect to search classes. What about decision classes? The Aaronson-Ambainis conjecture [2] states that one cannot separate the decision versions of BPP and BQP in the random oracle model. Assuming the conjecture is true, this also implies that there cannot be a separation between the decision versions of BPP QNC BPP 𝑑 and BQP in the random oracle model. Thus, for the case of decision classes, it would be interesting to see whether there exists some structured oracle separation for which the oracle can be instantiated based on a suitable computational assumption. Both [21] and [28] suggested the possibility of using either virtual black-box (VBB) obfuscation or indistinguishability obfuscation (iO) to instantiate their oracles. For the former, one difficulty is that it is known that one cannot VBB obfuscate general functions [12,13]. Irrespective of this fact, however, there is a more general obstacle that applies to either type of obfuscation. As we mentioned in the introduction, it was noted in [14] that no standard cryptographic assumption (not even the existence of iO) is known to imply a depth separation (even between P and NC). It therefore seems that one either has to use non-standard assumptions to prove the separations or make a significant advancement either in refuting the Aaronson-Ambainis conjecture or in proving P ≠ NC from a standard cryptographic assumption.

The limitations of using cryptographic assumptions to prove depth separations also apply to the search classes. In some sense, separations with respect to a random oracle are the best we can hope for, given the current techniques in computational complexity theory. This is peculiar, since one would imagine that using more structured non-oracular problems would allow one to prove stronger separations. The random oracle is the least structured type of oracle, but the fact that it is an oracle helps in establishing provable lower bounds.

Further questions in the random oracle model. Recall that our lifting lemma, turning a classical query sound problem into a problem which can separate BPP QNC BPP 𝑑 and BQP in the random oracle model, could be instantiated with the proof of quantumness from [43]. The resulting problem inherits the property that solutions can be publicly verified. We thus obtain a proof of quantum depth that is publicly verifiable. Unlike a proof of quantumness, the proof of quantum depth is sound against a family of quantum provers (in this case BPP QNC BPP 𝑑 provers). Can we further push this quantum soundness to obtain verification of BQP with a BPP verifier relative to a random oracle?

We have also seen that making use of a problem inspired by the Brakerski et al. [17] proof of quantumness allows us to prove more fine grained separations between hybrid classes. It is then natural to ask, whether these separations also yield finer grained proofs of quantum depth (which are sound against BPP QNC BPP 𝑑 provers and complete for a BPP QNC BPP 2𝑑+O(1) prover). This does not immediately follow from our results, as the problem we construct from BKVV is not efficiently verifiable, and our current techniques do not directly extend to the computationally-bounded setting. We therefore leave this as an open problem.

Generalizing beyond BPP QNC BPP

𝑑 . We have argued that BPP QNC BPP 𝑑 is the most natural class capturing the notion of 𝑑-depth quantum computation, combined with polynomial-depth classical computation. However, for the purpose of certifying quantum depth, as we have mentioned earlier (and as we discuss in more detail in Example 12), the situation becomes more subtle when the certification protocol involves interaction. We therefore propose that any protocol which establishes quantum depth 𝑑 and uses 𝑟 rounds of interaction should be sound against at least an 𝑟 level generalization of BPP QNC BPP 𝑑 (e.g. a 2 level generalization with quantum depth 𝑑 would be BPP QNC 𝑑 BPP QNC BPP 𝑑 -here 2 counts the number of times QNC 𝑑 appears in the tower of complexity classes, so that an 𝑟 level generalisation would have 𝑟 appearances of QNC 𝑑 ). In our case, since the proof of depth protocols are single-round, we show the necessary soundness against a BPP QNC BPP 𝑑 prover. Of course, there are other possible ways to define hybrid 𝑑-depth quantum-classical computation. For instance, one can define the class QDepth 𝑑 of problems solved by polynomial sized circuits with quantum and classical gates where the key constraint is that the longest path connecting quantum gates (with quantum wires) is at most 𝑑. We expect our separating problems (and 𝑑-Rec[P] in general, for classical query sound P) to not be contained in QDepth 𝑑 . We also expect that Q 𝑑 H ⊊ QDepth 𝑑 , but we leave the proof as future work.

Previous Work

We compare our results to the previous works [21], [28], [11], and [22].

Comparison to [21], [28] and [11]. Compared to previous work on the topic, our work gives a comprehensive treatment of the complexity of hybrid quantum-classical computation.

As mentioned earlier, the primary difference compared to [21] and [28] is that all of our separations are with respect to a random oracle, rather than with respect to highly structured oracles. However, one caveat is that our separations are for search problems. Our contribution is also conceptual. We propose BPP QNC BPP 𝑑 as the appropriate model to capture "𝑑-depth quantum computation combined with polynomial-time classical computation". While [21] and [28] showed that BPP QNC 𝑑 ∪ QNC BPP 𝑑 ⊈ BQP, we show the stronger result that BPP QNC BPP 𝑑 ⊈ BQP. Our work also shows separations between different hybrid models. Such separations were considered in [11], where they are again proven only with respect to highly structured oracles.

In terms of techniques, we take inspiration and ideas from both [21] and [11]. In particular we build on two key ideas-the sampling argument and domain hiding. One of the main contributions of our analysis is to abstract and generalise these techniques beyond their original scope which was tailored to specific promise problems. While most of our results build on these techniques, we also point out that to prove the separation between the hybrid models QNC BPP O(1) ⊈ BPP QNC 𝑑 we use entirely different ideas. In particular, as an intermediate step, we establish a theorem that characterizes the structure of strategies that succeed in the proof of quantumness of BKVV, which may be of independent interest.

Comparison to [22]. The work of [22] was the first to consider proofs of quantum depth. However, the notion of soundness that they propose, and their corresponding protocol (in the single prover setting), suffers from the issues that we discussed after Theorem 2 (and in Example 12 below).

In particular, their protocol can be spoofed by a 𝑑 level tower of

BPP QNC BPP

O(1) (as described in Subsection 1.3). In practical terms, this means that it can be spoofed by running several constant depth quantum computers in parallel, provided the "idle coherence time" of each quantum computer is longer than the time that elapses between messages in the protocol. In contrast, our proof of depth protocol does not suffer from this issue and can be used to certify that the prover is able to perform computations "beyond" BPP QNC BPP 𝑑 .

TECHNICAL OVERVIEW

Here we give a high level technical overview of the paper.

Bounds on Quantum Depth

In this subsection, we describe the proof of Theorem 1. As mentioned previously, our main technical contribution is a general lifting lemma that takes any problem separating BPP from BQP in the random oracle model, which additionally satisfies a property that we call classical query soundness, and constructs a problem separating BPP QNC d BPP and BQP. We first explain the key idea behind this construction. To be concrete, after describing the key idea, we restrict to an NP search problem due to Yamakawa and Zhandry [43], which satisfies classical query soundness (this problem is particularly appealing because it is in NP, and thus solutions can be publicly verified, however we emphasize that other known search problems that are not in NP can also be used for the separation). We then build towards a proof that this problem is not in BPP QNC BPP 𝑑 by considering hardness for the three special cases QNC 𝑑 , QNC BPP 𝑑 and BPP QNC 𝑑 . The desired result is obtained by combining the ideas in these three cases.

Let P be a (search) problem, defined relative to a random oracle 𝐻 , that separates BPP from BQP. Suppose that P is such that it requires quantum access to 𝐻 in order to be solved with polynomially many queries (classical query soundness will eventually require a bit more than this). As mentioned in Subsection 1.2.1, the first natural idea to lift this to a separation between low quantum depth and polynomial quantum depth is to replace the evaluation of 𝐻 with a sequential evaluation of random oracles. For example, suppose that originally 𝐻 : Σ → {0, 1} 𝑛 . Then, let 𝐻 0 , . . . , 𝐻 𝑑-1 : Σ → Σ, and

the problem that is identical to P except that it is relative to H . Then, it is natural to imagine that P ′ requires quantum depth at least 𝑑 + 1 to solve. This idea does not quite work right away, since H , as defined, is not actually a uniformly random oracle any more. This is because with every 𝐻 𝑖 that is added, the number of collisions in H increases (on average). To remedy this, one could assume that 𝐻 0 , . . . , 𝐻 𝑑-1 are random permutations (although note that random permutations cannot be generically constructed from random oracles). A similar idea works in a different setting, for arguing about the post-quantum security of "proofs of sequential work" [15]. However, in our case, the analysis is complicated by the fact that we consider hybrid models. CCL were the first to consider a variant of sequential hashing (sequential permutations), in the context of hybrid models. However, their analysis only works for certain structured oracles. In this work, we adapt their ideas to the random oracle setting and overcome these difficulties.

Lifting P ∉ BPP to P ∉ BPP QNC BPP 𝑑 . Given a problem P with respect to 𝐻 , we define the problem P = 𝑑-Rec[P] to be P with respect to H = 𝐻 𝑑 • • • • • 𝐻 0 where 𝐻 0 , . . . , 𝐻 𝑑 are independent random oracles with the following domains and co-domains: 𝐻 0 :

Notice that 𝐻 0 is not surjective, as its codomain is much larger than its image. 12 In fact, this is also true for 𝐻 𝑖 • • • • • 𝐻 0 , for all 𝑖 < 𝑑. This and the fact that the 𝐻 𝑖 functions are random, have two important consequences. First, it means that with high probability

and so H behaves like a random oracle. Consequently, P ′ inherits the soundness and completeness of P. Second, it means that one can apply a "domain hiding" technique, which, at a high level, works as follows. One way of evaluating H at 𝑥 ∈ Σ is to sequentially compose 𝐻 0 , 𝐻 1 , . . . , 𝐻 𝑑 which would require depth 𝑑 + 1. Intuitively, it seems unlikely that there is a more depth efficient way of evaluating H because the domain on which the 𝐻 𝑖 's need to be evaluated (which is

) is getting shuffled and lost in an exponentially larger domain (which is Σ 𝑑 ′ ). Therefore, even though one has access to all L = (𝐻 0 , 𝐻 1 , . . . , 𝐻 𝑑 ) oracles at the first layer of depth, one only knows that 𝐻 0 needs to be queried at Σ but the algorithm has no information about where the relevant domains of 𝐻 1 . . . 𝐻 𝑑 are. At the second depth layer, the algorithm can learn 𝐻 0 (Σ) and so learns where to query 𝐻 1 but, and this needs to be shown, it still does not know where the relevant domains of 𝐻 2 , . . . 𝐻 𝑑 are. By starting with a sufficiently large expansion, i.e. a sufficiently large 𝑑 ′ > 𝑑, this argument can be repeated until depth 𝑑 where the relevant domain of 𝐻 𝑑 still remains hidden. Thus, even though P ′ can potentially be solved with 𝑑 + 1 depth, it cannot be solved with depth 𝑑. This is the basic idea behind why the problem is not in QNC 𝑑 . Instead of working with P and 𝑑-Rec[P] abstractly, we consider the following concrete problem.

𝑑-CodeHashing |

The problem. We refer to the problem introduced by Yamakawa and Zhandry [43] as CodeHashing in this work. The problem is stated in terms of a family of error-correcting codes called suitable codes. For our purposes, it suffices to think of suitable codes as a family of sets {𝐶 𝜆 } 𝜆 where each 𝐶 𝜆 is a set of codewords {(x 1 , . . . x 𝑛 )} with each coordinate x 𝑖 belonging to some alphabet Σ. The size of this alphabet, |Σ| = 2 𝜆 Θ(1) is exponential in 𝜆, and the number of components 𝑛 = Θ(𝜆) essentially equals 𝜆.

CodeHashing is defined as follows.

Definition 9 (CodeHashing; informal). Let {𝐶 𝜆 } 𝜆 be a suitable code and let 𝐻 : {0, 1} log 𝑛 × Σ → {0, 1} be a random oracle. Given a description of the suitable code (e.g. as parity check matrices) and oracle access to 𝐻 , on input 1 𝜆 , the problem is to find a codeword x = (x 1 . . . x 𝑛 ) ∈ 𝐶 𝜆 such that 13 𝐻 (𝑖 ||x 𝑖 ) = 1 for all 𝑖 ∈ {1 . . . 𝑛}.

Note that

CodeHashing is an NP search problem, since from, e.g. the parity check matrix of the code, it is easy to verify that x is indeed a codeword and with a single parallel query (𝑛 queries in total) to 𝐻 , one can check that it hashes correctly.

YZ shows that CodeHashing satisfies the following two properties.

Lemma 10 (Paraphrased from YZ). The following hold.

• Completeness: There is a QPT machine which solves CodeHashing with probability 1 -negl(𝜆) and makes only one parallel query to 𝐻 . • Soundness: Every (potentially unbounded time) classical circuit which makes at most 2 𝜆 𝑐 queries to 𝐻 , with 𝑐 < 1, solves CodeHashing with probability at most 2 -Ω (𝜆) .

The fact that soundness holds against unbounded time classical circuits which make only poly-many queries to the random oracle is essential in proving that BPP QNC BPP ⊊ BQP. Applying our lifting map, 𝑑-Rec[P] on CodeHashing we obtain the following. 14 Definition 11 (𝑑-CodeHashing; informal). Let {𝐶 𝜆 } 𝜆 be a suitable code, and

where 𝐻 0 , . . . , 𝐻 𝑑 are as in Section 2.1. Given a description of the suitable code, access to random oracles L = (𝐻 0 . . . 𝐻 𝑑 ), on input 1 𝜆 , find a codeword for all 𝑖 ∈ {1 . . . 𝑛}.

To convey the key ideas behind the proof that 𝑑-CodeHashing ∉ BPP QNC BPP 𝑑 , we first consider the QNC 𝑑 case in some more detail, and extend the analysis to QNC BPP 𝑑 . We then analyse the BPP QNC 𝑑 case, which uses a technique called the "sampling argument" due 13 We use 𝑎 | |𝑏 to mean concatenation of 𝑎 and 𝑏. 14 We used bit i [ H(

to [27]. These ideas were first considered in the structured oracle setting by [21] and [11]. We adapt them to show 𝑑-CodeHashing ∉ BPP QNC BPP 𝑑 relative to a random oracle.

𝑑-CodeHashing

Base sets. We started our discussion in Subsection 2.1 by observing that the analysis is simplified by taking 𝐻 0 . . . 𝐻 𝑑-1 to be injective functions. However, for a large enough 𝑑 ′ , it is not hard to see that this is indeed the case on an appropriately restricted domain. The sets which describe this restricted domain are chosen randomly. We call them base sets and denote them by 𝑆 01 , . . . 𝑆 0𝑑 (corresponding to 𝐻 1 , . . . 𝐻 𝑑 respectively). Observe that 𝐻 0 maps Σ to Σ 𝑑 ′ (which is exponentially larger than Σ; recall that |Σ| = 2 𝜆 Θ(1) ) and, since 𝐻 0 is a random function, the probability that this mapping is injective is 1 -negl(𝜆). Pick any set 𝑆 01 ⊆ Σ 𝑑 ′ uniformly at random in the domain of 𝐻 1 subject to two constraints: (1) it includes 𝐻 0 (Σ), i.e. the domain of 𝐻 1 on which the value of H depends, and (2) its size is |𝑆 01 | = |Σ| 𝑑+2 . The first constraint ensures that the domain we care about is included in the base sets and the second ensures that: (a) |𝑆 01 | is exponentially smaller than |Σ| 𝑑 ′ and (b) |𝑆 01 | is large enough for applying "domain hiding" as mentioned above. Define 𝑆 0𝑖 := 𝐻 𝑖-1 (. . . 𝐻 1 (𝑆 01 ) . . . ) to be the image of 𝑆 01 through the first 1 to (𝑖 -1)'th oracles for 𝑖 ∈ {2 . . . 𝑑 }. Let 𝐸 denote the event that 𝐻 0 is injective and 𝐻 1 . . . 𝐻 𝑑-1 are injective on the base sets. We show that 𝐸 (given our choice for 𝑑 ′ ), occurs with overwhelming probability. In the subsequent discussion, we assume that base sets have been selected and that 𝐸 occurs.

Proof idea. We describe the proof that 𝑑-CodeHashing ∉ QNC 𝑑 in some more detail, which implements the previously described "domain hiding" idea and proceeds via a hybrid argument. Denote a QNC 𝑑 circuit that makes 𝑑 parallel calls to the oracle L = (𝐻 0 , . . . 𝐻 𝑑 ) by

Here, 𝜌 0 is some initial state, 𝑈 𝑖 are single layered unitaries, and the composition is meant to act as conjugation, i.e. 𝑈 1 • 𝜌 0 = 𝑈 1 𝜌 0 𝑈 † 1 . We show that the behaviour of such a circuit, i.e. its probability of outputting a valid answer, is negligibly close to the behaviour of another circuit

where M 1 , . . . M 𝑑 are "shadow oracles" corresponding to L that contain no information about the values taken by H on Σ. Clearly then, this circuit cannot be solving 𝑑-CodeHashing because it never queries H . This in turn means that the original circuit also cannot solve 𝑑-CodeHashing, which implies 𝑑-CodeHashing ∉ QNC 𝑑 . It remains to define M 1 . . . M 𝑑 and to argue that the two circuits have essentially the same behaviour. Using a hybrid argument, one can establish the latter by showing that the following are close in trace distance: (1)

and so on. To convey intuition, we sketch these steps one at a time, and we define M 1 . . . M 𝑑 as we proceed. We restrict to base sets 𝑆 01 . . . 𝑆 0𝑑 as described above.

Hybrid 1. Let 𝑆 1𝑗 := 𝐻 𝑗-1 (𝑆 1,𝑗-1 ) be the propagation of 𝑆 11 through 𝐻 1 to 𝐻 𝑗-1 . Here, we are trying to define a sequence of sets (𝑆 11 , . . . 𝑆 1𝑑 ) on which we require that M 1 outputs ⊥ and outside of these sets, we require that M 1 behaves just like L, i.e. if one denotes M 1 = (𝐻 0 , 𝑀 11 , . . . 𝑀 1𝑑 ), then we require that 𝑀 1𝑖 behaves as 𝐻 𝑖 outside 𝑆 1𝑖 and outputs ⊥ inside 𝑆 1𝑖 . To be concise, we will say that M 1 is a shadow oracle of L with respect to (𝑆 11 . . . 𝑆 1𝑑 ). Why do we want this behaviour? For 𝑆 𝑖 := 𝐻 𝑖-1 (. . . 𝐻 0 (Σ) . . . ), M 1 clearly contains no information about H on Σ, since 𝑆 𝑗 ⊆ 𝑆 1𝑗 . But why couldn't we just have chosen (𝑆 1 . . . 𝑆 𝑑 ) instead of (𝑆 11 . . . 𝑆 1𝑑 ) to define M 1 ? Briefly, this is because choosing to hide an exponentially larger set (note that |𝑆 11 | = |Σ| 𝑑+1 while |𝑆 1 | = |Σ|) allows us to easily apply similar arguments in the subsequent hybrids. This will become evident shortly. Recalling our goal, we want to establish that L • 𝑈 1 • 𝜌 0 and M 1 • 𝑈 1 • 𝜌 0 are close in trace distance. To do this, we use the so-called one-way to hiding (O2H) lemma [8]. Informally, the lemma, as applied to our situation, says that if (a) the input state 𝜌 0 contains no information about the set where L and M 1 behave differently, and (b) the probability of finding any element inside this set is negligible, then the trace distance between the two states of interest is negligible. The lemma clearly applies in our case because (a) initially the algorithm contains no information about L (it has not yet made any queries) and (b) the probability of finding any element in the set 𝑆 1𝑖 where L and M 1 behave differently, without knowing anything about L, is at most |𝑆 1𝑖 |/|𝑆 0𝑖 | = negl(𝜆), for each 𝑖 ∈ {1 . . . 𝑑 }, and thus still negligible by a union bound.

In this step, we will see the advantage of having chosen a sequence of sufficiently large sets (𝑆 11 , . . . 𝑆 1𝑑 ) where M 1 outputs ⊥. Let us begin with examining the information contained in 𝜌 1 about L. In the previous case, 𝜌 0 contained no information about L. Since 𝜌 1 only learns about L by querying M 1 , it suffices to examine the information contained in M 1 . Since M 1 does not hide any information about 𝐻 0 , 𝜌 1 could have learnt 𝑆 1 = 𝐻 0 (Σ). Recall also that 𝑆 1 ⊆ 𝑆 11 . This means that if one were to take M 2 equal to M 1 , then one cannot expect L•𝑈 2 • 𝜌 1 to be close to M 2 •𝑈 2 • 𝜌 1 in general because 𝑈 2 could query the oracle at 𝑆 1 and the outputs of the two circuits would be different with probability one-M 1 outputs ⊥ while L does not. Consequently, when constructing M 2 , we do not hide anything about 𝐻 1 . As for 𝐻 2 . . . 𝐻 𝑑 , note that, M 1 contains no information about the behaviour of L inside 𝑆 12 , 𝑆 13 . . . 𝑆 1𝑑 . We can therefore, treat 𝑆 12 . . . 𝑆 1𝑑 as the new "base sets" and proceed analogously. Let 𝑆 22 ⊆ 𝑆 12 be a random subset of 𝑆 12 , subject to the constraint (as before) that (a) it includes 𝑆 2 = 𝐻 1 (𝐻 0 (Σ)) and (b)

Defining M 2 to be the shadow oracle of L with respect to (∅, 𝑆 22 , . . . 𝑆 2𝑑 ), one can again apply the O2H lemma to conclude that L

Generalising the argument above, one sees that the sets 𝑆 𝑖 𝑗 constitute a triangular matrix (where the 𝑖-th row corresponds to sets on which M 𝑖 outputs ⊥)

which clarifies why the argument can only be applied for 𝑑 steps (as we expect). To see this, note that at the 𝑑th step, all oracles except the last have been completely revealed (last row). Crucially, the last oracle is blocked at 𝑆 𝑑 ⊆ 𝑆 𝑑𝑑 and therefore reveals no information about H (Σ). If one proceeds with the (𝑑 + 1)-th step, all oracles are revealed and one can no longer argue that the algorithm does not access H (Σ).

Observe that so far, we have not used the fact that CodeHashing is classically hard, only that without access to the oracle, the problem cannot be solved. The classical hardness comes into play once BPP computations are allowed.

𝑑-CodeHashing ∉ QNC BPP

𝑑

. We now sketch how one goes from arguing 𝑑-CodeHashing ∉ QNC 𝑑 to arguing

𝑖 denotes a classical algorithm, and Π 𝑖 denotes a (possibly partial) measurement. The analogous circuit with shadow oracles is denoted by

The idea, again, is to establish, via a hybrid argument, that the two circuits are close in trace distance. In the QNC 𝑑 case, thanks to the depth of the circuit being 𝑑, we were able to argue that any QNC 𝑑 algorithm behaves equivalently if we take away its access to H . When trying to argue that a QNC BPP 𝑑 algorithm cannot solve the problem, we have to be more careful because the BPP part has sufficient depth to make queries to H . In our argument, this will affect how the shadow oracles M 𝑖 are defined.

In some more detail, we allow the classical algorithm to make "path queries"-which intuitively just means that if 𝐻 𝑖 is queried at 𝑥 𝑖 , the algorithm also learns (𝑥 0 , 𝑥 1 . . . 𝑥 𝑑 ) such that 15 𝑥 𝑗+1 = 𝐻 𝑗 (𝑥 𝑗 ) for all 𝑗. This of course can only help the algorithm.

The key idea is that we account for the "paths" that have been queried classically until depth 𝑖 and define M 𝑖 to be consistent with those (i.e. it never outputs ⊥ on these paths). As before, we can replace queries to L with queries to M 𝑖 that contain no information about H except for the paths which were classically queried. Appealing to the soundness of CodeHashing, such an algorithm cannot succeed. This is because CodeHashing has the property that even an unbounded classical algorithm cannot succeed if it only makes polynomially many queries to the oracle.

𝑑-CodeHashing

∉ BPP QNC 𝑑 . Observe that a poly depth quantum circuit can access H and since a BPP QNC 𝑑 circuit has poly many QNC 𝑑 circuits, it is not a priori clear that BPP QNC 𝑑 cannot also access H . This is why the approach we used to prove that 𝑑-CodeHashing ∉ QNC 𝑑 cannot be applied directly. Crucially, to argue that the problem is not in BPP QNC 𝑑 , one must use the fact that the contents of each QNC 𝑑 circuit are measured entirely, and that each QNC 𝑑 circuit takes only classical inputs. In order to handle the classical information that each QNC 𝑑 circuit receives as input, we use a technique called the "sampling argument". In essence, this says that if L has high entropy (which is to say that the oracles being queried are sufficiently random), then conditioned on any string 𝑠 correlated with it, the resulting L|𝑠 behaves as a "convex combination" of high entropy distributions with a small fraction of their values completely fixed. This allows us to reduce the analysis to that of a particular set of paths being exposed, which we can handle by proceeding as in the QNC BPP 𝑑 case. A similar argument was used by CCL to establish that a problem is not in BPP QNC 𝑑 with respect to a (structured) oracle. Their analysis used a sequence of permutation oracles and was simplified by viewing the oracles, equivalently, as distributions over paths (as opposed to a sequence of functions assigning values to individual points). The paths viewpoint was particularly helpful when considering the "sampling argument" (the version we use is derived from [27]). [11] showed that such a sampling argument can be obtained for almost any oracle which can be viewed as a distribution over paths. In our setting, since the oracles are random, paths can collide. Thus, one needs to define a suitable notion of "paths" in this setting. We provide more details in the next three paragraphs. However, since these are relatively more technical, one may wish to skip directly to Subsection 2.1.5 on a first read.

Sampling argument for Permutations. Suppose 𝑡 is a permutation over 𝑁 elements labelled {0, . . . , 𝑁 -1}. This permutation 𝑡 is ordinarily viewed as a function, 𝑡 (𝑥) specifying how 𝑥 is mapped. However, one could equivalently view 𝑡 as a collection of pairs (or tuples later) (𝑥, 𝑦) such that 𝑡 (𝑥) = 𝑦. We call such a pair a "path". Now consider distributions over permutations. Let's begin with a uniform distribution F over all permutations 𝑢. One may characterise F as follows: for any 𝑢 ∼ F, i.e. any 𝑢 sampled from F, it holds that Pr[𝑢 (𝑥

We first state a basic version of the sampling argument. To this end, we define a (𝑝, 𝛿) non-uniform distribution, F (𝑝,𝛿) , which is closely related to the uniform distribution F. At a high level, F (𝑝,𝛿) is "𝛿 close to" F with at most 𝑝 many paths fixed. What does "𝛿 closeness" mean? Let Pr[𝑆 ⊆ paths(𝑢)] denote the probability that a collection 𝑆 of (non-colliding) paths is in 𝑢. Then, for any distribution G (over permutations), a distribution G 𝛿 is 𝛿 close to it if the following holds: when 𝑡 ′ ∼ G 𝛿 and 𝑡 ∼ G, one has

We are almost ready to state the basic sampling argument. We need the notion of a "convex combination" of random variables. We say a random variable (such as our permutation) 𝑡 is a convex combination of random variables 𝑡 𝑖 , denoted by 𝑡 ≡ 𝑖 𝛼 𝑖 𝑡 𝑖 (where

Informally, the basic sampling argument is a statement about a uniform permutation 𝑢 ∼ F and how the distribution F changes if we are given some "advice" about this permutation which is simply a function 𝑔(𝑢). Roughly speaking, given that 𝑔(𝑢) evaluates to 𝑟 with probability at least 2 -𝑚 , the distribution F conditioned on 𝑟 is a convex combination 16 of F (𝑝,𝛿) distributions where the number of paths fixed is at most 𝑝 = 2𝑚/𝛿. Here 𝛿 is a free parameter. We slightly abuse the notation and write this basic sampling argument as F|𝑟 ≡ conv(F (𝑝,𝛿) ).

If we view 𝑔(𝑢) as the output of the first quantum part of the circuit for BPP QNC 𝑑 , and 𝑢 as the oracle of interest (details are in the next section), it is suggestive that 𝑢 |𝑔(𝑢) will be the oracle for the second quantum part of the circuit. We can use the sampling argument above and re-use our analysis because F and F (𝑝,𝛿) have very similar statistical properties. However, it is unclear how to use the sampling argument thereafter as the basic sampling argument seems to only apply to F (and not to F (𝑝,𝛿) ). It turns out that one can extend the sampling argument to obtain

Consequently, if the procedure is successively applied ñ ≤ poly(𝑛) times (starting with F), the convex combination would be over distributions of the form F ( ñ𝑝, ñ𝛿) . The parameters can be appropriately chosen to ensure that at most polynomially many paths are exposed but we omit the details in this overview.

Sampling argument for Injective Shufflers. The proofs of the previously mentioned statements do not rely on any special property of the distribution F nor do they depend on the fact that we were considering permutations. Any object for which we can describe a "reasonable" notion of "paths" admits such a sampling argument. Therefore, as we did for permutations, to describe the sampling argument, we change our viewpoint and consider "paths" in L = (𝐻 0 , . . . 𝐻 𝑑 ) instead of individual values taken by the 𝐻 𝑖 's. Recall that a "path" was a tuple of the form (𝑥 0 , 𝑥 1 . . . ) such that

This viewpoint is inadequate for capturing the probabilistic behaviour of L due to two reasons (which are not hard to rectify). First, since 𝐻 0 : Σ → Σ 𝑑 ′ , it is clear that at least Σ 𝑑 ′ -1 many points will never be contained in any "path" as described above. Therefore the behaviour of most points in 𝐻 𝑖 (for 𝑖 ∈ {1 . . . 𝑑 }) will not be captured by the "paths" viewpoint. Second, even though 𝐻 𝑖 maps Σ 𝑑 ′ → Σ 𝑑 ′ for 𝑖 ∈ {1, . . . 𝑑 -1}, 𝐻 𝑖 may not be injective and therefore the paths might collide, which again would mean the behaviour of many points would not be captured by the "paths" viewpoint.

To rectify the second issue, we can select base sets (𝑆 01 , . . . 𝑆 0𝑑 ) =: S0 and condition on the event 𝐸. Since in our proofs, we only care about the behaviour of L on S0 , it suffices to restrict our attention to S0 . Recall that L|𝐸 behaves as a permutation on S0 . Therefore no "path" inside S0 collides. To rectify the first issue, we consider two kinds of paths-Type 0 paths and Type 1 paths. 17 A Type 0 path is what we described earlier: a tuple of the form (𝑥 0 , 𝑥 1 . . . ) such that 𝑥 𝑖 = 𝐻 𝑖-1 (𝑥 𝑖-1 ) for all 𝑖. A Type 1 path is a tuple of the form

Observe that, restricted to S0 and conditioned 18 on 𝐸, we have the following equivalence: given Pr[𝐻 𝑖 (𝑥) = 𝑥 ′ ] for all 𝑖, 𝑥 and 𝑥 ′ , one can compute the probability associated with both types of paths and conversely, given probabilities associated with the paths, one can compute Pr[𝐻 𝑖 (𝑥) = 𝑥 ′ ] for all 𝑖, 𝑥 and 𝑥 ′ .

As is evident, working with L directly is cumbersome and we therefore define a simpler object, the injective shuffler. Fix sets

𝑖 : 𝑆 0𝑖 → 𝑆 0,𝑖+1 for all 𝑖 ∈ {1, . . . 𝑑 -1} be injective functions and let 𝐻 ′ 𝑑 : 𝑆 0𝑑 → {0, 1} 𝑛 ∪ {⊥} (which may not be injective) such that 𝐻 ′ 𝑑 outputs ⊥ for all paths originating from Σ (and no other). 19 We define the injective shuffler, K as (𝐻 ′ 0 , . . . 𝐻 ′ 𝑑 ). Think of K as a simpler way to denote the relevant object associated with L|𝐸. What do we mean by the relevant object-not only is it injective, it also never reveals any information 20 about the values taken by H in Σ. As alluded to at the beginning of this subsection, since the strings 𝑠 𝑖 arise from quantum parts which only get access to L via shadow oracles, the sampling argument only needs to be applied to parts of L outside of paths in H .

To state the sampling argument for the injective shuffler, we define (𝑝, 𝛿) non-𝛽-uniform distributions F (𝑝,𝛿) |𝛽 inj for the injective shuffler (analogous to the way we defined them for permutations). We begin with the uniform distribution-it is simply a distribution which assigns equal probabilities to all the possible injective shufflers, given the sets (𝑆 0𝑖 ) 𝑖 . As for 𝛽-uniform distributions, F |𝛽 inj , we first need to define the "paths", 𝛽. Here, 𝛽 will again be a set of "non-colliding paths" but formalising this requires some care (details in the full version [10]). Then a 𝛽-uniform distribution is the same as the uniform distribution except that the paths in 𝛽 are fixed. Omitting further details, one can define F (𝑝,𝛿) |𝛽 to be a distribution which is "𝛿 close to" the 𝛽-uniform distribution with at most 𝑝 many paths fixed (in addition to 𝛽).

The sampling argument for injective shufflers is the following. Suppose we start with 𝑡 ∼ F 𝛿 ′ |𝛽 inj (i.e. a distribution which is "𝛿 ′ close to" 𝛽-uniform) and are given some advice ℎ(𝑡) which happens to be 𝑟 with probability at least 2 -𝑚 . Then the distribution F 𝛿 ′ |𝛽 inj conditioned on 𝑟 is, roughly speaking, a convex combination 21 of F (𝑝,𝛿+𝛿 ′ ) |𝛽 inj distributions where the number of paths fixed (in addition to 𝛽) is at most 𝑝 = 2𝑚/𝛿 and 𝛿 again is a free parameter. Using the previous shorthand, we have

Stitching everything together. As asserted before we described the sampling argument, one can replace all the oracles L in the quantum part of the circuit for BPP QNC 𝑑 with appropriate shadow oracles. Let M 11 , . . . M 1𝑑 denote the shadow oracles for the first quantum part, M 21 . . . M 2𝑑 for the second quantum part and so on. Suppose the paths queried by the 𝑖th classical part were 𝛽 𝑖 , the string outputted by the 𝑖th quantum part be 𝑠 𝑖 . Suppose M 11 . . . M 1𝑑 . . . M 𝑖-1,1 . . . M 𝑖-1,𝑑 have been specified. Now, conditioned on 𝑠 𝑖 , the sampling argument says L|𝑠 𝑖 behaves as a convex combination of injective shufflers with certain paths exposed, when restricted to base sets. Let 𝛽 (𝑠 𝑖 ) be the random variable which specifies these paths and occurs with the weights specified in the convex combination. One can define M 𝑖1 . . . M 𝑖𝑑 as in the QNC 𝑑 case, ensuring the paths 𝛽 1 . . . 𝛽 𝑖-1 and 𝛽 (𝑠 1 ) . . . 𝛽 (𝑠 𝑖-1 ) have been exposed. Note crucially that 𝑠 𝑖 is obtained by a quantum part which only had 19 i.e. 𝐻 ′ 𝑑 (𝑥 𝑑 ) =⊥ iff (𝑥 0 , 𝑥 1 , . . . 𝑥 𝑑 , 𝑥 𝑑+1 ) is a Type 0 path (therefore 𝑥 𝑑+1 =⊥). 20 Except for polynomially possibly many paths exposed by classical queries; we handle these shortly. 21 Again, neglecting a component with weight at most 2 -𝑚 . access to Lvia shadow oracles so it does not change the distribution over H (except for polynomially many paths which were already exposed, 𝛽 1 . . . 𝛽 𝑖-1 and 𝛽 (𝑠 1 ) . . . 𝛽 (𝑠 𝑖-1 )). Using a hybrid argument as in the QNC 𝑑 case, and using properties of the injective shuffler which is "𝛿 close" to being uniform, one can apply the O2H lemma and conclude that the hybrids (again, defined as in the QNC 𝑑 case) are close in trace distance. Eventually, this yields that the initial circuit is close in trace distance to the circuit which only accesses L via the shadows M 11 . . . M 1𝑑 . . . M 𝑚1 . . . M 𝑚𝑑 in the quantum part (denote the number of quantum parts by 𝑚 ≤ poly(𝜆)). The latter circuit cannot solve 𝑑-CodeHashing again, because H is only accessed by the classical parts of this circuit. More precisely, H is only queried at at most |𝛽 1 ∪ . . . 𝛽 𝑚 ∪ 𝛽 (𝑠 1 ) ∪ . . . 𝛽 (𝑠 𝑚 )| ≤ poly(𝜆) locations and therefore the whole circuit can be simulated while only making polynomially many classical queries to H . From the soundness of CodeHashing, this entails 𝑑-CodeHashing cannot be solved.

𝑑-CodeHashing ∉ BPP QNC BPP

𝑑

. Just as the analysis of the BPP QNC 𝑑 case built on the QNC 𝑑 case, one can analyze the BPP QNC BPP 𝑑 case by building on the QNC BPP 𝑑 case. While the high level idea stays the same, the details are more involved. This is partly because, in the QNC 𝑑 case, one could construct the shadow oracles M 1 . . . M 𝑑 "all at once" since we were assuming the "worst case", i.e. the quantum algorithm learns everything there is to learn from the shadow oracles. However, in the QNC BPP 𝑑 case, to define M 𝑖 , one had to know the behaviour of the classical algorithms in the hybrid circuits which involved M 1 . . . M 𝑖-1 (in particular one has to know the "paths" that have been exposed). We show how one can account for this, but we leave the details to the main body.

2.1.6 Proof of Quantum Depth. In this subsection, we discuss how our complexity-theoretic separations also yield protocols for certifying quantum depth, i.e. proofs of quantum depth, in a way that is insensitive to classical polynomial depth. First, let us be a bit more precise about what we mean by proof of quantum depth. Definition (informal). A proof of 𝑑 quantum depth is a twomessage protocol involving two parties, a verifier and a prover. Both parties are assumed to have access to the random oracle 𝐻 . The verifier is a PPT machine. The protocol satisfies the following, where 𝜆 is the security parameter.

• Completeness: There is a prover in BQP which makes the verifier accept with probability 1 -negl(𝜆). • Soundness: No prover in BPP QNC BPP 𝑑 makes the verifier accept with probability more than negl(𝜆). Let 𝑑 be at most a fixed polynomial. Since 𝑑-CodeHashing is in NP, it immediately yields a proof of 𝑑 quantum depth.

We conclude this discussion by illustrating the subtlety of considering proofs of quantum depth with more than two messages. Consider the following protocol.

Example 12. The verifier, Alice, prepares BB84 states |𝑏 𝑖 ⟩ 𝜃 𝑖 := 𝐻 𝜃 𝑖 |𝑏 𝑖 ⟩ (𝑏 𝑖 , 𝜃 𝑖 are both chosen uniformly at random) for 𝑖 ∈ {1, . . . 𝑛} where 𝐻 is the Hadamard operation (not to be confused with the random oracle). She sends them all to the prover, Bob.

Alice and Bob then engage in an 𝑛 round protocol. (1) . We obtain the above by instantiating our lifting procedure, 𝑑-Rec[•], with a variant of the proof of quantumness from [17], which we refer to as CollisionHashing. It is straightforward to show that CollisionHashing also satisfies classical query soundness by using the main argument in [17] and the query lower bound for finding collisions proved in [4].

Let 𝑔 be a 2 → 1 function for which it is hard to find a collision. Then, the (slightly simplified) problem is to produce a pair (𝑦, 𝑟 ) such that 𝑟 • (𝑥 0 ⊕ 𝑥 1 ) ⊕ 𝐻 (𝑥 0 ) ⊕ 𝐻 (𝑥 1 ) = 0 where {𝑥 0 , 𝑥 1 } ∈ 𝑔 -1 (𝑦). This problem can be solved in QNC O(1) (assuming that calls to 𝑔 take only depth 1) by preparing the superposition 𝑥 |𝑔(𝑥)⟩ |𝑥⟩, measuring the second register in the standard basis, and the first in the Hadamard basis (detailed later).

We said simplified because in CollisionHashing, 𝑔 is in fact a uniformly random function 𝑔 (treated as an oracle) with a domain twice as large as the co-domain. Note that this is not a 2 → 1 function in general. However, with overwhelming probability, a constant fraction of the elements in the co-domain has exactly two pre-images. Then, we require a pair (𝑦, 𝑟 ) such that either 𝑦 has exactly two pre-images and (𝑦, 𝑟 ) satisfies the "equation", or 𝑦 does not have exactly two pre-images. The limitation of CollisionHashing is that solutions to the problem are not verifiable, so the problem cannot be used to obtain a fine-grained proof of quantum depth. Denote by 𝑅 𝐻 the set of solutions to P (defined with respect to 𝐻 ). Then, the key idea is simple. The problem 𝑑-Ser[P] is to return a tuple (𝑐 0 , 𝑐 1 , . . . , 𝑐 𝑑 ) such that: 𝑐 0 is a solution to P, i.e.

Separations

, and similarly until 𝑐 𝑑 , which should be such that

To be a bit more concrete, take P to be CollisionHashing. We know CollisionHashing ∈ QNC O(1) . Clearly, 1) . This is because BPP QNC O(1) allows one to run polynomially many QNC O(1) circuits. Consequently, one can use the first circuit to obtain the classical output 𝑐 0 , use the second circuit to find 𝑐 1 and so on. On the other hand, intuitively, we expect that 𝑑-Ser[CollisionHashing] ∉ QNC BPP 𝑑 . This is because to solve the (𝑖 +1)-th sub-problem, one seems to require the solution to all of the previous 𝑖 sub-problems. Since there are 𝑑 + 1 sub-problems in total, QNC BPP 𝑑 does not seem to suffice (here of course we are implicitly using the fact that P ∉ BPP). Formally, the argument proceeds in a similar way as for the lifting map 𝑑-Rec in Subsection 2.1.3, except for one subtlety which is handled by requiring that the problem P satisfies the extra property of offline soundness. We refer the reader to the main text for more details. We remark that offline soundness follows from classical query soundness and therefore both CollisionHashing and CodeHashing satisfy it.

The immediate consequence of the existence of the lifting map

Establishing QNC BPP

O(1) ⊈ BPP QNC 𝑑 . This is the more surprising of the two hybrid separations, and its proof is more involved. In this section, we fix 𝑑 ≤ 𝑝𝑜𝑙𝑦 (𝜆). The problem that yields this separation is the following variation on CollisionHashing: given access to a 2-to-1 function 𝑔 23 , and to 𝐻 0 , . . . 𝐻 𝑑 (which specify ℎ as ℎ = 𝐻 𝑑 • • • • • 𝐻 0 ), find a pair (𝑦, 𝑟 ) such that 𝑟 • (𝑥 0 ⊕ 𝑥 1 ) ⊕ 𝐻 (ℎ(𝑦)||𝑥 0 ) ⊕ 𝐻 (ℎ(𝑦)||𝑥 1 ) = 0 , where {𝑥 0 , 𝑥 1 } = 𝑔 -1 (𝑦). We refer to the new problem as 𝑑-hCollisionHashing.

Without relying on ℎ (that is, requiring that the equation to be satisfied is just 𝑟 • (𝑥 0 ⊕ 𝑥 1 ) ⊕ 𝐻 (𝑥 0 ) ⊕ 𝐻 (𝑥 1 ) = 0), this problem is the same as CollisionHashing. This can be solved in QNC O(1) as follows:

(i) Evaluate 𝑔 on a uniform superposition of inputs, obtaining 𝑥 |𝑥⟩ |𝑔(𝑥)⟩, (ii) Measure the image register obtaining some outcome 𝑦 and a state (|𝑥 0 ⟩ + |𝑥 1 ⟩) |𝑦⟩, (iii) Query a phase oracle for 𝐻 to obtain ((-1) 𝐻 (𝑥 0 ) |𝑥 0 ⟩ + (-1) 𝐻 (𝑥 1 ) |𝑥 1 ⟩) |𝑦⟩, (iv) Make a Hadamard basis measurement of the first register, obtaining outcome 𝑟 .

At a high level, in order to solve the new problem, which includes the evaluation of ℎ as an input to 𝐻 , one needs the ability to perform a (classical) depth 𝑑 computation to evaluate ℎ(𝑦) (since this requires the sequential evaluations of 𝐻 0 , . . . , 𝐻 𝑑 ). Note that a QNC BPP algorithm can solve this problem: the only modification to the algorithm described above is that, at step (iii), the algorithm first computes ℎ(𝑦) (using polynomial classical computation), and then queries the oracle 𝐻 on a superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ). One can easily verify that this leads to a valid (𝑦, 𝑟 ) for the problem.

Next, we sketch how one can argue that the problem cannot be solved in BPP QNC . The key technical ingredient is a "structure theorem" that characterizes the structure of efficient quantum strategies that are successful at CollisionHashing. Our structure theorem applies equally to the proof of quantumness protocol from [17] (recall that the latter is just a version of collision hashing where 𝑔 is replaced by a 2-to-1 trapdoor claw-free function).

Theorem 14 (informal). Let 𝑃 be any BQP prover that succeeds with 1 -negl(𝑛) probability at the proof of quantumness protocol from [17], by making 𝑞 queries to the oracle 𝐻 . Then, with 1 -negl(𝑛) probability over pairs (𝐻, 𝑦), the following holds. Let 𝑝 𝑦 |𝐻 be the probability that 𝑃 𝐻 outputs 𝑦, and let 𝑥 0 ,𝑥 1 be the pre-images of 𝑦. Then, for all 𝑏 ∈ {0, 1}, there exists 𝑖 ∈ [𝑞] such that the state of the query register of 𝑃 𝐻 right before the 𝑖-th query has weight 1 2 𝑝 𝑦 |𝐻 • (1 -negl(𝑛)) on 𝑥 𝑏 . 23 Since we want our problem to be relative to a uniformly random oracle, in the formal description of the problem in the main text, we will not assume that 𝑔 is exactly 2-to-1. Rather we will take 𝑔 to be a uniformly random function with domain twice as large as the co-domain, and simply restrict our attention to 𝑦's in the co-domain that have exactly two pre-images (this is a constant fraction of the elements of the co-domain with overwhelming probability).

See the full version [10] for a formal statement of this result. This is a crucial strengthening of a Theorem from [26], and employs the compressed oracle technique [44]. A slight adaptation of this to our problem asserts that a successful strategy must be querying the random oracle 𝐻 at a (close to) uniform superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ). Now let 𝐴 be a BPP QNC algorithm that succeeds at 𝑑-hCollisionHashing with high probability and let 𝑞 be the total number of queries to ℎ made by the algorithm. Then, one can show that, since the QNC part of the algorithm does not have sufficient depth to evaluate ℎ (which is a sequential evaluation of 𝐻 0 , . . . , 𝐻 𝑑 ), we can assume, without loss of generality, the QNC part of 𝐴 has no access to ℎ. In other words, all of the queries to ℎ are classical. Now, Theorem 14 says essentially that, for any 𝑦, the only way to succeed with high probability (conditioned on that 𝑦 being the output) is to query (with as much weight as the probability of outputting 𝑦) a uniform superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ). However, observe that, for any 𝑦, the only way for 𝐴 to query 𝐻 (with a high weight) at a uniform superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ) is to correctly guess the value of ℎ(𝑦). Since this value is uniformly random for any algorithm that has not queried ℎ at 𝑦, it follows that querying 𝐻 at the uniform superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ) must necessarily happen after the algorithm has already queried ℎ on 𝑦.

This implies that there must exist an 𝑖 * ∈ [𝑞] such that, with high probability, 𝐴 outputs 𝑦, 𝑟 such that 𝑦 is contained in the list of classical queries made to ℎ up to the 𝑖 * -th query. Denote such a list by 𝐿 𝑖 * . Moreover, with high probability over 𝐿 𝑖 * , the continuation of 𝐴 (from that point on) queries 𝐻 at a uniform superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ) for some 𝑦 ∈ 𝐿 𝑖 * . We show that such an algorithm 𝐴 can be leveraged to extract a collision for 𝑔.

The key observation is that, since 𝐴 is a BPP QNC algorithm, and all of the queries to ℎ happen in the BPP portion of 𝐴, the "state" of algorithm 𝐴 right after the 𝑖 * -th query to ℎ is entirely classical. Thus, one can take a "snapshot" of the state of 𝐴 at that point (i.e. copy it), and simply run two independent executions of 𝐴 from that point on (with independent classical randomness). By what we argued earlier, with high probability, there exists 𝑦 ∈ 𝐿 𝑖 * , such that the execution of 𝐴 from that point on, queries 𝐻 at a uniform superposition of (ℎ(𝑦), 𝑥 0 ) and (ℎ(𝑦), 𝑥 1 ). Since the two executions are identical and independent, it follows that measuring the query registers of 𝐻 in both executions will yield distinct pre-images of 𝑦 with significant probability.

Finding collisions of 𝑔 is of course hard (for any query-bounded quantum algorithm) [4]. Hence, this yields a contradiction. For details, we refer the reader to the full version [10].