A quantum-classical performance separation in nonconvex optimization
- URL: http://arxiv.org/abs/2311.00811v1
- Date: Wed, 1 Nov 2023 19:51:00 GMT
- Title: A quantum-classical performance separation in nonconvex optimization
- Authors: Jiaqi Leng, Yufan Zheng, Xiaodi Wu
- Abstract summary: We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family.
On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
- Score: 7.427989325451079
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective.
We construct a zeroth-order quantum estimator for the surrogate oracle function.
arXiv Detail & Related papers (2024-10-21T16:52:26Z) - Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
We show that solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP.
Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result.
arXiv Detail & Related papers (2024-10-17T13:43:18Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
A feature of constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard.
For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class.
We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_mathrmunsat-N_mathrmsat$, spectrally filtered quantum optimization will return states with $E leq q_m.
arXiv Detail & Related papers (2023-12-11T04:15:55Z) - Generalized Quantum Signal Processing [0.6768558752130311]
We present a Generalized Quantum Signal Processing approach, employing general SU(2) rotations as our signal processing operators.
Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that $|P|leq 1$.
In cases where only $P$ is known, we provide an efficient GPU optimization capable of identifying in under a minute of time, a corresponding $Q$ for degree on the order of $107$.
arXiv Detail & Related papers (2023-08-03T01:51:52Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization.
In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
arXiv Detail & Related papers (2023-01-10T20:43:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.