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
- 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 [77.8485863487028]
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) - Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions [8.495749905129278]
Despite progress in classical lower bounds for non optimization, these bounds are still widely open.
Omegabig(frac-1+ppp)$ regarding the first setting.
Omegano()$ regarding the second setting.
Omega()$ if gradient function is meand smooth.
Omega()$ if gradient function is meand smooth.
Omega()$ if gradient function is meand smooth.
Omega()$ if gradient function is meand smooth.
arXiv Detail & Related papers (2022-12-07T19:02:36Z) - 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 algorithms for approximate function loading [0.0]
We introduce two approximate quantum-state preparation methods for the NISQ era inspired by the Grover-Rudolph algorithm.
A variational algorithm capable of loading functions beyond the aforementioned smoothness conditions is proposed.
arXiv Detail & Related papers (2021-11-15T17:36:13Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - 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.