This paper introduces a hybrid quantum framework for training Variational Quantum Algorithms (VQAs) aimed at addressing the fundamental problem of entanglement detection using adiabatic quantum computing. This problem is of foundational significance in quantum information science and has been approached through both classical and quantum methodologies. We propose an adiabatic-inspired optimization strategy for training VQAs, which combines a discretization of the parameter space with a hierarchical segmentation scheme. The optimization problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model to leverage the capabilities of quantum annealing. Preliminary results are compared against classical neural networks and conventional VQA training techniques. The findings aim to stimulate further investigation and discussion within the scientific community regarding the efficacy and applicability of the proposed approach.This paper introduces a hybrid quantum framework for training Variational Quantum Algorithms (VQAs) aimed at addressing the fundamental problem of entanglement detection using adiabatic quantum computing. This problem is of foundational significance in quantum information science and has been approached through both classical and quantum methodologies. We propose an adiabatic-inspired optimization strategy for training VQAs, which combines a discretization of the parameter space with a hierarchical segmentation scheme. The optimization problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model to leverage the capabilities of quantum annealing. Preliminary results are compared against classical neural networks and conventional VQA training techniques. The findings aim to stimulate further investigation and discussion within the scientific community regarding the efficacy and applicability of the proposed approach.

quant-pharXiv:2610.39577IEEE International Conference on Quantum Artificial Intelligence (QAI)Oct 30, 20261 citation

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.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.05128Oct 6, 20260 citations

Learning adiabatic quantum algorithms over optimization problems

Davide Pastorello, Enrico Blanzieri, Valter Cavecchia

Quantum Machine IntelligenceJan 3, 20219 citations

Variational quantum algorithms

Marco Cerezo, Andrew Arrasmith, Ryan Babbush +8 more

arXiv:2012.09265Nature Reviews PhysicsAug 12, 20213,385 citations

Variational quantum algorithms: fundamental concepts, applications and challenges

Han Qi, Sihui Xiao, Zhuo Liu +2 more

Quantum Information ProcessingJun 3, 202437 citations

Continuous Variational Quantum Algorithms for Time Series

Muhao Guo, Yang Weng, Ye Lili +1 more

Variational quantum algorithms (VQAs) are the leading algorithm for achieving quantum advantage using near-term quantum computers. VQAs use parameterized quantum circuits for inference, and the variational parameters in quantum circuits can be trained using a classical optimizer. The parameters are trained to guide how the quantum bits evolve and make the final measurements closely match the ground truth. However, this way of learning from raw data makes it difficult to capture the underlying dynamic information in the data, especially for time series data. To address this limitation, we proposed continuous variational quantum algorithms (CVQAs) for time series in this paper. CVQAs use quantum variational circuits to parameterize the dynamics of time series, thus they can learn the dynamic information behind the data. After the dynamics are trained, the prediction results will be obtained by a differential equation solver working on the dynamics. Since we aim to model the dynamics of data instead of the data itself, the quantum circuit in our approach will need fewer qubits and variational gates. To evaluate our proposed approach, we compare our model with baseline models on several weather time series. Experimental results prove that our approach has better or equivalent results but with fewer qubits and variational gates compared to baseline models.Variational quantum algorithms (VQAs) are the leading algorithm for achieving quantum advantage using near-term quantum computers. VQAs use parameterized quantum circuits for inference, and the variational parameters in quantum circuits can be trained using a classical optimizer. The parameters are trained to guide how the quantum bits evolve and make the final measurements closely match the ground truth. However, this way of learning from raw data makes it difficult to capture the underlying dynamic information in the data, especially for time series data. To address this limitation, we proposed continuous variational quantum algorithms (CVQAs) for time series in this paper. CVQAs use quantum variational circuits to parameterize the dynamics of time series, thus they can learn the dynamic information behind the data. After the dynamics are trained, the prediction results will be obtained by a differential equation solver working on the dynamics. Since we aim to model the dynamics of data instead of the data itself, the quantum circuit in our approach will need fewer qubits and variational gates. To evaluate our proposed approach, we compare our model with baseline models on several weather time series. Experimental results prove that our approach has better or equivalent results but with fewer qubits and variational gates compared to baseline models.

International Joint Conference on Neural Networks (IJCNN)Jun 18, 20237 citations

\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.