REVIEW 2 cited by
A quantum-classical performance separation in nonconvex optimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
In this paper, we identify a family of nonconvex continuous optimization instances, each $d$-dimensional instance with $2^d$ local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any $d$-dimensional instance from this family using $\widetilde{\mathcal{O}}(d^3)$ quantum queries to the function value and $\widetilde{\mathcal{O}}(d^4)$ additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.
Forward citations
Cited by 2 Pith papers
-
Stochastic Quantum Hamiltonian Descent
SQHD is a gate-based quantum algorithm that approximates a Lindblad dynamics blending Hamiltonian descent with stochastic component noise, giving an order-2 weak approximation and an O(1/t + eta sigma*) convergence bo...
-
Quantum Optimization via Gradient-Based Hamiltonian Descent
Gradient-based QHD, a quantum Hamiltonian descent variant that inserts the gradient into the kinetic term, is claimed to converge at O(t^-2) in theory and to outperform QHD and classical methods in 2D tests.
Discussion (0). Continue with ORCID to comment.