Strong Simulation

T. H. Johnson, Jacob Biamonte, Stephen R. L. Clark +1 more

Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered, and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in P this would imply that all problems in NP and #P could be solved in polynomial time.

Stefan Hillmich, Robert Wille

Yi Deng

Cupjin Huang, Michael Newman, Márió Szegedy

We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.

S. D. Barrett, Klemens Hammerer, Sarah K. Harrison +2 more

As the realization of a fully operational quantum computer remains distant, quantum simulation, whereby one quantum system is engineered to simulate another, becomes a key goal of great practical importance. Here we report on a variational method exploiting the natural physics of cavity QED architectures to simulate strongly interacting quantum fields. Our scheme is broadly applicable to any architecture involving tunable and strongly nonlinear interactions with light; as an example, we demonstrate that existing cavity devices could simulate models of strongly interacting bosons. The scheme can be extended to simulate systems of entangled multicomponent fields, beyond the reach of existing classical simulation methods.

Melinda Hagedorn