When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to which then produces an output boolean vector, and $C$ must be constructed from some basic gates (and or not).

It's fascinating that if we assume our input vector is not a boolean vector $v \in \lbrace 0,1\rbrace ^n$ but rather an exponentially large complex vector $v \in \mathbb{C}^{2^n}$, BUT we also now restrict our circuits to strictly be complex unitary matrices, we end up with a stronger model of computation, BQP, which can solve problems that we currently don't know to be solvable in P.

Subjectively what happened here, was we made the state of our program much larger. After all $\mathbb{C}^{2^n}$ is for most n way bigger state than $\lbrace 0,1 \rbrace^n$, but then we made our circuit much weaker, that is we can't do arbitrary circuits anymore we can ONLY multiply with complex unitary matrices. Between making the state bigger (obviously strengthening your computational power power), and the circuit choice smaller (which would weaken your computational power), we all said and done end up with a slight net gain in computational power (factoring is now polytime, but NP has not yet obviously become accessible!).

So now this leads to the natural question, can the process: "expand state size", "reduce choice of operators" yield other interesting complexity classes that are stronger than BQP but don't collapse NP to their P?

An example of what I would look for could be the following: what if the state vector is $\mathbb{C}^{2^{2^n}}$ but the gates that we get to use are a much more restricted class than unitary matrices (ex: only unitary matrices with determinant 1). Does this model computation allow us to solve problems in polynomial time that are known to be intractable to a quantum computer?

Perhaps the example I give may not clearly give an answer so feel free to swap out the underlying field $\mathbb{C}$ with some other ring of your choice, and then restrict the operators as you see fit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.