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:1810.04640

Energy Minimization in $CP^n$: Some Numerical and Analytical Results

Radel Ben Av, Assaf Goldberger, Giora Dula, Yossi Strassler

Published Oct 10, 2018• 2 citations
arXivHTMLPDF

Abstract

We study the problem of minimizing the energy function $M^p(m,n) := \min \sum_{1\le i0$ are integers and $p$ is even. This problem has implications on finding nice polyhedra in projective spaces, and on quantum random access codes. We conduct experimental search in the complex case which suggests nice patterns on the minimum values. In some cases($p=2$ and partially $n=2$) we supply analytical proofs and give full descriptions of the minimal configurations. We also show that as $m\to \infty$, nearly equidistributed configurations points nearly give the minimal values we expect from our patterns.

DOI
10.48550/arxiv.1810.04640

Related papers

Continuous-time quantum algorithms for unstructured problems

Itay Hen

We consider a family of unstructured optimization problems, for which we propose a method for constructing analogue, continuous-time (not necessarily adiabatic) quantum algorithms that are faster than their classical counterparts. In this family of problems, which we refer to as ‘scrambled input’ problems, one has to find a minimum-cost configuration of a given integer-valued n -bit black-box function whose input values have been scrambled in some unknown way. Special cases within this set of problems are Grover’s search problem of finding a marked item in an unstructured database, certain random energy models, and the functions of the Deutsch–Josza problem. We consider a couple of examples in detail. In the first, we provide an O (1) deterministic analogue quantum algorithm to solve the seminal problem of Deutsch and Josza, in which one has to determine whether an n -bit boolean function is constant (gives 0 on all inputs or 1 on all inputs) or balanced (returns 0 on half the input states and 1 on the other half). We also study one variant of the random energy model, and show that, as one might expect, its minimum energy configuration can be found quadratically faster with a quantum adiabatic algorithm than with classical algorithms.

arXiv:1302.7256•Journal of Physics A Mathematical and Theoretical•Jan 8, 2014•18 citations

Minimum energy configurations on a toric lattice as a quadratic assignment problem. Part II: symmetry reduction of semidefinite programming relaxations

Daniel Brosch, Etienne de Klerk

arXiv:2001.11348•Jan 30, 2020•0 citations

Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

Yexin Zhang, Zhang, Chenyi, Cong Fang +2 more

Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let $f_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $ψ\colon\mathbb{R}^d\to\mathbb{R}$ be a $μ$-strongly convex proximal function. The goal is to find an $ε$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tildeΘ\big(n+\sqrt{n\ell/μ}\big)$. We also prove a quantum lower bound $\tildeΩ(n+n^{3/4}(\ell/μ)^{1/4})$ when $d$ is large enough. Both our quantum upper and lower bounds can extend to the cases where $ψ$ is not necessarily strongly convex, or each $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $ε$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)$ queries.

arXiv:2406.03006•Jun 5, 2024•3 citations

Multidimensional derivative-free optimization. A case study on minimization of Hartree-Fock-Roothaan energy functionals

A. Bagci

This study presents an evaluation of derivative-free optimization algorithms for the direct minimization of Hartree-Fock-Roothaan energy functionals involving nonlinear orbital parameters and quantum numbers with noninteger order. The analysis focuses on atomic calculations employing noninteger Slater-type orbitals. Analytic derivatives of the energy functional are not readily available for these orbitals. Four methods are investigated under identical numerical conditions: Powell's conjugate-direction method, the Nelder-Mead simplex algorithm, coordinate-based pattern search, and a model-based algorithm utilizing radial basis functions for surrogate-model construction. Performance benchmarking is first performed using the Powell singular function, a well-established test case exhibiting challenging properties including Hessian singularity at the global minimum. The algorithms are then applied to Hartree-Fock-Roothaan self-consistent-field energy functionals, which define a highly non-convex optimization landscape due to the nonlinear coupling of orbital parameters. Illustrative examples are provided for closed$-$shell atomic configurations, specifically the He, Be isoelectronic series, with calculations performed for energy functionals involving up to eight nonlinear parameters. This work presents the first systematic investigation of derivative-free optimization methods for Hartree-Fock$-$Roothaan energy minimization with non-integer Slater orbitals.

quant-pharXiv:2512.24509•Jan 1, 2026

Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization

Cinar Ari, Robert Hildebrand

We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial $x^T Q x + c^T x + γ$ over the integer points of a bounded rational polyhedron $\{x : Ax \le b\}$. For $n$ variables and $m$ inequalities, the running time is $$2^{O(n \log(n+1))} (m+1)^{O(n)} β^{O(n)} (1+L)^{O(1)},$$ where $β$ is one plus the maximum binary encoding length of an entry of $A$ or $Q$, and $L$ is the full input encoding length. The polynomial degree in $L$ is absolute; in particular, the encoding of $b$, $c$, and $γ$ enters only this fixed-degree factor. Our algorithm refines the integral parallelepiped cover of Goemans and Rothvoss into cells with controlled displacement sets. On each cell, either an integer displacement of negative quadratic value rules out every point as a global minimizer, or the quadratic identity supplies a separation oracle for the convex hull of each integer objective sublevel set. The integer-query feasibility theorem of Hildebrand and Goess then finds the cell minimum. A refinement through scaled lattices solves the displacement search, and a localization argument separates the encoding dependence of the constraint matrix and quadratic part from that of the remaining data. Combining the bounded algorithm with the unboundedness test of Ari and Hildebrand extends the method to arbitrary rational polyhedra.

arXiv:2609.17889•Sep 15, 2026•1 citation

On Reducing Complexity of a Soft-Decision Decoding Algorithm for Cyclic Codes Based on Energy Minimization Principle (Special Section on Information Theory and Its Applications)

Akira Shiozaki, Kazutaka Aoki

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Oct 25, 1998•0 citations
Energy Minimization in CPnCP^nCPn: Some Numerical and Analytical Results
We study the problem of minimizing the energy function M^p(m,n) := \min \sum_{1\le i0 are integers and ppp is even. This problem has implications on finding nice polyhedra in projective spaces, and on quantum random access codes. We conduct experimental search in the complex case which suggests nice patterns on the minimum values. In some cases(p=2p=2p=2 and partially n=2n=2n=2) we supply analytical proofs and give full descriptions of the minimal configurations. We also show that as m→∞m\to \inftym→∞, nearly equidistributed configurations points nearly give the minimal values we expect from our patterns.
We consider a family of unstructured optimization problems, for which we propose a method for constructing analogue, continuous-time (not necessarily adiabatic) quantum algorithms that are faster than their classical counterparts. In this family of problems, which we refer to as ‘scrambled input’ problems, one has to find a minimum-cost configuration of a given integer-valued n -bit black-box function whose input values have been scrambled in some unknown way. Special cases within this set of problems are Grover’s search problem of finding a marked item in an unstructured database, certain random energy models, and the functions of the Deutsch–Josza problem. We consider a couple of examples in detail. In the first, we provide an O (1) deterministic analogue quantum algorithm to solve the seminal problem of Deutsch and Josza, in which one has to determine whether an n -bit boolean function is constant (gives 0 on all inputs or 1 on all inputs) or balanced (returns 0 on half the input states and 1 on the other half). We also study one variant of the random energy model, and show that, as one might expect, its minimum energy configuration can be found quadratically faster with a quantum adiabatic algorithm than with classical algorithms.
Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let f1,…,fn ⁣:Rd→Rf_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}f1​,…,fn​:Rd→R be ℓ\ellℓ-smooth convex functions and ψ ⁣:Rd→Rψ\colon\mathbb{R}^d\to\mathbb{R}ψ:Rd→R be a μμμ-strongly convex proximal function. The goal is to find an εεε-optimal point for F(x)=1n∑i=1nfi(x)+ψ(x)F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})F(x)=n1​∑i=1n​fi​(x)+ψ(x). We give a quantum algorithm with complexity O~(n+d+ℓ/μ(n1/3d1/3+n−2/3d5/6))\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)O~(n+d​+ℓ/μ​(n1/3d1/3+n−2/3d5/6)), improving the classical tight bound Θ~(n+nℓ/μ)\tildeΘ\big(n+\sqrt{n\ell/μ}\big)Θ~(n+nℓ/μ​). We also prove a quantum lower bound Ω~(n+n3/4(ℓ/μ)1/4)\tildeΩ(n+n^{3/4}(\ell/μ)^{1/4})Ω~(n+n3/4(ℓ/μ)1/4) when ddd is large enough. Both our quantum upper and lower bounds can extend to the cases where ψψψ is not necessarily strongly convex, or each fif_ifi​ is Lipschitz but not necessarily smooth. In addition, when FFF is nonconvex, our quantum algorithm can find an εεε-critial point using O~(n+ℓ(d1/3n1/3+d)/ε2)\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)O~(n+ℓ(d1/3n1/3+d​)/ε2) queries.
This study presents an evaluation of derivative-free optimization algorithms for the direct minimization of Hartree-Fock-Roothaan energy functionals involving nonlinear orbital parameters and quantum numbers with noninteger order. The analysis focuses on atomic calculations employing noninteger Slater-type orbitals. Analytic derivatives of the energy functional are not readily available for these orbitals. Four methods are investigated under identical numerical conditions: Powell's conjugate-direction method, the Nelder-Mead simplex algorithm, coordinate-based pattern search, and a model-based algorithm utilizing radial basis functions for surrogate-model construction. Performance benchmarking is first performed using the Powell singular function, a well-established test case exhibiting challenging properties including Hessian singularity at the global minimum. The algorithms are then applied to Hartree-Fock-Roothaan self-consistent-field energy functionals, which define a highly non-convex optimization landscape due to the nonlinear coupling of orbital parameters. Illustrative examples are provided for closed−-−shell atomic configurations, specifically the He, Be isoelectronic series, with calculations performed for energy functionals involving up to eight nonlinear parameters. This work presents the first systematic investigation of derivative-free optimization methods for Hartree-Fock−-−Roothaan energy minimization with non-integer Slater orbitals.
We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial xTQx+cTx+γx^T Q x + c^T x + γxTQx+cTx+γ over the integer points of a bounded rational polyhedron {x:Ax≤b}\{x : Ax \le b\}{x:Ax≤b}. For nnn variables and mmm inequalities, the running time is 2O(nlog⁡(n+1))(m+1)O(n)βO(n)(1+L)O(1),2^{O(n \log(n+1))} (m+1)^{O(n)} β^{O(n)} (1+L)^{O(1)},2O(nlog(n+1))(m+1)O(n)βO(n)(1+L)O(1), where βββ is one plus the maximum binary encoding length of an entry of AAA or QQQ, and LLL is the full input encoding length. The polynomial degree in LLL is absolute; in particular, the encoding of bbb, ccc, and γγγ enters only this fixed-degree factor. Our algorithm refines the integral parallelepiped cover of Goemans and Rothvoss into cells with controlled displacement sets. On each cell, either an integer displacement of negative quadratic value rules out every point as a global minimizer, or the quadratic identity supplies a separation oracle for the convex hull of each integer objective sublevel set. The integer-query feasibility theorem of Hildebrand and Goess then finds the cell minimum. A refinement through scaled lattices solves the displacement search, and a localization argument separates the encoding dependence of the constraint matrix and quadratic part from that of the remaining data. Combining the bounded algorithm with the unboundedness test of Ari and Hildebrand extends the method to arbitrary rational polyhedra.