Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

• URL: http://arxiv.org/abs/2307.09593v2
• Date: Fri, 11 Oct 2024 20:31:24 GMT
• Title: Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Authors: Dylan Lewis, Stephan Eidenbenz, Balasubramanya Nadiga, Yiğit Subaşı,
• Abstract summary: We investigate the limitations of quantum computers for solving nonlinear dynamical systems. We provide a significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector.
• Score: 0.2624902795082451
• License:
• Abstract: We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm [Liu et al., PNAS 118, 2021] answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.

Related papers

• 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)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• 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)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
  arXiv  Detail & Related papers  (2023-05-23T16:17:57Z)
• Efficient Quantum Algorithms for Quantum Optimal Control [2.9370710299422607]
  We present efficient quantum algorithms for solving the quantum optimal control problem. Our algorithms are based on a time-dependent Hamiltonian simulation method and a fast gradient-estimation algorithm. Our quantum algorithms require fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2023-04-05T17:33:57Z)
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks [0.0]
  We simulate the execution of quantum algorithms with limited entanglement. We find that the algorithms can be executed with high fidelity even if the entanglement is somewhat reduced. Our results are promising for the execution of these algorithms on future quantum computers.
  arXiv  Detail & Related papers  (2023-04-04T12:42:18Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware. We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
  arXiv  Detail & Related papers  (2022-06-13T16:21:04Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)

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.