A new platform for quantum electronics based on 2D semiconductors
Location: QNC 0101
IQC faculty host: Adam Wei Tsen
Extending boundaries in quantum networks
Location: QNC 0101
Quantum telescopes and quantum imaging
Location: QNC 0101
Does provable absence of barren plateaus imply classical simulability?
Location: QNC 0101
Machina Ex Quanta: Rise of the Quantum Boltzmann Machines
Location: QNC 0101
Beyond Binary Quantum Information in Superconducting Circuits: Taking the Transmon for a Spin
Location: QNC 0101
Programmable Atom Interferometry in a Multidimensional Optical Lattice
Location: QNC 0101
Spin, photons and phonons: diamond nanophotonics
Location: QNC 0101
Quantum computing for quantum chemistry
Location: QNC 0101
QNC building, 200 University Ave. Room QNC 1201 Waterloo
Understanding the dynamics of quantum many-body systems is one of the fundamental objectives of physics. The existence of an efficient quantum algorithm for simulating these dynamics with reasonable resource requirements suggests that this problem might be among the first practically relevant tasks quantum computers can tackle. Although an efficient classical algorithm for simulating such dynamics is not generally expected, the classical hardness of many-body dynamics has been rigorously proven only for certain commuting Hamiltonians. In this talk, I will show that computing the output distribution of quantum many-body dynamics is classically difficult, classified as #P-hard, also for a large class of non-commuting many-body spin Hamiltonians. Our proof leverages the robust polynomial estimation technique and the #P-hardness of computing the permanent of a matrix. By combining this with the anticoncentration conjecture of the output distribution, I will argue that sampling from the output distribution generated by the dynamics of a large class of spin Hamiltonians is classically infeasible. Our findings can significantly reduce the number of qubits required to demonstrate quantum advantage using analog quantum simulators.