All reports by Author Martin Schwarz:

__
TR15-173
| 29th October 2015
__

Martin Schwarz#### An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers

__
TR13-154
| 29th October 2013
__

Martin Schwarz, Maarten Van den Nest#### Simulating Quantum Circuits with Sparse Output Distributions

Martin Schwarz

We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce ... more >>>

Martin Schwarz, Maarten Van den Nest

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained ... more >>>