pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

Simulating quantum computers with probabilistic methods

Maarten Van den Nest, MPQ

We investigate the boundary between classical and quantum computational power. This work consists of two parts.

First we develop novel classical simulation techniques that are centered around sampling methods. Using these techniques we generate new classes of simulatable quantum circuits, where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example,  we derive a criterion to assess when the concatenation of two simulatable quantum circuits remains simulatable, and use this to show that the concatenation of matchgate, Toffoli, Clifford, bounded-depth circuits, and others, remains simulatable.  We also show that sparse quantum circuits can be simulated efficiently classically, as well as circuits composed of CNOT and exp[iθX] gates.

In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would become classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.