Perimeter Institute Quantum Discussions

Finding ground states of quantum many-body systems is one of the most important---and one of the most notoriously difficult---problems in physics, both in scientific research and in practical applications.  Indeed, we know from a complexity-theoretic perspective that all methods  (quantum or classical) must necessarily fail to find the ground state efficiently in general. The ground state energy problem is already NP-hard even for classical, frustration-free, local Hamiltonians with constant spectral gap. For general quantum Hamiltonians, the problem becomes QMA-hard.

Nonetheless, as ground state problems are of such importance, and classical algorithms are often successful despite the theoretical exponential worst-case complexity, a number of quantum algorithms for the ground state problem have been proposed and studied. From quantum phase estimation-based methods, to adiabatic state preparation, to dissipative state engineering, to the variation quantum eigensolver (VQE), to quantum/probabilistic imaginary-time evolution (QITE/PITE).

Dissipative state engineering was first introduced in 2009 by Verstraete, Cirac and Wolf and by Kraus et al. However, it only works for the restricted class of frustration-free Hamiltonians.

In this talk, I will show how to construct a dissipative state preparation dynamics that provably produces the correct ground state for arbitrary Hamiltonians, including frustrated ones. This leads to a new quantum algorithm for preparing ground states: the Dissipative Quantum Eigensolver (DQE). DQE has a number of interesting advantages over previous ground state preparation algorithms:

• The entire algorithm consists simply of iterating the same set of   simple local measurements repeatedly.
• The expected overlap with the ground state increases monotonically with the length of time this process is allowed to run.
• It converges to the ground state subspace unconditionally, without any assumptions on or prior information about the Hamiltonian (such as spectral gap or ground state energy bound).
• The algorithm does not require any variational optimisation over parameters.
• It is often able to find the ground state in low circuit depth in practice.
• It has a simple implementation on certain types of quantum hardware, in particular photonic quantum computers.
• It is immune to errors in the initial state.
• It is inherently fault-resilient, without incurring any fault-tolerance overhead. I.e.\ not only is it resilient to errors on the quantum state, but also to faulty implementations of the algorithm itself; the overlap of the output with the ground state subspace degrades smoothly with the error rate, independent of the total run-time.

I give a mathematically rigorous analysis of the DQE algorithm and proofs of all the above properties, using non-commutative generalisations of methods from classical probability theory.

---

Zoom link https://pitp.zoom.us/j/96022753460?pwd=SWlUVkVta1RyY3dsWUJWckRqOHdNdz09

Systems in thermal equilibrium at non-zero temperature are described by their Gibbs state. For classical many-body systems, the Metropolis-Hastings algorithm gives a Markov process with a local update rule that samples from the Gibbs distribution. For quantum systems, sampling from the Gibbs state is significantly more challenging. Many algorithms have been proposed, but these are more complex than the simple local update rule of classical Metropolis sampling, requiring non-trivial quantum algorithms such as phase estimation as a subroutine.

Here, we show that a dissipative quantum algorithm with a simple, local update rule is able to sample from the quantum Gibbs state. In contrast to the classical case, the quantum Gibbs state is not generated by converging to the fixed point of a Markov process, but by the states generated at the stopping time of a conditionally stopped process. This gives a new answer to the long-sought-after quantum analogue of Metropolis sampling. Compared to previous quantum Gibbs sampling algorithms, the local update rule of the process has a simple implementation, which may make it more amenable to near-term implementation on suitable quantum hardware. We also show how this can be used to estimate partition functions using the stopping statistics of an ensemble of runs of the dissipative Gibbs sampler. This dissipative Gibbs sampler works for arbitrary quantum Hamiltonians, without any assumptions on or knowledge of its properties, and comes with certifiable precision and run-time bounds.
This talk is based on 2304.04526, completed in collaboration with Jan-Lukas Bosse and Toby Cubitt.

Zoom Link: https://pitp.zoom.us/j/96780945341?pwd=NG9SUjE4SkVia3VqazNXUFNUamhRdz09

We investigate the evolution of quantum information under Pauli measurement circuits. We focus on the case of one- and two-dimensional systems, which are relevant to the recently introduced Floquet topological codes. We define local reversibility in context of measurement circuits, which allows us to treat finite depth measurement circuits on a similar footing to finite depth unitary circuits. In contrast to the unitary case, a finite depth locally reversible measurement sequence can implement a translation in one dimension. A locally reversible measurement sequence in two dimensions may also induce a flow of logical information along the boundary. We introduce "measurement quantum cellular automata" which unifies these ideas and define an index in one dimension to characterize the flow of logical operators. We find a Z_2 bulk invariant for Floquet topological codes which indicates an obstruction to having a trivial boundary. We prove that the Hastings-Haah honeycomb code belong to a class with such obstruction, which means that any boundary must have either non-local dynamics, period doubled, or admits boundary flow of quantum information.

Zoom Link: https://pitp.zoom.us/j/96083249406?pwd=MnhYbTEyU05ybVdyUlE3UGZrdEhPdz09

A key subroutine in quantum computing, especially in quantum simulation, is to prepare thermal states or ground states of Hamiltonians. Today, I will talk about a new family of quantum algorithms for this task. Physically, our algorithms distill the essence of system-bath interaction by simulating an effective Lindbladian; computationally, our algorithms are quantum analogs of classical Markov chain Monte Carlo sampling. Given the ubiquity of thermodynamics and the triumph of classical Monte Carlo methods, we anticipate that quantum thermal state preparation will become indispensable in quantum computing. 

Joint work with Michael J. Kastoryano, Fernando G.S.L. Brandão, and András Gilyén. https://arxiv.org/abs/2303.18224 

Zoom Link: https://pitp.zoom.us/j/91641127738?pwd=cExPM3Bvd3BaYnJYS0U0UlBiVTJ0QT09

I will introduce a family of dual-unitary circuits in 1+1 dimensions which are invariant under the joint action of Lorentz and scale transformations. With the same dual unitaries I will construct tensor-network states for this 1+1 model and interpret them as spatial slices of curved 2+1 discrete geometries. These tensor-network states satisfy the Ryu-Takayanagi conjecture outside event horizons, but the geometry of the network is also well defined inside the horizon. The dynamics of the circuit induces a natural dynamics on these geometries which reproduces GR phenomena like the gravitational redshift, the formation of black holes and the growth of their throat.

Zoom link:  https://pitp.zoom.us/j/92034586204?pwd=eEo0NzVjeFkxWVJnY0hjOUhodXNWdz09

We study the behavior of errors in the quantum simulation of  spin systems with long-range multibody interactions resulting from the  Trotter-Suzuki decomposition of the time evolution operator. We  identify a regime where the Floquet operator underlying the Trotter  decomposition undergoes sharp changes even for small variations in the  simulation step size. This results in a time evolution operator that  is very different from the dynamics generated by the targeted  Hamiltonian, which leads to a proliferation of errors in the quantum  simulation. These regions of sharp change in the Floquet operator,  referred to as structural instability regions, appear typically at  intermediate Trotter step sizes and in the weakly interacting regime,  and are thus complementary to recently revealed quantum chaotic  regimes of the Trotterized evolution [L. M. Sieberer et al. npj  Quantum Inf. 5, 78 (2019); M. Heyl, P. Hauke, and P. Zoller, Sci. Adv.  5, eaau8342 (2019)]. We characterize these structural instability  regimes in p-spin models, transverse-field Ising models with  all-to-all p-body interactions, and analytically predict their  occurrence based on unitary perturbation theory. We further show that  the effective Hamiltonian associated with the Trotter decomposition of  the unitary time-evolution operator, when the Trotter step size is  chosen to be in the structural instability region, is very different  from the target Hamiltonian, which explains the large errors that can  occur in the simulation in the regions of instability. These results  have implications for the reliability of near-term gate based quantum  simulators, and reveal an important interplay between errors and the  physical properties of the system being simulated.

Zoom link:  https://pitp.zoom.us/j/92045582127?pwd=WDUxcnlIeXdnVWM3WGJoSFVMNDE2dz09

We present a quantum algorithm for simulating the classical dynamics of 2^n coupled oscillators (e.g.,  masses coupled by springs). Our approach leverages a mapping between the Schrodinger equation and Newton's equations for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time, for a specification of the problem that we prove is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2^n modes.

Zoom link:  https://pitp.zoom.us/j/91882209363?pwd=UndJRVdaZW04RGtpL0M2SE52RDJwZz09

Entanglement entropies of two-dimensional gapped ground states are expected to satisfy an area law, with a constant correction term known as the topological entanglement entropy (TEE). In many models, the TEE takes a universal value that characterizes the underlying topological phase. However, the TEE is not truly universal: it can differ even for two states related by constant-depth circuits, which are necessarily in the same phase. The difference between the TEE and the value predicted by the anyon theory is often called the spurious topological entanglement entropy. We show this spurious contribution is always nonnegative, thus the value predicted by the anyon theory provides a universal lower bound. This observation also leads to a definition of TEE which is invariant under constant-depth quantum circuits.

Based on a joint work with Daniel Ranard (MIT), Michael Levin (U Chicago), Ting-Chun Lin (UCSD), and Bowen Shi (UCSD)

Zoom link:  https://pitp.zoom.us/j/93809342984?pwd=QXJkK0ZYR3QzdjlUUWlkMEFXMWRnQT09

For n≥3, we demonstrate the existence of quantum codes which are local in dimension n with V qubits, distance V^{(n−1)/n}, and dimension V^{(n−2)/n}, up to a polylog(V) factor. The distance is optimal up to the polylog factor. The dimension is also optimal for this distance up to the polylog factor. The proof combines the existence of asymptotically good quantum codes, a procedure to build a manifold from a code by Freedman-Hastings, and a quantitative embedding theorem by Gromov-Guth.

Zoom link:  https://pitp.zoom.us/j/96227350980?pwd=TEFtamRmTXg3dnBMNEhKUkpHbmVoZz09

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing using no or few additional quantum resources, in contrast to fault-tolerant schemes that come along with heavy overheads. Error mitigation has been successfully applied to reduce noise in near-term applications. 

In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively `undone' for larger system sizes. We set up a framework that rigorously captures large classes of error mitigation schemes in use today. The core of our argument combines fundamental limits of statistical inference with a construction of families of random circuits that are highly sensitive to noise.

We show that even at poly loglog depth, a super-polynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. They also impact other near-term applications, constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.

Zoom link:  https://pitp.zoom.us/j/95736148335?pwd=akZLaHE5aStNQVZOeVFETlltNzVwdz09

Recent progress in the development of quantum technologies has enabled the direct investigation of dynamics of increasingly complex quantum many-body systems. This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage. Here we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian. For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error. In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb–Robinson bound. Our results use cluster expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence. This has important physical consequences besides our efficient algorithms. In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.

Joint work with Dominik S. Wild (arXiv:2210.11490)

Zoom link:  https://pitp.zoom.us/j/97166113711?pwd=UEg4NnJlQkkxQXFnN2xXYTBxS001Zz09

We present an efficient machine learning (ML) algorithm for predicting any unknown quantum process over n qubits. For a wide range of distributions D on arbitrary n-qubit states, we show that this ML algorithm can learn to predict any local property of the output from the unknown process, with a small average error over input states drawn from D. The ML algorithm is computationally efficient even when the unknown process is a quantum circuit with exponentially many gates. Our algorithm combines efficient procedures for learning properties of an unknown state and for learning a low-degree approximation to an unknown observable. The analysis hinges on proving new norm inequalities, including a quantum analogue of the classical Bohnenblust-Hille inequality, which we derive by giving an improved algorithm for optimizing local Hamiltonians. Overall, our results highlight the potential for ML models to predict the output of complex quantum dynamics much faster than the time needed to run the process itself.

Zoom link:  https://pitp.zoom.us/j/93857777354?pwd=c044blZuQVhLS200ME4vN25uaGJudz09