Difference between 'AWPP' and standard quantum physics
Quantum Computers are considered a more powerful type of computer than so called 'classical' computers. While a typical classical computer could be considered as a black box that can solve Polynomial time (P) problems in polynomial time (i.e. 'efficiently'), a typical (universal, fault tolerant) quantum computer can solve Bounded-error Quantum Polynomial time (BQP) problems 'efficiently'.
However, on physical grounds, it appears that quantum computers cannot efficiently solve Postselected BQP (Post-BQP) problems. Thanks to Scott Aaronson's Quantum Computing, Postselection, and Probabilistic Polynomial-Time, it's known that this is largely due to the requirement that efficiently solving such a problem would require a massive fundamental change in the laws of physics:
- the probability of a successful measurement would be $\lvert\psi\rvert^p$ for some $p\neq 2$, instead of the usual $p=2$ in quantum physics.
- quantum physics would allow for linear but non-unitary transformations as well as unitary ones.
It turns out that there are other complexity classes between BQP and Post-BQP. Perhaps the most interesting of these is Almost-Wide Probabilistic Polynomial (AWPP), which can be considered the best upper bound of BQP. The main assumption behind AWPP is that physics is tomographically local, although it's reckoned that quantum physics isn't quite enough to efficiently solve an AWPP problem.
I'm interested in learning about the differences (if any) between (current) quantum physics and a physical 'AWPP-theory', so my question here is this: if we lived in a universe where physics naturally described AWPP computation, what would the physical and computational differences (if any) be between such a universe and the one we actually live in?
0 answers
0 comment threads