Applying the Quantum Alternating Operator Ansatz to the Graph Matching
Problem
- URL: http://arxiv.org/abs/2011.11918v1
- Date: Tue, 24 Nov 2020 06:36:11 GMT
- Title: Applying the Quantum Alternating Operator Ansatz to the Graph Matching
Problem
- Authors: Sagnik Chatterjee and Debajyoti Bera
- Abstract summary: We design a derivation technique to tackle a few problems over maximal matchings in graphs.
We get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the W -states as input.
Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a 2-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings.
- Score: 0.5584060970507505
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Quantum Alternating Operator Ansatz (QAOA+) framework has recently gained
attention due to its ability to solve discrete optimization problems on noisy
intermediate-scale quantum (NISQ) devices in a manner that is amenable to
derivation of worst-case guarantees. We design a technique in this framework to
tackle a few problems over maximal matchings in graphs. Even though maximum
matching is polynomial-time solvable, most counting and sampling versions are
#P-hard.
We design a few algorithms that generates superpositions over matchings
allowing us to sample from them. In particular, we get a superposition over all
possible matchings when given the empty state as input and a superposition over
all maximal matchings when given the W -states as input.
Our main result is that the expected size of the matchings corresponding to
the output states of our QAOA+ algorithm when ran on a 2-regular graph is
greater than the expected matching size obtained from a uniform distribution
over all matchings. This algorithm uses a W -state as input and we prove that
this input state is better compared to using the empty matching as the input
state.
Related papers
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards.
For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
arXiv Detail & Related papers (2023-08-23T08:38:53Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
We prove concentration properties at any constant level (number of layers) on ensembles of random optimization problems in the infinite size limit.
Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral.
We show that the performance of the QAOA at constant levels is bounded away from optimality for pure $q$-spin models when $qge 4$ and is even.
arXiv Detail & Related papers (2022-04-21T17:40:39Z) - Deep Probabilistic Graph Matching [72.6690550634166]
We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints.
The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
arXiv Detail & Related papers (2022-01-05T13:37:27Z) - Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques.
We show that computing the quantum guesswork of qubit ensembles with uniform probability distribution leads to a more-than-quadratic speedup.
As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.
arXiv Detail & Related papers (2021-12-03T01:24:57Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
We present methods for constructing any target coupling graph using limited global controls in an Ising-like quantum spin system.
Our approach is motivated by implementing the quantum approximate optimization algorithm (QAOA) on trapped ion quantum hardware.
Noisy simulations of Max-Cut QAOA show that our implementation is less susceptible to noise than the standard gate-based compilation.
arXiv Detail & Related papers (2020-11-16T18:43:09Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers.
We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs.
We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
arXiv Detail & Related papers (2020-11-10T22:17:50Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: A Typical Case [6.810856082577402]
The quantum circuit has p applications of a unitary operator that respects the locality of the graph.
We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large.
arXiv Detail & Related papers (2020-04-20T00:48:02Z)
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.