IQIM Postdoctoral and Graduate Student Seminar

Joint IQIM/AWS Seminar

Abstract: Classical simulation techniques are widely used in quantum computation and condensed matter physics. In this talk I will describe algorithms for classically simulating measurement of an n-qubit quantum state in the standard basis, that is, sampling a bit string from the probability distribution determined by the Born rule. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states. Unlike previously known techniques they do not require computation of marginal probabilities. Two classes of quantum states are considered: output states of polynomial-size quantum circuits, and ground states of local Hamiltonians with an inverse polynomial spectral gap. We show that our algorithm can significantly accelerate quantum circuit simulations based on tensor network contraction or low-rank stabilizer decompositions. As another striking consequence we obtain a polynomial-time classical algorithm for instances of Forrelation Problem associated with degree-3 polynomials. To sample ground state probability distributions we employ the so-called fixed-node Hamiltonian construction, previously used in Quantum Monte Carlo simulations to address the fermionic sign problem. We implement the proposed sampling algorithm numerically and use it to sample from the ground state of Haldane-Shastry Hamiltonian with up to 56 qubits.

Joint work with Giuseppe Carleo, David Gosset, and Yinchen Liu, Phys. Rev. Lett. 128, 220503 (2022), arXiv:2207.07044

This week's seminar will be presented by zoom:

https://caltech.zoom.us/j/88407627311?pwd=RGx4MlpSUnBLbDJvdE4rS1FHbWZvUT09

Meeting ID: 884 0762 7311
Passcode: 932356