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:2503.04620 · Communications Physics

Interpolation-based coordinate descent method for parameterized quantum circuits

Zhijian Lai, Jiang Hu, Taehee Ko, Jiayuan Wu, Dong An

Published Jan 7, 2026• 1 citation
arXivHTMLPDF

Abstract

Parameterized quantum circuits (PQCs) are fundamental to many hybrid quantum-classical algorithms. However, existing structure-based optimizers for the training of PQCs, such as Rotosolve and sequential minimal optimization, rely on heuristic node selection or ignore statistical noise, which limits their robustness and accuracy. To address this issue, we propose an interpolation-based coordinate descent (ICD) method as a unified framework for all structure-based optimizers. ICD approximates the cost function through interpolation, recovers its trigonometric structure, and performs global one-dimensional updates on individual parameters. Unlike previous methods, ICD derives optimal interpolation nodes that minimize statistical errors from measurements. For the common case of r equidistant frequencies, we prove that equidistant nodes with spacing 2π/(2r + 1) jointly minimize the mean squared error of Fourier coefficient estimates, the condition number of the interpolation matrix, and the average variance of the approximated cost function. Numerical experiments confirm the superior robustness and efficiency of ICD over gradient-based methods. Parameterized quantum circuits are a common tool in variational quantum algorithms and quantum machine learning. The authors design an interpolation-based coordinate descent method that reconstructs the cost landscape from a few circuit runs and achieves more efficient training than standard gradient and coordinate descent methods in our numerical tests.

DOI
10.1038/s42005-025-02473-8

Related papers

Random coordinate descent: A simple alternative for optimizing parameterized quantum circuits

Zhiyan Ding, Taehee Ko, Jiahao Yao +2 more

Variational quantum algorithms rely on the optimization of parameterized quantum circuits in noisy settings. The commonly used back-propagation procedure in classical machine learning is not directly applicable in this setting due to the collapse of quantum states after measurements. Thus, gradient estimations constitute a significant overhead in a gradient-based optimization of such quantum circuits. This paper introduces a random coordinate descent algorithm as a practical and easy-to-implement alternative to the full gradient descent algorithm. This algorithm only requires one partial derivative at each iteration. Motivated by the behavior of measurement noise in the practical optimization of parameterized quantum circuits, this paper presents an optimization problem setting that is amenable to analysis. Under this setting, the random coordinate descent algorithm exhibits the same level of stochastic stability as the full gradient approach, making it as resilient to noise. The complexity of the random coordinate descent method is generally no worse than that of the gradient descent and can be much better for various quantum optimization problems with anisotropic Lipschitz constants. Theoretical analysis and extensive numerical experiments validate our findings. Published by the American Physical Society 2024

arXiv:2311.00088•Physical Review Research•Jul 8, 2024•9 citations

One Coordinate at a Time: Convergence Guarantees for Rotosolve in Variational Quantum Algorithms

Sayantan Pramanik, M Girish Chandra

In this paper, we resolve an open question in the field of optimization algorithms for training parametrized quantum circuits: Does the popular Rotosolve algorithm converge? Until now, interpolation-based coordinate descent methods such as Rotosolve have mostly been treated as heuristics, lacking any formal convergence guarantees. We rigorously analyze Rotosolve, and show that it converges to $\varepsilon$-stationary points if the optimization landscape is non-convex and smooth; and to $\varepsilon$-suboptimal points if the objective function additionally obeys the Polyak-Lojasiewicz (PL) condition. Further, we derive explicit worst-case rates of convergence in the finite quantum measurement regime. These rates are contrasted against those from a similar coordinate-based method: Randomized Coordinate Descent (RCD). Although in the worst case their rates are, prima facie, equivalent, we present arguments for a more nuanced comparison between the two. We highlight that Rotosolve is hyperparameter-free, and implicitly uses first and second derivatives in its updates. Finally, we supplement our theoretical findings with numerical experiments from Quantum Machine Learning; and compare the performance of Rotosolve against RCD, Stochastic Gradient Descent, Simultaneous Perturbation Stochastic Approximation, and Randomized Stochastic Gradient Free methods.

quant-pharXiv:2604.25613•Apr 29, 2026•0 citations

Enhancing Hybrid Methods in Parameterized Quantum Circuit Optimization

Joona V. Pankkonen, Matti Raasakka, Andrea Marchesin +1 more

Parameterized quantum circuits (PQCs) play an essential role in the application of variational quantum algorithms (VQAs) in noisy intermediate-scale quantum (NISQ) devices. The PQCs are a leading candidate to achieve a quantum advantage in NISQ devices and have already been applied in various domains such as quantum chemistry, quantum machine learning, combinatorial optimization, and many others. There is no single definitive way to optimize PQCs. The most commonly used methods are based on computing the gradient via the parameter-shift rule to use classical gradient descent (GD) optimizers like Adam, stochastic GD, and others. In addition, sequential single-qubit optimizers have been proposed, such as Rotosolve, Free-Axis Selection (Fraxis), Free-Quaternion Selection (FQS), and hybrid algorithms from the aforementioned optimizers. We further develop hybrid algorithms than those represented in the previous work by drawing inspiration from the early stopping method used in classical machine learning. The switch between the optimizers depends on the previous cost function values compared to the previous ones. We introduce two new hybrid algorithms that are more robust and scalable, and they outperform previous hybrid methods in terms of convergence towards the global minima across various cost functions. In addition, we find that they are feasible for NISQ devices with different noise profiles.

arXiv:2510.08142•Oct 9, 2025•0 citations

Global Optimization for Parametrized Quantum Circuits

Iosif Sakos, Antonios Varvitsiotis, Georgios Korpas +1 more

In the absence of error correction, noisy intermediate-scale quantum devices are operated by training parametrized quantum circuits (PQCs) so as to minimize a suitable loss function. Finding the optimal parameters of those circuits is a hard optimization problem, where global guarantees are known only for highly structured cases of limited practical relevance, and first-order methods can fail to find even local minima due to the presence of barren plateaus. In this work, we study the training of practical classes of PQCs, namely polynomial-depth circuits with a constant number of trainable parameters. This captures widely used PQC families, including fixed-depth QAOA, hardware-efficient ansätze, and Fixed Parameter Count QAOA. Our main technical result is a fully polynomial randomized approximation scheme (FPRAS), which, for every $ε>0$, returns an $ε$-approximate solution to the problem's global optimum with high probability, and has runtime and query complexity polynomial in $1/ε$ and the number of qubits. Unlike the standard hybrid quantum-classical training loop in variational algorithms, where the quantum device is queried repeatedly throughout the training, our approach separates the computation into two distinct stages: (1) an initial quantum data-acquisition phase, followed by (2) a classical global-optimization phase based on the trigonometric moment/sum-of-squares hierarchies. Under a standard flat-extension condition, which can be checked numerically, the method also supports the extraction of optimal circuit parameters. The existence of an FPRAS implies that the promise problem associated with the optimization of poly-depth constant-parameter PQC is in BQP. This imposes a limitation on the expressive power of the class, namely, it cannot encode combinatorial optimization problems whose objective values are separated by an inverse-polynomial gap.

quant-pharXiv:2603.21757•Mar 24, 2026•0 citations

Sequential minimal optimization for quantum-classical hybrid algorithms

Ken M. Nakanishi, Keisuke Fujii, Synge Todo

We propose a sequential minimal optimization method for quantum-classical hybrid algorithms, which converges faster, robust against statistical error, and hyperparameter-free.Specifically, the optimization problem of the parameterized quantum circuits is divided into solvable subproblems by considering only a subset of the parameters.In fact, if we choose a single parameter, the cost function becomes a simple sine curve with period 2π , and hence we can exactly minimize with respect to the chosen parameter.Furthermore, even in general cases, the cost function is given by a simple sum of trigonometric functions with certain periods and hence can be minimized by using a classical computer.By repeatedly performing this procedure, we can optimize the parameterized quantum circuits so that the cost function becomes as small as possible.We perform numerical simulations and compare the proposed method with existing gradient-free and gradient-based optimization algorithms.We find that the proposed method substantially outperforms the existing optimization algorithms and converges to a solution almost independent of the initial choice of the parameters.This accelerates almost all quantum-classical hybrid algorithms readily and would be a key tool for harnessing near-term quantum devices.

arXiv:1903.12166•Physical Review Research•Oct 29, 2020•215 citations

Distributed Coordinate Descent Algorithm for Variational Quantum Classification

Izuho Koyasu, Rudy Raymond, Hiroshi Imai

Quantum Machine Learning (QML) is one of promising applications for near-term quantum computing. Two popular methods in QML are kernel methods and variational methods. Variational methods, which consist of parametrized quantum circuits (PQCs) to encode data and define classifiers, work faster in theory (i.e., O(N) to learn from$N$training examples) than kernel methods, which use quantum circuits to compute O(N2) elements of kernel matrices. However, in practice when dealing with large N, it is necessary to speed up variational methods due to the slow quantum gates. In this work, we propose a parallelization of training variational quantum classifiers to utilize the availability of many quantum devices with dozens of qubits. In contrast to existing parallelization of variational methods with gradient-based algorithms, we develop a novel distributed coordinate descent algorithm to optimize parametrized gates of variational quantum circuits. There are several gradient-free methods to optimize PQCs that have been shown to converge faster. Here, by focusing on the so-called Free-axis selection (Fraxis) method, we show how the gradient-free methods can be parallelized, and demonstrate their efficacies by running the algorithm on both simulators and IBM Quantum devices. We confirm the proposed algorithm achieves high classification accuracy and gains almost-linear speedup with the degree of parallelization.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•8 citations
Parameterized quantum circuits (PQCs) are fundamental to many hybrid quantum-classical algorithms. However, existing structure-based optimizers for the training of PQCs, such as Rotosolve and sequential minimal optimization, rely on heuristic node selection or ignore statistical noise, which limits their robustness and accuracy. To address this issue, we propose an interpolation-based coordinate descent (ICD) method as a unified framework for all structure-based optimizers. ICD approximates the cost function through interpolation, recovers its trigonometric structure, and performs global one-dimensional updates on individual parameters. Unlike previous methods, ICD derives optimal interpolation nodes that minimize statistical errors from measurements. For the common case of r equidistant frequencies, we prove that equidistant nodes with spacing 2π/(2r + 1) jointly minimize the mean squared error of Fourier coefficient estimates, the condition number of the interpolation matrix, and the average variance of the approximated cost function. Numerical experiments confirm the superior robustness and efficiency of ICD over gradient-based methods. Parameterized quantum circuits are a common tool in variational quantum algorithms and quantum machine learning. The authors design an interpolation-based coordinate descent method that reconstructs the cost landscape from a few circuit runs and achieves more efficient training than standard gradient and coordinate descent methods in our numerical tests.
Variational quantum algorithms rely on the optimization of parameterized quantum circuits in noisy settings. The commonly used back-propagation procedure in classical machine learning is not directly applicable in this setting due to the collapse of quantum states after measurements. Thus, gradient estimations constitute a significant overhead in a gradient-based optimization of such quantum circuits. This paper introduces a random coordinate descent algorithm as a practical and easy-to-implement alternative to the full gradient descent algorithm. This algorithm only requires one partial derivative at each iteration. Motivated by the behavior of measurement noise in the practical optimization of parameterized quantum circuits, this paper presents an optimization problem setting that is amenable to analysis. Under this setting, the random coordinate descent algorithm exhibits the same level of stochastic stability as the full gradient approach, making it as resilient to noise. The complexity of the random coordinate descent method is generally no worse than that of the gradient descent and can be much better for various quantum optimization problems with anisotropic Lipschitz constants. Theoretical analysis and extensive numerical experiments validate our findings. Published by the American Physical Society 2024
In this paper, we resolve an open question in the field of optimization algorithms for training parametrized quantum circuits: Does the popular Rotosolve algorithm converge? Until now, interpolation-based coordinate descent methods such as Rotosolve have mostly been treated as heuristics, lacking any formal convergence guarantees. We rigorously analyze Rotosolve, and show that it converges to ε\varepsilonε-stationary points if the optimization landscape is non-convex and smooth; and to ε\varepsilonε-suboptimal points if the objective function additionally obeys the Polyak-Lojasiewicz (PL) condition. Further, we derive explicit worst-case rates of convergence in the finite quantum measurement regime. These rates are contrasted against those from a similar coordinate-based method: Randomized Coordinate Descent (RCD). Although in the worst case their rates are, prima facie, equivalent, we present arguments for a more nuanced comparison between the two. We highlight that Rotosolve is hyperparameter-free, and implicitly uses first and second derivatives in its updates. Finally, we supplement our theoretical findings with numerical experiments from Quantum Machine Learning; and compare the performance of Rotosolve against RCD, Stochastic Gradient Descent, Simultaneous Perturbation Stochastic Approximation, and Randomized Stochastic Gradient Free methods.
Parameterized quantum circuits (PQCs) play an essential role in the application of variational quantum algorithms (VQAs) in noisy intermediate-scale quantum (NISQ) devices. The PQCs are a leading candidate to achieve a quantum advantage in NISQ devices and have already been applied in various domains such as quantum chemistry, quantum machine learning, combinatorial optimization, and many others. There is no single definitive way to optimize PQCs. The most commonly used methods are based on computing the gradient via the parameter-shift rule to use classical gradient descent (GD) optimizers like Adam, stochastic GD, and others. In addition, sequential single-qubit optimizers have been proposed, such as Rotosolve, Free-Axis Selection (Fraxis), Free-Quaternion Selection (FQS), and hybrid algorithms from the aforementioned optimizers. We further develop hybrid algorithms than those represented in the previous work by drawing inspiration from the early stopping method used in classical machine learning. The switch between the optimizers depends on the previous cost function values compared to the previous ones. We introduce two new hybrid algorithms that are more robust and scalable, and they outperform previous hybrid methods in terms of convergence towards the global minima across various cost functions. In addition, we find that they are feasible for NISQ devices with different noise profiles.
In the absence of error correction, noisy intermediate-scale quantum devices are operated by training parametrized quantum circuits (PQCs) so as to minimize a suitable loss function. Finding the optimal parameters of those circuits is a hard optimization problem, where global guarantees are known only for highly structured cases of limited practical relevance, and first-order methods can fail to find even local minima due to the presence of barren plateaus. In this work, we study the training of practical classes of PQCs, namely polynomial-depth circuits with a constant number of trainable parameters. This captures widely used PQC families, including fixed-depth QAOA, hardware-efficient ansätze, and Fixed Parameter Count QAOA. Our main technical result is a fully polynomial randomized approximation scheme (FPRAS), which, for every ε>0ε>0ε>0, returns an εεε-approximate solution to the problem's global optimum with high probability, and has runtime and query complexity polynomial in 1/ε1/ε1/ε and the number of qubits. Unlike the standard hybrid quantum-classical training loop in variational algorithms, where the quantum device is queried repeatedly throughout the training, our approach separates the computation into two distinct stages: (1) an initial quantum data-acquisition phase, followed by (2) a classical global-optimization phase based on the trigonometric moment/sum-of-squares hierarchies. Under a standard flat-extension condition, which can be checked numerically, the method also supports the extraction of optimal circuit parameters. The existence of an FPRAS implies that the promise problem associated with the optimization of poly-depth constant-parameter PQC is in BQP. This imposes a limitation on the expressive power of the class, namely, it cannot encode combinatorial optimization problems whose objective values are separated by an inverse-polynomial gap.
We propose a sequential minimal optimization method for quantum-classical hybrid algorithms, which converges faster, robust against statistical error, and hyperparameter-free.Specifically, the optimization problem of the parameterized quantum circuits is divided into solvable subproblems by considering only a subset of the parameters.In fact, if we choose a single parameter, the cost function becomes a simple sine curve with period 2π , and hence we can exactly minimize with respect to the chosen parameter.Furthermore, even in general cases, the cost function is given by a simple sum of trigonometric functions with certain periods and hence can be minimized by using a classical computer.By repeatedly performing this procedure, we can optimize the parameterized quantum circuits so that the cost function becomes as small as possible.We perform numerical simulations and compare the proposed method with existing gradient-free and gradient-based optimization algorithms.We find that the proposed method substantially outperforms the existing optimization algorithms and converges to a solution almost independent of the initial choice of the parameters.This accelerates almost all quantum-classical hybrid algorithms readily and would be a key tool for harnessing near-term quantum devices.
Quantum Machine Learning (QML) is one of promising applications for near-term quantum computing. Two popular methods in QML are kernel methods and variational methods. Variational methods, which consist of parametrized quantum circuits (PQCs) to encode data and define classifiers, work faster in theory (i.e., O(N) to learn fromNNNtraining examples) than kernel methods, which use quantum circuits to compute O(N2) elements of kernel matrices. However, in practice when dealing with large N, it is necessary to speed up variational methods due to the slow quantum gates. In this work, we propose a parallelization of training variational quantum classifiers to utilize the availability of many quantum devices with dozens of qubits. In contrast to existing parallelization of variational methods with gradient-based algorithms, we develop a novel distributed coordinate descent algorithm to optimize parametrized gates of variational quantum circuits. There are several gradient-free methods to optimize PQCs that have been shown to converge faster. Here, by focusing on the so-called Free-axis selection (Fraxis) method, we show how the gradient-free methods can be parallelized, and demonstrate their efficacies by running the algorithm on both simulators and IBM Quantum devices. We confirm the proposed algorithm achieves high classification accuracy and gains almost-linear speedup with the degree of parallelization.