An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime

• URL: http://arxiv.org/abs/2012.02338v1
• Date: Fri, 4 Dec 2020 00:01:15 GMT
• Title: An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime
• Authors: Pedro Rivero, Ian C. Clo\"et, Zack Sullivan
• Abstract summary: We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm. We analyze some of its use cases based on time complexity in the low qubit number regime. We demonstrate the efficacy of our algorithm for a benchmark problem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The VQE algorithm has turned out to be quite expensive to run given the way we currently access quantum processors (i.e. over the cloud). In order to alleviate this issue, we introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm, and analyze some of its use cases based on time complexity in the low qubit number regime. In exchange for some extra classical resources, this novel strategy is proved to be optimal in terms of the number of samples it requires from the quantum processor. We develop a simple analytical model to evaluate when this algorithm is more efficient than VQE, and, from the same theoretical considerations, establish a threshold above which quantum advantage can occur. Finally, we demonstrate the efficacy of our algorithm for a benchmark problem.

Related papers

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Bayesian Optimization Priors for Efficient Variational Quantum Algorithms [0.0]
  Quantum computers currently rely on a quantum-classical approach known as Variational Quantum Algorithms (VQAs) to solve problems. We propose a hybrid framework for basic computational optimization that reduces the number of shots per time is charged. Using both proposed features, we show that using both proposed features statistically outperforms an implementation within VQAs for simulations.
  arXiv  Detail & Related papers  (2024-06-20T18:00:12Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
  We present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
  arXiv  Detail & Related papers  (2021-12-21T12:41:31Z)
• 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)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Towards quantum advantage via topological data analysis [0.0]
  We study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi. We provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis.
  arXiv  Detail & Related papers  (2020-05-06T06:31:24Z)
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization [0.0]
  We study the problem of detecting problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm. We achieve cross-validated accuracy well over 96%, which would yield a substantial practical advantage.
  arXiv  Detail & Related papers  (2020-01-22T20:42:02Z)

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.