Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate

• URL: http://arxiv.org/abs/2211.12519v2
• Date: Fri, 16 Jun 2023 07:47:31 GMT
• Title: Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
• Authors: Lennart Bittel, Sevag Gharibian, Martin Kliesch
• Abstract summary: Variational Quantum Algorithms (VQAs) have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the emphdepth' of the variational ansatz'' used. We show that approximating the optimal depth for a given VQA ansatz is intractable.
• Score: 0.6445605125467572
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the \emph{depth} of the variational ``ansatz'' used -- the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant $\epsilon>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor $N^{1-\epsilon}$, for $N$ denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even ``simpler'' QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.

Related papers

• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• Warm-Starting the VQE with Approximate Complex Amplitude Encoding [0.26217304977339473]
  The Variational Quantum Eigensolver (VQE) is a quantum algorithm to determine the ground state of quantum-mechanical systems. We propose a warm-starting technique, that utilizes an approximation to generate beneficial initial parameter values for the VQE. Such warm-starts open the path to fruitful combinations of classical approximation algorithms and quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-27T10:15:25Z)
• 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)
• QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
  We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
  arXiv  Detail & Related papers  (2023-04-14T08:03:20Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• A prescreening method for variational quantum state eigensolver [0.0]
  We propose a method to derive all of the states with high accuracy by using the Variational Quantum State Eigensolver (VQSE) and Subspace-Search VQE (SSVQE) methods. We show that by using the VQSE and the SSVQE prescreening methods, we can derive all of the hydrogen molecules states correctly.
  arXiv  Detail & Related papers  (2021-11-03T18:13:33Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Efficient measure for the expressivity of variational quantum algorithms [72.59790225766777]
  We exploit an advanced tool in statistical learning theory, i.e., covering number, to study the expressivity of variational quantum algorithms. We first exhibit how the expressivity of VQAs with an arbitrary ansatze is upper bounded by the number of quantum gates and the measurement observable. We then explore the expressivity of VQAs on near-term quantum chips, where the system noise is considered.
  arXiv  Detail & Related papers  (2021-04-20T13:51:08Z)
• Variational Quantum Algorithm for Estimating the Quantum Fisher Information [0.0]
  We present a variational quantum algorithm called Variational Quantum Fisher Information Estimation (VQFIE) By estimating lower and upper bounds on the QFI, based on bounding the fidelity, VQFIE outputs a range in which the actual QFI lies. This result can then be used to variationally prepare the state that maximizes the QFI, for the application of quantum sensing.
  arXiv  Detail & Related papers  (2020-10-20T17:44:55Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)
• MoG-VQE: Multiobjective genetic variational quantum eigensolver [0.0]
  Variational quantum eigensolver (VQE) emerged as a first practical algorithm for near-term quantum computers. Here, we propose the approach which can combine both low depth and improved precision. We observe nearly ten-fold reduction in the two-qubit gate counts as compared to the standard hardware-efficient ansatz.
  arXiv  Detail & Related papers  (2020-07-08T20:44:50Z)

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.