# Confusion regarding hardness of BQP

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.

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$$.
• 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 May 13, 2023 at 17:13
• 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)$. May 13, 2023 at 19:04
• 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$. May 13, 2023 at 19:07