The Quantum Supremacy Tsirelson Inequality
Abstract
A leading proposal for verifying nearterm quantum supremacy experiments on noisy random quantum circuits is linear crossentropy benchmarking. For a quantum circuit on qubits and a sample , the benchmark involves computing , i.e. the probability of measuring from the output distribution of on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomialtime classical algorithm given can output a string such that is substantially larger than (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit , sampling from the output distribution of achieves on average (Arute et al., 2019).
In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomialtime quantum algorithm do substantially better than ? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to . We show that, for any , outputting a sample such that on average requires at least queries to , but not more than queries to , if is either a Haarrandom qubit unitary, or a canonical state preparation oracle for a Haarrandom qubit state. We also show that when samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from is the optimal 1query algorithm for maximizing on average.
1 Introduction
A team based at Google has claimed the first experimental demonstration of quantum computational supremacy on a programmable device [AAB19]. The experiment involved random circuit sampling, where the task is to sample (with nontrivial fidelity) from the output distribution of a quantum circuit containing random  and qubit gates. To verify their experiemnt, they used the socalled Linear CrossEntropy Benchmark, or Linear XEB. Specifically, for an qubit quantum circuit and samples , the benchmark is given by:
The goal is for to be large with high probability over the choice of the random circuit and the randomness of the sampler, as this demonstrates that the observations tend to concentrate on the outputs that are more likely to be measured under the ideal distribution for . We formalize this task as the XHOG task:
Problem 1 (XHOG, or Linear CrossEntropy Heavy Output Generation).
Given a quantum circuit on qubits, output a sample such that , where the expectation is over an implicit distribution over circuits and over the randomness of the algorithm that outputs .
Here, “large” means bounded away from , as outputting uniformly at random achieves on average for any . On the other hand, if is drawn from the ideal distribution for , and if the random circuits empirically exhibit the PorterThomas distribution on output probabilities, then sampling from achieves [AAB19, AG19].
Under a strong complexitytheoretic conjecture about the classical hardness of nontrivially estimating output probabilities of quantum circuits, Aaronson and Gunn showed that no classical polynomialtime algorithm can solve XHOG for any on random quantum circuits of polynomial size [AG19]. Thus, a physical quantum computer that solves XHOG for is considered strong evidence of quantum computational supremacy.
In this work, we ask: can an efficient quantum algorithm for XHOG do substantially better than ? That is, what is the largest for which a polynomialtime quantum algorithm can solve XHOG on random circuits? Note that the largest we could hope for is achieved by the optimal sampler that always outputs the string maximizing . If the random circuits induce a PorterThomas distribution on output probabilities, then this solves XHOG for , because the probabilities of a PorterThomas distribution approach i.i.d. exponential random variables (see creftypecap 10 below). However, finding the largest output probability might be computationally difficult even on a quantum computer, which is why we restrict our attention to efficient quantum algorithms.
We refer to our problem as the “quantum supremacy Tsirelson inequality” in reference to the Bell [Bel64] and Tsirelson [CT80] inequalities for quantum nonlocal correlations (for a modern overview, see [CHTW04]). Under this analogy, the quantity in XHOG plays a similar role as the probability of winning some nonlocal game. For example, the Bell inequality for the CHSH game [CHSH69] states that no classical strategy can win the game with probability ; we view this as analogous to the conjectured inability of efficient classical algorithms to solve XHOG for any . By contrast, a quantum strategy with preshared entanglement allows players to win the CHSH game with probability
1.1 Our Results
We study the quantum supremacy Tsirelson inequality in the quantum query (or black box) model. That is, we consider distributions over quantum circuits that make queries to a randomized quantum or classical oracle, and ask how many queries to the oracle are needed to solve XHOG, in terms of . Our motivation for studying this problem in the query model is twofold. First, quantum query results often give useful intuition for what to expect in the real world, and can provide insight into why naive algorithmic approaches fail. Second, we view this as an interesting quantum query complexity problem in its own right. Whereas most other quantum query lower bounds involve decision problems [Amb18] or relation problems [Bel15], XHOG is more like a weighted, averagecase relation problem, because we only require that be large on average. Constrast this with the relation problem considered in [AC17], where the task is to output a such that is greater than some threshold.
Note that there are known quantum query complexity lower bounds for relation problems [AAB19], and even relation problems where the output is a quantum state [AMRR11, LR20]. Yet, it is unclear whether existing quantum query lower bound techniques are useful here. Whereas the adversary method tightly characterizes the quantum query complexity of decision problems and state conversion problems [LMR11], it is not even known to characterize the query complexity of relation problems (unless they are efficiently verifiable) [Bel15]. The adversary method appears to be essentially useless for saying anything about XHOG, which is not efficiently verifiable and is not a relation problem in the traditional sense.^{1}^{1}1As we will see later, however, the polynomial method [BBC01] plays an important role in one of our results.
The XHOG task is welldefined for any distribution of random quantum circuits, so this gives us a choice in selecting the distribution. We focus on three classes of oracle circuits that either resemble random circuits used in practical experiments, or that were previously studied in the context of quantum supremacy.
Canonical State Preparation Oracles
Because the linear crossentropy benchmark for a circuit depends only on the state produced by the circuit on the all zeros input, it is natural to consider an oracle that prepares a random state without leaking additional information about . Formally, we choose a Haarrandom qubit state , and fix a canonical state orthogonal to all qubit states.^{2}^{2}2We can always assume that a convenient exists by extending the Hilbert space, if needed. For example, if is an qubit state, a natural choice is to encode by and to choose . Then, we take the oracle that acts as , , and for any state that is orthogonal to both and . Equivalently, is a reflection about the state . Finally, we let be the composition of with any unitary that sends to , so that . This model is often chosen when proving lower bounds for quantum algorithms that query state preparation oracles (see e.g. [ARU14, AKKT20, BR20]), in part because the ability to simulate follows in a completely black box manner from the ability to prepare unitarily without garbage (see Lemma 7 below). Hence, the oracle is “canonical” in the sense that it is uniquely determined by and is not any more powerful than any other oracle that prepares without garbage.
HaarRandom Unitaries
A random polynomialsize quantum circuit does not behave like a canonical state preparation oracle: looks like a random quantum state for any computational basis state , not just . Indeed, random quantum circuits are known to informationtheoretically approximate the Haar measure in certain regimes [BHH16, HM18], and it seems plausible that they are also computationally difficult to distinguish from the Haar measure. Thus, one could alternatively model random quantum circuits by Haarrandom qubit unitaries.
Fourier Sampling Circuits
Finally, we consider quantum circuits that query a random classical oracle. For this, we use Fourier Sampling circuits, which Aaronson and Chen [AC17] previously studied in the context of proving oracular quantum supremacy for a problem related to XHOG. Fourier Sampling circuits are defined as , where is a phase oracle for a uniformly random Boolean function . On the allzeros input, Fourier Sampling circuits output a string with probability proportional to the squared Fourier coefficient . This model has the advantage that we can prove the corresponding quantum supremacy Bell inequality for classical algorithms given query access to , and that in some cases we can replace by a pseudorandom function to base quantum supremacy on cryptographic assumptions [AC17].
Our first result is an exponential lower bound on the number of quantum queries needed to solve XHOG given either of the two types of quantum oracles that we consider:
Theorem 2 (Informal version of Theorem 14 and Theorem 17).
For any , any quantum query algorithm for XHOG with query access to either:

a canonical state preparation oracle for a Haarrandom qubit state , or

a Haarrandom qubit unitary,
requires at least queries.
We do not know if Theorem 2 is optimal, but we show in Theorem 15 that a simple algorithm based on the quantum collision finding algorithm [BHT97] solves XHOG using queries to either oracle.
Finally, we show that for Fourier Sampling circuits, the naive algorithm of simply running the circuit is optimal among all query algorithms:
Theorem 3 (Informal version of Theorem 19).
Any query quantum algorithm for XHOG with Fourier Sampling circuits achieves .^{3}^{3}3Note that the value of achieved by the naive quantum algorithm for XHOG depends on the class of circuits used. In contrast to Haarrandom circuits that achieve , Fourier Sampling circuits achieve (see Proposition 18). This stems from the fact that the amplitudes of a Haarrandom quantum state are approximately distributed as complex normal random variables, whereas the amplitudes of a state produced by a random Fourier Sampling circuit are approximately distributed as real normal random variables.
1.2 Our Techniques
The starting point for our proof of the Tsirelson inequality with a canonical state preparation oracle is a result of Ambainis, Rosmanis, and Unruh [ARU14], which shows that any algorithm that queries can be approximately simulated by a different algorithm that makes no queries, but starts with copies of a resource state that depends on . This resource state consists of polynomially many (in the number of queries to ) states of the form , i.e. copies of in superposition with . Our strategy is to show that if any algorithm solves XHOG given this resource state, then a similar algorithm solves XHOG given copies of alone. Then, we prove a lower bound on the number of copies of needed to solve XHOG. To do so, we argue that if is Haarrandom, then the best algorithm for XHOG given copies of is a simple collisionfinding algorithm: measure all copies of in the computational basis, and output whichever string appears most frequently in the measurement results. For a Haarrandom qubit state, the chance of seeing any collisions is exponentially unlikely (unless the number of copies of is exponentially large in ), and so this does not do much better than measuring a single copy of and outputting the result.
To prove the analogous lower bound for XHOG with a Haarrandom unitary oracle, we show more generally that the canonical state preparation oracles and Haarrandom unitary oracles are essentially equivalent as resources, which may be of independent interest. More specifically, we show that for an qubit state , given query access to , one can approximately simulate (to exponential precision) a random oracle that prepares . By “random oracle that prepares ,” we mean an qubit unitary that acts as but Haarrandom everywhere else. We can construct such a by taking an arbitrary qubit unitary that maps to , then composing it with a Haarrandom unitary on the dimensional subspace orthogonal to .
Our lower bound for Fourier Sampling circuits uses an entirely different technique. We use the polynomial method of Beals et al. [BBC01], which shows that for any quantum algorithm that makes queries to a classical oracle, the output probabilities of the algorithm can be expressed as degree polynomials in the variables of the classical oracle. Our key observation is that the average linear XEB score achieved by such a quantum query algorithm can also be expressed as a polynomial in the variables of the classical oracle. We further observe that this polynomial is constrained by the requirement that the polynomials representing the output probabilities must be nonnegative and sum to . This allows us to upper bound the largest linear XEB score achievable by the maximum value of a certain linear program, whose variables are the coefficients of the polynomials that represent the output probabilities of the algorithm. To upper bound this quantity, we exhibit a solution to the dual linear program.
2 Preliminaries
2.1 Notation
We use to denote the set . We use to denote the identity matrix (of implicit size). We let denote the trace distance between density matrices and , and let denote the diamond norm of a superoperator acting on density matrices (see [AKN98] for definitions). For a unitary matrix , we use to denote the superoperator that maps to . In a slight abuse of notation, if denotes a quantum algorithm (which may consist of unitary gates, measurements, oracle queries, and initialization of ancilla qubits), then we also use to denote the superoperator corresponding to the action of on input density matrices.
2.2 Oracles for Quantum States
We frequently consider quantum algorithms that query quantum oracles. In this model, a query to a unitary matrix consists of a single application of either , , or controlled versions of or . We also consider quantum algorithms that make queries to random oracles. In analogue with the classical random oracle model, such calls are not randomized at each query. Rather, a unitary is chosen randomly (from some distribution) at the start of the execution of the algorithm, and thereafter all queries for the duration of the algorithm are made to .
We now define several types of unitary oracles that we will use. These definitions (and associated lemmas giving constructions of them) have appeared implicitly or explicitly in prior work, e.g. [ARU14, AKKT20, BR20, ABC20]. For completeness, we provide proofs of the constructions.
Definition 4.
For an qubit quantum state , the reflection about , denoted , is the qubit unitary .
In other words, is a eigenstate of , and all states orthogonal to are eigenstates. The following lemma shows that can be simulated given any unitary that prepares from the allzeros state, possibly with unentangled garbage.
Lemma 5.
Let be a unitary that acts as , where and are  and qubit states, respectively. Then one can simulate queries to the reflection using queries to .
Proof.
Consider the unitary . For any qubit state , the action of this unitary on is equivalent to the action of on . So, we can simulate as follows: first use one query to to prepare a copy of . Then, simulate each query to using a query to and to perform . ∎
Definition 6.
For a quantum state , the canonical state preparation oracle for , denoted , is the reflection about the state , where is some canonical state orthogonal to .
Unless otherwise specified, we generally assume that if is an qubit state, then is orthogonal to the space of qubit states under a suitable encoding (see Footnote 2).
The next lemma shows that can be simulated from any oracle that prepares without garbage:
Lemma 7.
Let be an qubit unitary that satisfies . Then one can simulate queries to using queries to .
Proof.
is known, so we may assume that a known unitary acts as . Because is defined as a reflection about , by Lemma 5, it suffices to construct a unitary that prepares any state of the form from using queries to . The following circuit accomplishes this, with :
∎
We introduce the notion of a random state preparation oracle, which, to our knowledge, is new.
Definition 8.
For an qubit state we define a random state preparation oracle for , denoted , as follows. We fix an arbitrary qubit unitary that satisfies , then choose a Haarrandom unitary that acts on the dimensional subspace orthogonal to in the space of qubit states. Finally, we set .
The invariance of the Haar measure guarantees that this distribution over is independent of the choice of , and hence this is welldefined. Note that while we often refer to as a single unitary matrix, really refers to a distribution over unitary matrices. Notice also that if is distributed as a Haarrandom qubit state, then is distributed as a Haarrandom qubit unitary.
2.3 Other Useful Facts
We use the following formula for the distance between unitary superoperators in the diamond norm.
Fact 9 ([Akn98]).
Let and be unitary matrices, and suppose is the distance between and the polygon in the complex plane whose vertices are the eigenvalues of . Then
Finally, we observe that for a Haarrandom qubit quantum state, the informationtheoretically largest linear XEB achievable is .
Fact 10.
Let be a Haarrandom qubit quantum state. Then:
Proof sketch.
For a Haarrandom , the probabilities follow a PorterThomas distribution [AAB19], which is to say that they approach i.i.d. exponential random variables with mean in the limit. By a wellknown result of Rényi [Rén53], the maximum of i.i.d. exponential random variables with mean is distributed as , where are i.i.d. exponentially distributed with mean . In particular, the expected value of the maximum of i.i.d. exponential random variables with mean is , where is the th harmonic number. So, should approach .
In reality, the probabilities are distributed according to a Dirichlet distribution (in fact, uniform on the dimensional probability simplex), which can be sampled from as follows: sample to be i.i.d. exponential random variables, and set . The same proof idea still works, essentially because the denominator concentrates sufficiently well. ∎
3 Canonical State Preparation Oracles
In this section, we prove the quantum supremacy Tsirelson inequality for XHOG with a canonical state preparation oracle for a Haarrandom state. We first sketch the important ideas in the proof. At the heart of our proof is the following lemma, due to Ambainis, Rosmanis, and Unruh [ARU14]. It shows that any quantum algorithm that makes queries to a canonical state preparation oracle can be approximately simulated by a quantum algorithm that makes no queries to , and instead receives various copies of and superpositions of with some canonical orthogonal state.
Lemma 11 ([Aru14]).
Let be a quantum query algorithm that makes queries to . Then for any , there is a quantum algorithm that makes no queries to , and a quantum state of the form:
such that for any state :
So long as , the output of will be arbitrarily close to the output of in trace distance. We will use this and creftypecap 10 to show that if solves XHOG for some , then so does . Then, to prove a lower bound on the number of queries to needed to solve XHOG, it sufficies to instead lower bound , the number of states of the form needed to solve XHOG.
When is a Haarrandom state, notice that the linear XEB depends only on the magnitude of the amplitudes in ; the phases are irrelevant. So, when considering algorithms that attempt to solve XHOG given only a state of the form used in Lemma 11, we might as well assume that the algorithm randomly reassigns the phases on . More formally, define the mixed state as
(1) 
where the expectation is over the diagonal unitaries such that the entries are i.i.d. uniformly random complex phases (and by convention, ). Then, the algorithm’s average linear XEB score on is identical to its average linear XEB score on , because of the invariance of the Haar measure with respect to phases.
Next, we observe that one can prepare by measuring copies of in the computational basis. We prove this in Lemma 12. So, when considering algorithms for XHOG that start with , it suffices to instead consider algorithms that simply measure copies of in the computational basis. Such algorithms are much easier to analyze, because once we have measured the copies of , we can assume (by convexity) that any optimal such algorithm for XHOG outputs a string deterministically given the measurement results. And in that case, clearly the optimal strategy is to output whichever maximizes the posterior expectation of given the measurement results. We analyze this strategy in Lemma 13, and show that roughly copies of are needed to do solve XHOG for bounded away from 2. The intuition is that the posterior expectation of increases only when we see at least twice in the measurement results. However, the probability that any two measurement results are the same is tiny—on the order of —and so we need to measure at least copies of to see any collisions with decent probability.
We now proceed to proving the necessary lemmas.
Lemma 12.
Let be an unknown quantum state, and consider a state of the form:
where are known for , and the vectors form an orthonormal basis. Define the mixed state as above. Then there exists a protocol to prepare by measuring copies of in the computational basis.
To give some intuition, we note that it is simpler to prove Lemma 12 in the case where for all . In that case, can be viewed as an density matrix where both the rows and columns are indexed by strings in . Then, the averaging over diagonal unitaries implies that is obtained from by zeroing out all entries where the index corresponding to the row is not a reordering of the index corresponding to the column. In fact, one can show that is expressible as a mixture of pure states, where each pure state is a uniform superposition over basis states that are reorderings of each other. Moreover, the probability associated with each pure state in this mixture is precisely the probability that one of the reorderings is observed when we measure copies of in the computational basis. So, to prepare , it sufficies to measure and then output the uniform superposition over reorderings of the measurement result.
The proof of Lemma 12 is similar, but we instead have to randomly set some of the measurement results to with probability .
Proof of Lemma 12.
We first describe the protocol. Define . Begin by taking the measurement results to obtain a string . Then, sample a string by setting
independently for each . Let . For each and , define
Finally, prepare and output the state
(2) 
This allows us to express the density matrix output by this protocol as follows:
(3) 
To complete the proof, we want to show that . To see that this holds, first consider an entry of , where . It is equal to
(4)  
(5)  
(6) 
Here, (4) and (5) are simple calculations that follow from the definitions of and . In (6), we use the fact that the entries are independent, uniformly random complex units, and so is if and otherwise, for positive integers . Also, if , then unless .
Evidently, whenever is not a reordering of , because is a mixture of pure states, each of which is a superposition of basis states that are reorderings of one another. So, it remains to show that whenever is a reordering of . Let . Then:
(7)  
(8)  
(9)  
(10)  
(11)  
(12) 
Here, (7) holds because and have disjoint support when ; (8) holds by definition of ; (9) holds by definitions of and ; (10) is a simplification; (11) holds by definition of , and (12) follows from (6), because was assumed to be a reordering of . ∎
Combining Lemma 11 and Lemma 12, we have reduced the problem of lower bounding the number of queries needed to solve XHOG, to lower bounding the number of copies of needed to solve XHOG. The next lemma lower bounds this latter quantity.
Lemma 13.
Let be a Haarrandom qubit quantum state. Consider a quantum algorithm that receives as input and outputs a string . Then:
Proof.
Let . As we have argued above, the algorithm achieves the same linear XEB score on average if it instead begins with the mixed state defined in (1), because of the invariance of the Haar measure with respect to phases. By Lemma 12, the algorithm can prepare by measuring in the computational basis. By a convexity argument, we can assume that the algorithm outputs deterministically given the measurement results.
Suppose the measurement results are . Clearly, the choice of that maximizes is whichever appears most frequently in (with ties broken arbitrarily): the probabilities are distributed according to a distribution, so we can easily compute the posterior expectations . So, it suffices to bound for the algorithm that chooses to be the most frequent measurement result.
Let be a random variable that denotes the frequency of the chosen . Then
(13)  
(14)  
(15)  
(16)  
(17)  
(18)  
(19) 
Here, (13) is valid by the law of total expectation. (14) substitutes the formula for the posterior expectation of a Dirichlet distribution. (15) is valid by linearity of expectation. In (16), we use the crude upper bound that is at most one more than the number of pairwise collisions in (which is tight when the number of collisions is 0 or 1). (17) is valid by linearity of expectation. (18) expands the sum, and computes the collision probabilities in terms of moments of the underlying prior distribution. ∎
We note that one should not expect Lemma 13 to be tight for large (say, ). For example, to achieve , we need at least enough samples to see with good probability. But is negligible unless . More generally, a tight bound on the number of copies of needed to achieve a particular value of seems closely related to the number of measurements of needed to see . This is like a sort of “balls into bins” problem [JK77, RS98] with balls and bins, but where the probabilities associated to each bin follow a Dirichlet prior rather than being uniform.
We finally have the tools to prove the main result of this section.
Theorem 14.
Any quantum query algorithm for XHOG with query access to for a Haarrandom qubit state requires queries.
Proof.
Consider a quantum algorithm that makes queries to and solves XHOG. Choose in Lemma 11 for a constant to be chosen later. By Lemma 11, there is a quantum algorithm that makes no queries to and instead starts with a state (depending on ) such that the trace distance between the output of and is at most for every . In particular, if we view as fixed, then the total variation distance between the outputs and of and , respectively, (as probability distributions over ) is at most . Hence, for every , we may write:
because the sum in the penultimate inequality is twice the total variation distance between and . creftypecap 10 states that for a Haarrandom , . So, for a Haarrandom , we have
In particular, if we choose sufficiently large, then solves XHOG.
Because of the invariance of the Haar measure with respect to phases, still solves XHOG if the pure state is replaced with the mixed state defined in (1). By Lemma 12, this implies the existence of an algorithm that solves XHOG given copies of . By Lemma 13, such an algorithm must satisfy:
Plugging in gives the desired lower bound on :
Lastly, we give an upper bound on the number of queries needed to nontrivially beat the naive algorithm for XHOG with . In fact, the following algorithm works with any oracle that prepares a Haarrandom state (including a Haarrandom unitary), because the algorithm only needs copies of and the ability to perform the reflection . We thank Scott Aaronson for suggesting this approach based on quantum collisionfinding.
Theorem 15.
There is a quantum algorithm for XHOG that makes queries to a state preparation oracle for a Haarrandom qubit state .
Proof.
The quantum algorithm is essentially equivalent to the collisionfinding algorithm of Brassard, Høyer, and Tapp [BHT97]. We proceed by measuring copies of in the computational basis, with results . If any string appears twice in , we output the first such collision. Otherwise, we perform quantum amplitude amplification [BHMT02] on another copy of , where the “good” subspace is spanned by . This uses the reflection , which can be simulated using a constant number of queries to any oracle that prepares (see Lemma 5). Finally, we measure and output the result of the amplitude amplification; call this result . For the purpose of analyzing this algorithm, we say that the algorithm “succeeds” if it either finds a collision in , or if is contained in the good subspace.
We first argue that for any , queries to (for amplitude amplification) are sufficient for the algorithm to succeed with high probability. For this part of the analysis, we view as fixed, and consider only the randomness of the algorithm. Notice that for each , can be placed on inputs for which the output probability is less than , because there are only possible outputs. Thus, by a Chernoff bound, we have that: , because at most half of the probability mass of the output distribution of
In particular, with probability , either the algorithm finds a collision in , or else applications of within the amplitude amplification subroutine are sufficient to measure a good string with arbitrarily high constant probability. So overall, the algorithm can be assumed to succeed with arbitrarily high constant probability.
Next, we argue that the algorithm outputs a string such that . Suppose that instead of performing amplitude amplification at the end, we just measured one additional copy of (still calling the result ) and output if there were no collisions in . Then notice that, conditional on this modified algorithm’s success, the expected XEB score is at least . In symbols, we claim that:
for this modified algorithm, because conditional on success, was observed at least twice in , so is a lower bound on the posterior expectation of the underlying Dirichlet prior distribution on the output probabilities of . But now, we claim that is the same for both the modified algorithm and the original algorithm that uses amplitude amplification. The reason is that amplitude amplification preserves conditional probabilities: the conditional probability distribution of is exactly the same in both algorithms, when conditioned on measuring in the good subspace. So overall, we have that:
where is the arbitrarily small constant failure probability of amplitude amplification. ∎
4 Random State Preparation Oracles
In this section, we show that a canonical state preparation oracle and a random state preparation oracle are essentially equivalent, and use it to prove the quantum supremacy Tsirelson inequality for XHOG with a Haarrandom oracle.
By Lemma 7, for a state , query access to a random state preparation oracle implies query access to the canonical state preparation oracle with constant overhead. The reverse direction is less obvious. We know from the definition of (Definition 8) that one can simulate given any qubit unitary that prepares from . So, it is tempting to let with to argue that allows simulating . However, this is only possible if is orthogonal to . And while we previously argued that we can always find a canonical state that is orthogonal to (Footnote 2), this requires extending the Hilbert space, so that no longer acts on qubits!
On the other hand, a random qubit state will be nearly orthogonal to with overwhelming probability. The next theorem shows that we can use this observation to approximately simulate given .
Theorem 16.
Let be an qubit state. Consider a quantum query algorithm that makes queries to . Then there is a quantum query algorithm that makes queries to such that:
Proof.
Without loss of generality, assume is orthogonal to all qubit states. Let be a Haarrandom qubit state, and let be an arbitrary qubit unitary that satisfies . Write , where is some qubit state orthogonal to , with the phase chosen so that is real and nonnegative. Note that .
Suppose we had an oracle acting on qubits such that . Then we could appeal to Lemma 7 to simulate an oracle that reflects about the state using queries to . Then the composition would be a reflection about the state , which in particular means it would act only on the space of qubit states. Furthermore, we’d have that , so we could simulate perfectly by choosing a random dimensional unitary and replacing calls to with .
Unfortunately, we do not have such an oracle ; we only have . However, we can show that there exists an oracle that is close to , so if we replace all occurrences of with , the resulting unitary we get is close to a random state preparation oracle for . Specifically, we take to be a rotation in the 2dimensional space spanned by and that satisfies . Then, we let .
is a rotation by angle in this 2dimensional subspace, and acts as the identity elsewhere. So, has eigenvalues , , and . The assumption that implies , so by creftypecap 9,
(20) 
Lemma 7 shows that (or more precisely, controlled or its inverse) is used times in implementing queries to , which means we need applications of to implement queries to .
Let denote the quantum algorithm that simulates using (for a random choice of ) in place of , and let denote the quantum algorithm that simulates using in place of . Then
(21)  