Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2211.12519 · Leibniz international proceedings in informatics

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

Lennart Bittel, Sevag Gharibian, Martin Kliesch

Published Nov 22, 2022• 14 citations
arXivHTMLPDF

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 $ε>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor $N^{1-ε}$, 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.

DOI
10.4230/lipics.ccc.2023.34

Related papers

Discretized Quantum Exhaustive Search for Variational Quantum Algorithms

Ittay Alfassi, Dekel Meirom, Tal Mor

Quantum computers promise a great computational advantage over classical computers, yet currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. Variational Quantum Algorithms (VQAs) have emerged as a leading strategy to address these limitations by optimizing cost functions based on measurement results of shallow-depth circuits. However, the optimization process usually suffers from severe trainability issues as a result of the exponentially large search space, mainly local minima and barren plateaus. Here we propose a novel method that can improve variational quantum algorithms -- ``discretized quantum exhaustive search''. On classical computers, exhaustive search, also named brute force, solves small-size NP complete and NP hard problems. Exhaustive search and efficient partial exhaustive search help designing heuristics and exact algorithms for solving larger-size problems by finding easy subcases or good approximations. We adopt this method to the quantum domain, by relying on mutually unbiased bases for the $2^n$-dimensional Hilbert space. We define a discretized quantum exhaustive search that works well for small size problems. We provide an example of an efficient partial discretized quantum exhaustive search for larger-size problems, in order to extend classical tools to the quantum computing domain, for near future and far future goals. Our method enables obtaining intuition on NP-complete and NP-hard problems as well as on Quantum Merlin Arthur (QMA)-complete and QMA-hard problems. We demonstrate our ideas in many simple cases, providing the energy landscape for various problems and presenting two types of energy curves via VQAs.

arXiv:2407.17659•Jul 24, 2024•4 citations

Classically Optimal Variational Quantum Algorithms

Jonathan Wurtz, Peter J. Love

Hybrid quantum-classical algorithms, such as variational quantum algorithms (VQA), are suitable for implementation on NISQ computers. In this Article we expand an implicit step of VQAs: the classical pre-computation subroutine which can non-trivially use classical algorithms to simplify, transform, or specify problem instance-specific variational quantum circuits. In VQA there is a trade-off between quality of solution and difficulty of circuit construction and optimization. In one extreme, we find VQA for MAXCUT which are exact, but circuit design or variational optimization is NP-HARD. At the other extreme are low depth VQA, such as QAOA, with tractable circuit construction and optimization but poor approximation ratios. Combining these two we define the Spanning Tree QAOA (ST-QAOA) to solve MAXCUT, which uses an ansatz whose structure is derived from an approximate classical solution and achieves the same performance guarantee as the classical algorithm and hence can outperform QAOA at low depth. In general, we propose integrating these classical pre-computation subroutines into VQA to improve heuristic or guaranteed performance.

arXiv:2103.17065•IEEE Transactions on Quantum Engineering•Jan 1, 2021•49 citations

Training Variational Quantum Algorithms Is NP-Hard, Even Locally

Dax Enshan Koh, Triscia Mundo, Iosif Sakos +1 more

Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be $\mathsf{NP}$-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly $\mathsf{NP}$-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within $\ell_p$-distance strictly less than $π/2$ of some local minimizer, for every $p\geq 1$. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly $\mathsf{NP}$-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.

quant-pharXiv:2610.05128•Oct 6, 2026•0 citations

Training Variational Quantum Algorithms Is NP-Hard

Lennart Bittel, Martin Kliesch

Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.

arXiv:2101.07267•Physical Review Letters•Sep 17, 2021•503 citations

Variational Quantum Algorithms for Combinatorial Optimization

Daniel F. Pérez-Ramírez

The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.

arXiv:2407.06421•Jul 8, 2024•20 citations

Quantum Approximate Optimization Algorithm (QAOA) for Solving NP-Hard Problems

Srikanth Kilaru, Thota Sravya Vardhani, Attluri Udaya Lakshmi +2 more

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.

IEEE Nexo-Tech International Conference on Advanced Technologies and Innovations (ICATI)•May 8, 2026•0 citations
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 $ε>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor $N^{1-ε}$, 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.
Quantum computers promise a great computational advantage over classical computers, yet currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. Variational Quantum Algorithms (VQAs) have emerged as a leading strategy to address these limitations by optimizing cost functions based on measurement results of shallow-depth circuits. However, the optimization process usually suffers from severe trainability issues as a result of the exponentially large search space, mainly local minima and barren plateaus. Here we propose a novel method that can improve variational quantum algorithms -- ``discretized quantum exhaustive search''. On classical computers, exhaustive search, also named brute force, solves small-size NP complete and NP hard problems. Exhaustive search and efficient partial exhaustive search help designing heuristics and exact algorithms for solving larger-size problems by finding easy subcases or good approximations. We adopt this method to the quantum domain, by relying on mutually unbiased bases for the 2n2^n2n-dimensional Hilbert space. We define a discretized quantum exhaustive search that works well for small size problems. We provide an example of an efficient partial discretized quantum exhaustive search for larger-size problems, in order to extend classical tools to the quantum computing domain, for near future and far future goals. Our method enables obtaining intuition on NP-complete and NP-hard problems as well as on Quantum Merlin Arthur (QMA)-complete and QMA-hard problems. We demonstrate our ideas in many simple cases, providing the energy landscape for various problems and presenting two types of energy curves via VQAs.
Hybrid quantum-classical algorithms, such as variational quantum algorithms (VQA), are suitable for implementation on NISQ computers. In this Article we expand an implicit step of VQAs: the classical pre-computation subroutine which can non-trivially use classical algorithms to simplify, transform, or specify problem instance-specific variational quantum circuits. In VQA there is a trade-off between quality of solution and difficulty of circuit construction and optimization. In one extreme, we find VQA for MAXCUT which are exact, but circuit design or variational optimization is NP-HARD. At the other extreme are low depth VQA, such as QAOA, with tractable circuit construction and optimization but poor approximation ratios. Combining these two we define the Spanning Tree QAOA (ST-QAOA) to solve MAXCUT, which uses an ansatz whose structure is derived from an approximate classical solution and achieves the same performance guarantee as the classical algorithm and hence can outperform QAOA at low depth. In general, we propose integrating these classical pre-computation subroutines into VQA to improve heuristic or guaranteed performance.
Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be NP\mathsf{NP}NP-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly NP\mathsf{NP}NP-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within ℓp\ell_pℓp​-distance strictly less than π/2π/2π/2 of some local minimizer, for every p≥1p\geq 1p≥1. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly NP\mathsf{NP}NP-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.
Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.