English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The quantum approximate optimization algorithm (QAOA) has the potential toapproximately solve complex combinatorial optimization problems in polynomialtime. However, current noisy quantum devices cannot solve large problems due tohardware constraints. In this work, we develop an algorithm that decomposes theQAOA input problem graph into a smaller problem and solves MaxCut using QAOA onthe reduced graph. The algorithm requires a subroutine that can be classical orquantum--in this work, we implement the algorithm twice on each graph. Oneimplementation uses the classical solver Gurobi in the subroutine and the otheruses QAOA. We solve these reduced problems with QAOA. On average, the reducedproblems require only approximately 1/10 of the number of vertices than theoriginal MaxCut instances. Furthermore, the average approximation ratio of theoriginal MaxCut problems is 0.75, while the approximation ratios of thedecomposed graphs are on average of 0.96 for both Gurobi and QAOA. With thisdecomposition, we are able to measure optimal solutions for ten 100-vertexgraphs by running single-layer QAOA circuits on the Quantinuum trapped-ionquantum computer H1-1, sampling each circuit only 500 times. This approach isbest suited for sparse, particularly $k$-regular graphs, as $k$-regular graphson $n$ vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$vertices in polynomial time. Further reductions can be obtained with apotential trade-off in computational time. While this paper applies thedecomposition method to the MaxCut problem, it can be applied to more generalclasses of combinatorial optimization problems.

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms