Consider a polynomial time quantum circuit on $n$ qubits. The class of circuits under consideration encompasses the complexity class $\mathsf{BQP}$.

Now, say we have an $n-1$ qubit polynomial time circuit (for example, say, after being given an $n$ qubit polynomial time circuit, we always throw away one qubit.) Is this circuit still $\mathsf{BQP}$ (or something like $\mathsf{BQP}_{n-1}$ — where this complexity class means all the computation you can do with $n-1$ qubits)? Does it make sense to ask such a question?

Note that if we only have $\log n$ qubits, the class is simulable in classical polynomial time. But I’m not sure how to coarse grain the hardness depending on the number of qubits. My intuition is that $n$ qubit computations cannot, in general, be done with $n-1$ qubits, but none of these classes should be classically simulable.


1 Answer 1


I don't think your hierarchy is all that well-defined as-is; I think you're confusing the width $n$ of the circuit with the length or depth $d$ of the circuit.

For example for a fixed universal gate set and a given $n$ we define the quantum (and classical!) complexity class based on the relationship between $n$ and the depth $d$ of the circuits. BQP problems can be solved when $d$ is polynomially related to $n$. This doesn't change when we reduce $n$ to $n-1$, because $n$ and $n-1$ are polynomially related to each other, and if, say, there is some polynomial $p$ such that the depth $d=p(n)$, then surely there is another polynomial $p'$ where we have $d'=p(n-1)=p'(n)$, because polynomials are closed under composition and $n-1$ is a polynomial in $n$.

But, as you hint at, this does change when the depth $d$ is related to a polynomial of $\log n$, because $n$ and $\log n$ are not polynomially related. Nonetheless and perhaps where you might have been wanting to go to, there is a non-trivial fine-grained hierarchy regarding these depths $d$ and their relationship to $n$.

For example, again fixing your universal gate set, from the time-hierarchy theorem you can decide problems when the depth $d=n$ than when the depth $d=n-1$. You can decide more problems when the depth $d=n^2-1$ than when the depth $d=n^2-2$. You can even decide more problems when $d=2^n+1$ than when $d=2^n$.

  • $\begingroup$ To do a small sanity check, does your argument mean that any computation (encompassing BQP) that I can do with $n$ qubits and depth $d = \text{poly}(n)$ can be done with $n-1$ qubits and depth $d' = \text{poly}(n-1)$, where $d' \geq d$? Is there any formal proof of this fact? It doesn't immediately feel intuitive to me $\endgroup$
    – BlackHat18
    May 13, 2023 at 17:13
  • $\begingroup$ All else being equal you can do more with a deeper circuit - this is the time-hierarchy theorem. So, your intuition is right. But I think you and I are getting confused as to what's meant by "$\mathrm{poly}$". Here, this means the class of all polynomials in a single variable. So, it's an abuse of notation on my part to say $d=\mathrm{poly\:} n$; it should be something more like $d\in\mathrm{poly\:} n$, the depth $d$ is equal to the evaluation of some polynomial $p$, evaluated at the number of inputs $n$, e.g. $d=p(n)$. $\endgroup$ May 13, 2023 at 19:04
  • $\begingroup$ The reason that we like to refer to the class $\mathrm{poly}$ is because it has some nice closure properties. Indeed this is what I mean when I say that both $n$ and $n-1$ are polynomially related. I could say that the depth $d'=p(n-1)=p'(n)$, where $p'(n)$ is still another polynomial in $n$. $\endgroup$ May 13, 2023 at 19:07

Your Answer

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

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