Post History

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)](https://complexityzoo.net/Complexity_Zoo:P#p) problems in polynomial time (i.e. 'efficiently'), a typical (universal, fault tolerant) quantum computer can solve [Bounded-error Quantum Polynomial time (BQP)](https://complexityzoo.net/Complexity_Zoo:B#bqp) problems 'efficiently'.

However, on physical grounds, it appears that quantum computers cannot efficiently solve [Postselected BQP (Post-BQP)](https://complexityzoo.net/Complexity_Zoo:P#postbqp) problems. Thanks to Scott Aaronson's [Quantum Computing, Postselection, and Probabilistic Polynomial-Time](https://arxiv.org/abs/quant-ph/0412187), 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)](https://complexityzoo.net/Complexity_Zoo:A#awpp), which can be considered the [best upper bound of BQP](https://iopscience.iop.org/article/10.1088/1367-2630/17/8/083001). The main assumption behind AWPP is that physics is [tomographically local](https://arxiv.org/abs/1303.1538), although it's reckoned that quantum physics [isn't quite enough to efficiently solve an AWPP problem](https://www.nature.com/articles/s41534-019-0156-9).

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?**