A Dequantized Algorithm for the Guided Local Hamiltonian Problem

• URL: http://arxiv.org/abs/2411.16163v2
• Date: Tue, 26 Nov 2024 02:33:20 GMT
• Title: A Dequantized Algorithm for the Guided Local Hamiltonian Problem
• Authors: Yukun Zhang, Yusen Wu, Xiao Yuan,
• Abstract summary: The guided local Hamiltonian (GLH) problem can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. We introduce a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm.
• Score: 2.891413712995642
• License:
• Abstract: The local Hamiltonian (LH) problem, the quantum analog of the classical constraint satisfaction problem, is a cornerstone of quantum computation and complexity theory. It is known to be QMA-complete, indicating that it is challenging even for quantum computers. Interestingly, the guided local Hamiltonian (GLH) problem -- an LH problem with a guiding state that has a non-trivial overlap with the ground state -- can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. Remarkably, the quantum algorithm for solving the GLH problem can be `dequantized' (i.e., made classically simulatable) under certain conditions, such as when only constant accuracy is required and when the Hamiltonian satisfies an unrealistic constant operator norm constraint. In this work, we relieve these restrictions by introducing a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm. We demonstrate that it achieves either limited or arbitrary constant accuracy, depending on whether the guiding state's overlap is general or exceeds a certain threshold. Crucially, our approach eliminates the constant operator norm constraint on the Hamiltonian, opening its applicability to realistic problems. Our results advance the classical solution of the GLH problem in practical settings and provide new insights into the boundary between classical and quantum computational power.

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)
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics [42.29248343585333]
  We benchmark quantum hardware and error mitigation techniques on up to 133 qubits. We show reliable control up to a two-qubit gate depth of 28, featuring a maximum of 1396 two-qubit gates. Results are transferable to applications such as Hamiltonian simulation, variational algorithms, optimization, or quantum machine learning.
  arXiv  Detail & Related papers  (2024-04-11T18:00:05Z)
• State-Averaged Orbital-Optimized VQE: A quantum algorithm for the democratic description of ground and excited electronic states [0.0]
  The SA-OO-VQE package aims to answer both problems with its hybrid quantum-classical conception based on a typical Variational Quantum Eigensolver approach. The SA-OO-VQE has the ability to treat degenerate (or quasi-degenerate) states on the same footing, thus avoiding known numerical optimization problems around avoided crossings or conical intersections.
  arXiv  Detail & Related papers  (2024-01-22T12:16:37Z)
• 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 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)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Minimum-Time Quantum Control and the Quantum Brachistochrone Equation [3.0616044531734192]
  We present the general solution to the full quantum brachistochrone equation. We prove that the speed of evolution under constraints is reduced with respect to the unrestricted case. We find that solving the quantum brachistochrone equation is closely connected to solving the dynamics of the Lagrange multipliers.
  arXiv  Detail & Related papers  (2022-04-27T09:26:59Z)
• Schr\"odinger-Heisenberg Variational Quantum Algorithms [1.9887498823918806]
  Recent breakthroughs have opened the possibility to intermediate-scale quantum computing with tens to hundreds of qubits. The extremely high accuracy needed to surpass classical computers poses a critical demand to the circuit depth. Here, we propose a paradigm of Schr"odinger-Heisenberg variational quantum algorithms to resolve this problem.
  arXiv  Detail & Related papers  (2021-12-15T04:53:01Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Iterative Quantum Assisted Eigensolver [0.0]
  We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian. Our algorithm builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers.
  arXiv  Detail & Related papers  (2020-10-12T12:25:16Z)
• Limitations of optimization algorithms on noisy quantum devices [0.0]
  We present a transparent way of comparing classical algorithms to quantum ones running on near-term quantum devices. Our approach is based on the combination of entropic inequalities that determine how fast the quantum state converges to the fixed point of the noise model.
  arXiv  Detail & Related papers  (2020-09-11T17:07:26Z)

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.