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

Science China Physics Mechanics and Astronomy

Quantum second-order optimization algorithm for general polynomials

Pan Gao, Keren Li, Shijie Wei, Gui‐Lu Long

Published Sep 2, 2021• 25 citations
Publisher
DOI
10.1007/s11433-021-1725-9

Related papers

Exponential speedup of quantum newton optimization algorithm for general polynomials

Heng Fan

Science China Physics Mechanics and Astronomy•Aug 27, 2021•3 citations

Robustness of Quantum Algorithms for Nonconvex Optimization

Weiyuan Gong, Zhang, Chenyi, Tongyang Li

Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises. In this paper, we systematically study quantum algorithms for finding an $ε$-approximate second-order stationary point ($ε$-SOSP) of a $d$-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of $O(ε^{10}/d^5)$, accelerated perturbed gradient descent with quantum gradient estimation takes $O(\log d/ε^{1.75})$ quantum queries to find an $ε$-SOSP. We then prove that perturbed gradient descent is robust to the noise of $O(ε^6/d^4)$ and $O(ε/d^{0.5+ζ})$ for $ζ>0$ on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. We then propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to $O(ε^{1.5}/d)$ and $O(ε/\sqrt{d})$ noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes $O(d^{2.5}/ε^{3.5})$ and $O(d^2/ε^3)$ queries to the two oracles, giving a polynomial speedup over the classical counterparts. Moreover, we characterize the domains where quantum algorithms can find an $ε$-SOSP with poly-logarithmic, polynomial, or exponential number of queries in $d$, or the problem is information-theoretically unsolvable even by an infinite number of queries. In addition, we prove an $Ω(ε^{-12/7})$ lower bound in $ε$ for any randomized classical and quantum algorithm to find an $ε$-SOSP using either noisy zeroth- or first-order oracles.

arXiv:2212.02548•Dec 5, 2022•8 citations

What Can Be Computed with Indefinite Causal Structure?

Omri Shmueli

Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit. We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in $\textbf{NP}$. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond $\textbf{BQP}$ within the process matrix formalism, even while preserving unitarity.

quant-pharXiv:2610.40573•Oct 30, 2026•0 citations

Quantum Algorithms for Optimization

Ansh Bansal

IOSR Journal of Computer Engineering•Oct 1, 2025•0 citations

Optimal Quantum Algorithms for Ordered Search

Joseph Carolan, Andrew M. Childs

Ordered search is the problem of locating a target element in a sorted list of size $n$ using comparison queries. Classically, binary search requires $\lceil \log_2 n\rceil$ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal $\frac{1}π\ln n+o(\log n)$ queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.

quant-pharXiv:2609.34293•Sep 29, 2026•0 citations

Quantum algorithms for the polynomial eigenvalue problems.

Changpeng Shao, Jin-Peng Liu

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $\Omega(\sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

•Oct 28, 2020•0 citations
Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises. In this paper, we systematically study quantum algorithms for finding an εεε-approximate second-order stationary point (εεε-SOSP) of a ddd-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of O(ε10/d5)O(ε^{10}/d^5)O(ε10/d5), accelerated perturbed gradient descent with quantum gradient estimation takes O(log⁡d/ε1.75)O(\log d/ε^{1.75})O(logd/ε1.75) quantum queries to find an εεε-SOSP. We then prove that perturbed gradient descent is robust to the noise of O(ε6/d4)O(ε^6/d^4)O(ε6/d4) and O(ε/d0.5+ζ)O(ε/d^{0.5+ζ})O(ε/d0.5+ζ) for ζ>0ζ>0ζ>0 on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. We then propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to O(ε1.5/d)O(ε^{1.5}/d)O(ε1.5/d) and O(ε/d)O(ε/\sqrt{d})O(ε/d​) noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes O(d2.5/ε3.5)O(d^{2.5}/ε^{3.5})O(d2.5/ε3.5) and O(d2/ε3)O(d^2/ε^3)O(d2/ε3) queries to the two oracles, giving a polynomial speedup over the classical counterparts. Moreover, we characterize the domains where quantum algorithms can find an εεε-SOSP with poly-logarithmic, polynomial, or exponential number of queries in ddd, or the problem is information-theoretically unsolvable even by an infinite number of queries. In addition, we prove an Ω(ε−12/7)Ω(ε^{-12/7})Ω(ε−12/7) lower bound in εεε for any randomized classical and quantum algorithm to find an εεε-SOSP using either noisy zeroth- or first-order oracles.
Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit. We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in NP\textbf{NP}NP. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond BQP\textbf{BQP}BQP within the process matrix formalism, even while preserving unitarity.
Ordered search is the problem of locating a target element in a sorted list of size nnn using comparison queries. Classically, binary search requires ⌈log⁡2n⌉\lceil \log_2 n\rceil⌈log2​n⌉ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal 1πln⁡n+o(log⁡n)\frac{1}π\ln n+o(\log n)π1​lnn+o(logn) queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.
Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with A,BA,BA,B symmetric, and BBB positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when BBB is invertible, B−1AB^{-1}AB−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when BBB is singular, any quantum algorithm uses at least Ω(n)\Omega(\sqrt{n})Ω(n​) queries to compute the eigenvalues, where nnn is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.