Confusion regarding hardness of BQP

Question

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.

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$.