On the sampling complexity of open quantum systems

• URL: http://arxiv.org/abs/2209.10870v1
• Date: Thu, 22 Sep 2022 09:09:28 GMT
• Title: On the sampling complexity of open quantum systems
• Authors: Isobel A. Aloisio, Gregory A. L. White, Charles D. Hill, Kavan Modi
• Abstract summary: We show how the complexity of the underlying quantum process corresponds to the complexity of the associated family of master equations for the dynamics. Our results pave the way for studying open quantum systems from a complexity-theoretic perspective.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Open quantum systems are ubiquitous in the physical sciences, with widespread applications in the areas of chemistry, condensed matter physics, material science, optics, and many more. Not surprisingly, there is significant interest in their efficient simulation. However, direct classical simulation quickly becomes intractable with coupling to an environment whose effective dimension grows exponentially. This raises the question: can quantum computers help model these complex dynamics? A first step in answering this question requires understanding the computational complexity of this task. Here, we map the temporal complexity of a process to the spatial complexity of a many-body state using a computational model known as the process tensor framework. With this, we are able to explore the simulation complexity of an open quantum system as a dynamic sampling problem: a system coupled to an environment can be probed at successive points in time -- accessing multi-time correlations. The complexity of multi-time sampling, which is an important and interesting problem in its own right, contains the complexity of master equations and stochastic maps as a special case. Our results show how the complexity of the underlying quantum stochastic process corresponds to the complexity of the associated family of master equations for the dynamics. We present both analytical and numerical examples whose multi-time sampling is as complex as sampling from a many-body state that is classically hard. This also implies that the corresponding family of master equations are classically hard. Our results pave the way for studying open quantum systems from a complexity-theoretic perspective, highlighting the role quantum computers will play in our understanding of quantum dynamics.

Related papers

• Benchmarking quantum chaos from geometric complexity [0.23436632098950458]
  We consider a new method to study geometric complexity for interacting non-Gaussian quantum mechanical systems. Within some limitations, geometric complexity can indeed be a good indicator of quantum chaos.
  arXiv  Detail & Related papers  (2024-10-24T14:04:58Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups [9.538251541300028]
  We introduce a novel quantum walk that encodes the Laplacian, a key mathematical object whose spectral properties reflect the underlying simplicial complex. Our results achieve superpolynomial quantum speedup with quantum walks without relying on quantum oracles for large datasets.
  arXiv  Detail & Related papers  (2024-04-23T18:00:17Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Saturation and recurrence of quantum complexity in random local quantum dynamics [5.803309695504831]
  Quantum complexity is a measure of the minimal number of elementary operations required to prepare a given state or unitary channel. Brown and Susskind conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly-exponential times.
  arXiv  Detail & Related papers  (2022-05-19T17:42:31Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Quantum Markov Chain Monte Carlo with Digital Dissipative Dynamics on Quantum Computers [52.77024349608834]
  We develop a digital quantum algorithm that simulates interaction with an environment using a small number of ancilla qubits. We evaluate the algorithm by simulating thermal states of the transverse Ising model.
  arXiv  Detail & Related papers  (2021-03-04T18:21:00Z)
• Probing quantum information propagation with out-of-time-ordered correlators [41.12790913835594]
  Small-scale quantum information processors hold the promise to efficiently emulate many-body quantum systems. Here, we demonstrate the measurement of out-of-time-ordered correlators (OTOCs) A central requirement for our experiments is the ability to coherently reverse time evolution.
  arXiv  Detail & Related papers  (2021-02-23T15:29:08Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Quantum State Complexity in Computationally Tractable Quantum Circuits [0.0]
  We discuss a special class of numerically tractable quantum circuits, known as quantum automaton circuits. We show that automaton wave functions have high quantum state complexity. We present evidence of a linear growth of design complexity in local quantum circuits.
  arXiv  Detail & Related papers  (2020-09-11T16:25:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.