I was looking at this lecture note where the author gives an oracle separation between $\mathsf{BQP}$ and $\mathsf{NP}$. He hints at how "standard diagonalisation techniques can be used to make this rigorous".

Can someone detail a diagonalisation technique that ought to be used? There should intuitively be important differences between the ones used to put something outside classical complexity classes and the ones used to put something outside $\mathsf{BQP}$. Specifically, given that Grover's algorithm is optimal, I am looking for a diagonalisation technique such that we can construct an oracle $A$ for which $\mathsf{NP}^{A} \not\subseteq \mathsf{BQP}^{A}$.


1 Answer 1


It seems to me that the diagonalisation arguments that can be used are only slightly different from a standard one, e.g. such as can be found in these lecture notes about the Baker–Gill–Solovay Theorem (i.e., that there are oracles $A$ for which $\mathsf P^A = \mathsf{NP}^A$ and also oracles $A$ for which $\mathsf P^A \ne \mathsf{NP}^A$). Basically, you have to describe how to 'engineer' an adversarial input a little differently.

Here's how we might use this approach to prove the existence of an oracle $A$ for which $\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$. For any oracle $A$, define a language $$ L_A = \Bigl\{ 1^n \;\Big\vert\; \exists z \in \{0,1\}^n : A(z,0) = (z,1)\Bigr\} . $$ It is clear that $L_A \in \mathsf{NP}^A$ for the simple reason that a nondeterministic Turing machine can examine whether the input is of the form $1^n$ for some $n$, and then guess a string $z \in \{0,1\}^n$ for which $A(z,0) = (z,1)$ if such $z$ exists. The goal is to show that $L_A$ cannot be decided in polynomial time, with bounded error, by a uniform unitary circuit family, using the $O(2^{n/2})$ lower bound on the search problem.

  1. Let $c,N > 0$ be such that the search problem on oracles with $n$-bit inputs requires at least $c 2^{n/2}$ oracle queries to decide correctly (with probability at least 2/3), for all $n > N$.

  2. Let $\mathbf C^{(1)}\!$, $\mathbf C^{(2)}\!$, $\ldots$ be an enumeration of all unitary oracle circuit families $\mathbf C^{(k)} \!= \{ C^{(k)}_n \}_{n \geqslant 0 }$, such that the gate-sequence of the circuit $C^{(k)}_n\!$ acting on $n$-bit inputs can be produced in time strictly less than $c 2^{n/2}$. (This time bound relates to the 'uniformity' condition, where we will be interested in circuits can be computed by a deterministic Turing machine in polynomial time — a stronger condition than we impose here. The enumeration of these circuit families could be done, for instance, by representing them indirectly by the deterministic Turing machines $\mathbf T^{(k)}$ which produce their gate sequences, and enumerating those.) We enumerate the circuit families so that each circuit family occurs infinitely often in the enumeration.

    • From the run-time bounds on the description of the gate sequence, it follows in particular that $C^{(k)}_n$ has fewer than $c 2^{n/2}$ gates for all $k$, and in particular makes fewer than $c 2^{n/2}$ queries to the oracle.

    • For any $n$, consider the circuit $C^{(n)}_n\!$. From the lower bound on the search problem, we know that for $n > N$ there are possible values of the oracle function $f: \{0,1\}^n \to \{0,1\}$ evaluated by the oracle, such that with probability 2/3, the output produced by $C^{(n)}_n\!$ on input $1^n$ is not the correct answer to whether $\exists z \!\in\! \{0,1\}^n\!:\! f(z) \!=\! 1$.

    • For each $n > N$, select such a function $f_n$ for which $C^{(n)}_n$ "fails" in this way.

  3. Let $A$ be an oracle which, on inputs of size $n > N$, evaluates $f_{\!\!\:n\!\:}$.

Having constructed $A$ in this way, each circuit family $\mathbf C^{(n)}$ fails to correctly decide $L_A$ with probability at least 2/3, for some $n > N$ (and infinitely many such $n$ in fact). Then none of the circuit families $\mathbf C^{(k)}$ correctly decide $L_A$ with success probability bounded below by 2/3 on all inputs, so that $L_A$ cannot be solved with such bounds by any uniform unitary circuit family constructible in time $p(n)$.

Thus, $L_A \notin \mathsf{BQP}^A$, from which it follows that $\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.