Quantum phase estimation is at the heart of most quantum algorithms with exponential speedup. In this paper we demonstrate how to utilize it to compute the dynamical response functions of many-body quantum systems. Specifically, we design a circuit that acts as an efficient quantum generative model, providing samples out of the spectral function of high rank observables in polynomial time. This includes many experimentally relevant spectra such as the dynamic structure factor, the optical conductivity, or the NMR spectrum. Experimental realization of the algorithm, apart from logarithmic overhead, requires doubling the number of qubits as compared to a simple analog simulator.
Quantum phase estimation is at the heart of most quantum algorithms with exponential speedup. In this paper we demonstrate how to utilize it to compute the dynamical response functions of many-body quantum systems. Specifically, we design a circuit that acts as an efficient quantum generative model, providing samples out of the spectral function of high rank observables in polynomial time. This includes many experimentally relevant spectra such as the dynamic structure factor, the optical conductivity, or the NMR spectrum. Experimental realization of the algorithm, apart from logarithmic overhead, requires doubling the number of qubits as compared to a simple analog simulator.
The efficient probing of spectral features is important for characterising and understanding the structure and dynamics of quantum materials. In this work, we establish a framework for probing the excitation spectrum of quantum many-body systems with quantum simulators. Our approach effectively realises a spectral detector by processing the dynamics of observables with time intervals drawn from a defined probability distribution, which only requires native time evolution governed by the Hamiltonian without ancilla. The critical element of our method is the engineered emergence of frequency resonance such that the excitation spectrum can be probed. We show that the time complexity for transition energy estimation has a logarithmic dependence on simulation accuracy and how such observation can be guaranteed in certain many-body systems. We discuss the noise robustness of our spectroscopic method and show that the total running time maintains polynomial dependence on accuracy in the presence of device noise. We further numerically test the error dependence and the scalability of our method for lattice models. We present simulation results for the spectral features of typical quantum systems, either gapped or gapless, including quantum spins, fermions and bosons. We demonstrate how excitation spectra of spin-lattice models can be probed experimentally with IBM quantum devices.
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. The functional form of these response functions can be mapped to a corresponding eigenproblem of a Hermitian matrix H , thus suggesting the use of quantum phase estimation. Our proposed quantum algorithm operates in the standard s -sparse, oracle-based query access model. For a network of N oscillators with maximum norm ∥ H ∥ max , and when the eigenvalue tolerance ɛ is much smaller than the minimum eigenvalue gap, we use O ( log ( N s ∥ H ∥ max / ɛ ) algorithmic qubits and obtain a rigorous worst-case query complexity upper bound O ( s ∥ H ∥ max / ( δ 2 ɛ ) ) up to logarithmic factors, where δ denotes the desired precision on the coefficients appearing in the response functions. Crucially, our proposal does not suffer from the infamous state preparation bottleneck and can as such potentially achieve large quantum speedups compared to relevant classical methods. As a proof-of-principle of exponential quantum speedup, we show that a simple adaptation of our algorithm solves the random glued-trees problem in polynomial time. We discuss practical limitations as well as potential improvements for quantifying finite-size, end-to-end complexities for application to relevant instances.
By decomposing quantum dynamics across the Lie orbits of a list of observables, we find polynomial bounded classical simulations for the dynamics of the quantum system given a polynomial sized dynamic Lie algebra (DLA) for the generators of the quantum system. To do so, we describe how to construct the Dynamic Observable Subspace (DOS) that captures all the relevant dynamics for calculating expectation values for a specific observable for Pauli strings, diffusor mixers, and general local generators. Efficient sparse matrix representation, decoupling nonlinearity from such representation and basis construction with permissible pruning allows us to simulate the closed dynamics of such systems with hundreds of qubits. Moreover, we find that while restricted DOS circuits may not express the space of an associated Hamiltonian, they can dramatically outperform a fully expressive circuit due to the absence of the Barren Plateau. While classically simulatable, such circuits can still exhibit a form of quantum advantage through inference, act as warm starting for more expressive circuits, and find high quality trial states for Quantum Amplitude Amplification or Quantum Phase Estimation. In the simulation of quantum dynamics, we find that our restricted circuit can be simulated in polynomial time while producing high quality guiding state for downstream tasks like Quantum Phase Estimation with significantly lower energy than circuits with full expressivity.
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. The functional form of these response functions can be mapped to a corresponding eigenproblem of a Hermitian matrix 𝐻, thus suggesting the use of quantum phase estimation. Our proposed quantum algorithm operates in the standard 𝑠-sparse, oracle-based query access model. For a network of 𝑁 oscillators with maximum norm ∥𝐻∥max, and when the eigenvalue tolerance ɛ is much smaller than the minimum eigenvalue gap, we use 𝒪(log(𝑁𝑠∥𝐻∥max/ɛ) algorithmic qubits and obtain a rigorous worst-case query complexity upper bound 𝒪(𝑠∥𝐻∥max/(𝛿2ɛ)) up to logarithmic factors, where 𝛿 denotes the desired precision on the coefficients appearing in the response functions. Crucially, our proposal does not suffer from the infamous state preparation bottleneck and can as such potentially achieve large quantum speedups compared to relevant classical methods. As a proof-of-principle of exponential quantum speedup, we show that a simple adaptation of our algorithm solves the random glued-trees problem in polynomial time. We discuss practical limitations as well as potential improvements for quantifying finite-size, end-to-end complexities for application to relevant instances.
Response theory has a successful history of connecting experimental observations with theoretical predictions. Of particular interest is the optical response of matter, from which spectroscopy experiments can be modelled. However, the calculation of response properties for quantum systems is often prohibitively expensive, especially for nonlinear spectroscopy, as it requires access to either the time evolution of the system or to excited states. In this work, we introduce a generalized quantum phase estimation framework designed for multi-variate phase estimation. This allows the treatment of general correlation functions enabling the recovery of response properties of arbitrary orders. The generalized quantum phase estimation circuit has an intuitive construction that is linked with a physical process of interest, and can directly sample frequencies from the distribution that would be obtained experimentally. In addition, we provide a single-ancilla modification of the new framework for early fault-tolerant quantum computers. Overall, our framework enables the efficient simulation of spectroscopy experiments beyond the linear regime, such as Raman spectroscopy, having that the circuit cost grows linearly with respect to the order of the target nonlinear response. This opens up an exciting new field of applications for quantum computers with potential technological impact.
Quantum generative modeling (QGM) relies on preparing quantum states and generating samples from these states as hidden---or known---probability distributions. As distributions from some classes of quantum states (circuits) are inherently hard to sample classically, QGM represents an excellent test bed for quantum supremacy experiments. Furthermore, generative tasks are increasingly relevant for industrial machine learning applications, and thus QGM is a strong candidate for demonstrating a practical quantum advantage. However, this requires that quantum circuits are trained to represent industrially relevant distributions, and the corresponding training stage has an extensive training cost for current quantum hardware in practice. In this work, we propose protocols for classical training of QGMs based on circuits of the specific type that admit an efficient gradient computation, while remaining hard to sample. In particular, we consider instantaneous quantum polynomial (IQP) circuits and their extensions. Showing their classical simulability in terms of the time complexity, sparsity, and anticoncentration properties, we develop a classically tractable way of simulating their output probability distributions, allowing classical training to a target probability distribution. The corresponding quantum sampling from IQPs can be performed efficiently, unlike when using classical sampling. We numerically demonstrate the end-to-end training of IQP circuits using probability distributions for up to 30 qubits on a regular desktop computer. When applied to industrially relevant distributions this combination of classical training with quantum sampling represents an avenue for reaching advantage in the noisy intermediate-scale quantum (NISQ) era.