Results 81 - 90 of 24267
We give quasipolynomial-time classical algorithms for estimating thermal expectations of the SYK model—a random fermionic system—despite the presence of a sign problem and large quantum circuit lower bounds. Complementing this result, we describe disordered systems (random Pauli Hamiltonians) whose Gibbs states transition from classically easy to quantumly hard as they are cooled, leaving no room for quantum advantage. Finally, we will discuss where to look for quantum advantage in Gibbs states of random Hamiltonians.
"In this talk, I’ll discuss two of my recent papers on proving mixing times for quantum spin systems, by estimating the spectral gap of a dissipative quantum Gibbs sampler [CKG23]. In particular, for arbitrary all-to-all quantum systems at sufficiently high temperatures, and one-dimensional quantum systems at any temperature.
At the heart of both proofs is the introduction of a “pseudo” Lindbladian which does not generate a CPTP map, and yet admits much sharper locality properties instrumental in proving spectral gaps. I’ll conclude with an outlook towards the quantum and classical simulation of the systems studied.
Based on joint work with Chi-Fang Chen
2510.08533 and 2606.26090."
"A key issue of current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation. This limits the regime in which the experiments can be verified to precisely the regime in which they are also simulatable. An important outstanding question is therefore to find quantum advantage schemes that are also classically verifiable. We design a new quantum advantage proposal--Hidden Code Sampling--whose output distribution is conditionally peaked. These peaks enable verification in far less time than it takes for full simulation. Assuming certain conjectures, it can even be made efficient. At the same time, we show that exactly sampling from the output distribution is classically hard unless the polynomial hierarchy collapses, and we propose a plausible conjecture regarding average-case hardness.
Our scheme is based on ideas from quantum error correction. The required quantum computations are closely related to quantum fault-tolerant circuits and can potentially be implemented transversally. Our proposal may thus give rise to a next generation of quantum advantage experiments en route to full quantum fault tolerance."