Classical Simulation and Complexity of Quantum Computations

Alan M. Kadin

•Classical superconducting circuit simulators are powerful and available. •Include Josephson junction as basic element. •Provide efficient time-domain simulations of complex circuits. •May show effects otherwise attributed to quantum circuits. •Circuits of coupled superconducting qubits are being developed for quantum computing (QC). •Entangled quantum theory incompatible with classical simulators. •Quantum model difficult to simulate on conventional computers for complex circuits already being tested. •Classical circuit simulations should provide the baseline to compare with quantum effects, but this is seldom done. •Coupled oscillators are delocalized even in classical limit.

Yongshan Ding, Frederic T. Chong

孝志 三原

Ryan L. Mann

This thesis explores the relationship between quantum computation and combinatorial structures, with the goal of improving our understanding of the complexity of quantum computation. We begin by studying the case when the complexity of combinatorial structures can be used to provide evidence for the hardness of classically simulating quantum computations. To this end, we show that the complexity of evaluating multiplicative-error approximations of Jones polynomials can be used to bound the classical complexity of simulating random quantum computations. We then proceed by studying the contrary case, that is, when do the combinatorial structures allow for an efficient classical simulation of quantum computations? We establish an efficient deterministic approximation algorithm for the Ising model partition function with complex parameters when the interactions and external fields are absolutely bounded close to zero. This provides an efficient classical algorithm for simulating a class of quantum computations with bounded interactions between the qubits. In the second part of this thesis, we present some independent results on the efficient preparation of Fock states with a high number of photons from a resource of single photons. These Fock states are a fundamental resource in many quantum information protocols.

Tzvetan S. Metodi, Arvin I. Faruque, Frederic T. Chong

Ryan L. Mann, Michael J. Bremner

There is a natural relationship between Jones polynomials and quantum computation. We use this relationship to show that the complexity of evaluating relative-error approximations of Jones polynomials can be used to bound the classical complexity of approximately simulating random quantum computations. We prove that random quantum computations cannot be classically simulated up to a constant total variation distance, under the assumption that (1) the Polynomial Hierarchy does not collapse and (2) the average-case complexity of relative-error approximations of the Jones polynomial matches the worst-case complexity over a constant fraction of random links. Our results provide a straightforward relationship between the approximation of Jones polynomials and the complexity of random quantum computations.