All reports by Author Joseph Fitzsimons:

__
TR18-105
| 30th May 2018
__

Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen#### Quantum proof systems for iterated exponential time, and beyond

__
TR14-181
| 19th December 2014
__

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee#### The space "just above" BQP

Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen

We show that any language in nondeterministic time $\exp(\exp(\cdots\exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - \exp(-C\exp(\cdots\exp(n)))$, ... more >>>

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>