QSE Quantum Seminar: Mini algorithms-fest - John Martyn and Jonathan Lu

Please join us for the QSE Center Quantum Seminar with John Martyn from Harvard University & Pacific Northwest National Lab (PNNL) who will give the talk "A Little Incoherence Goes a Long Way: Enhancing Quantum and Classical Algorithms with Randomization" and Jonathan Lu from MIT who will give the talk "Hamiltonian Decoded Quantum Interferometry" on Thursday November 13 from 12:00pm to 2:00pm
Location: BS 160

Pizzas will be available at 12:00pm. The first talk will start at 12:10pm. All PhDs, postdocs, students, group leaders, and PIs are welcome to join us.

ABSTRACT:
1. "A Little Incoherence Goes a Long Way: Enhancing Quantum and Classical Algorithms with Randomization" - John Martyn
In studying quantum systems, either with quantum algorithms or classical methods, we typically focus on coherent unitary dynamics. Decoherence arising from randomness or environmental noise is often viewed as detrimental, and sought to be suppressed. In this talk, I will demonstrate the opposite: incoherence, in small doses, is beneficial to both quantum and classical algorithms. I will illustrate this statement in two contexts. First, in quantum algorithms based on quantum signal processing, I will show how using a randomized channel, instead of the standard deterministic one, reduces costs (e.g., gate count) by 50%. Second, in the context of neural-network quantum states, I will prove how using a variational mixed state representation, instead of a pure state, provides more accurate estimates of ground state observables. In aggregate, these results reveal the surprising utility of incoherence in quantum information, and suggest wider applications in algorithm development. 

2. "Hamiltonian Decoded Quantum Interferometry" - Jonathan Lu
We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a degree-d polynomial P and Hamiltonian H, HDQI prepares a density matrix proportional to P^2(H) by solving a combination of two tasks: decoding weight-d errors on a classical code defined by H, and preparing a pilot state that encodes the anti-commutation structure of H.     Choosing P(x) to approximate exponentials yields Gibbs states; other choices prepare approximate ground states, microcanonical ensembles, and other spectral filters.
For local Hamiltonians, the corresponding decoding problem is that of LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians—including the toric code and Haah's cubic code—but we also develop a matching efficient classical algorithm for this task. For a non-commuting semiclassical spin glass and commuting stabilizer Hamiltonians with quantum defects, HDQI prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical pre-processing. These results position HDQI as a versatile algorithmic primitive, and as the first extension of Regev's reduction to non-abelian groups.

BIOS:
John Martyn is a Quantum Initiative Fellow at Harvard University, and a Staff Scientist of Pacific Northwest National Laboratory. In his research, he explores the theoretical side of quantum information, with a focus on developing quantum and classical algorithms for simulating physics and solving hard computational problems. He recently received his PhD in physics from MIT, advised by Isaac Chuang, during which he spent time interning at IBM Quantum and Google X. In the beforetimes, he received a BS in physics from the University of Maryland, and worked as a student researcher at Caltech.
Jonathan Lu is a Ph.D. student in Applied Mathematics at MIT co-advised by Peter Shor and Misha Lukin. He works on algorithmic aspects of quantum coding theory, especially in connection to quantum algorithms, complexity, and cryptography. Recent work includes the use of error correction to devise new quantum physics algorithms, and rigorous analyses of the average-case complexity of decoding quantum codes.