skip to main content

IQIM Postdoctoral and Graduate Student Seminar

Wednesday, January 18, 2023
11:00am to 12:00pm
Add to Cal
Online Event
How to simulate quantum measurement without computing marginals
Sergey Bravyi, IBM Quantum,

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:

Meeting ID: 884 0762 7311
Passcode: 932356

For more information, please contact Marcia Brown by phone at 626-395-4013 or by email at [email protected].