Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR14-181 | 19th December 2014
Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

The space "just above" BQP

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

ISSN 1433-8092 | Imprint