Related papers: Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries

Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries

URL: http://arxiv.org/abs/2411.08824v1
Date: Wed, 13 Nov 2024 18:04:01 GMT
Title: Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries
Authors: Jonas Nüßlein, Leo Sünkel, Jonas Stein, Tobias Rohe, Daniëlle Schuman, Claudia Linnhoff-Popien, Sebastian Feld,
Abstract summary: We show that our modified QUBO matrix $Q_Hamilton$ describes the same energy spectrum as the original $Q$. Our algorithm achieved reductions in the number of couplings by up to $49%$ and in circuit depth by up to $41%$.
Score: 4.958204128486634
License:
Abstract: QAOA is a quantum algorithm for solving combinatorial optimization problems. It is capable of searching for the minimizing solution vector $x$ of a QUBO problem $x^TQx$. The number of two-qubit CNOT gates in the QAOA circuit scales linearly in the number of non-zero couplings of $Q$ and the depth of the circuit scales accordingly. Since CNOT operations have high error rates it is crucial to develop algorithms for reducing their number. We, therefore, present the concept of \textit{semi-symmetries} in QUBO matrices and an algorithm for identifying and factoring them out into ancilla qubits. \textit{Semi-symmetries} are prevalent in QUBO matrices of many well-known optimization problems like \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, \textit{Vertex Cover} and \textit{Graph Isomorphism}, among others. We theoretically show that our modified QUBO matrix $Q_{mod}$ describes the same energy spectrum as the original $Q$. Experiments conducted on the five optimization problems mentioned above demonstrate that our algorithm achieved reductions in the number of couplings by up to $49\%$ and in circuit depth by up to $41\%$.

Related papers

Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
We introduce the concept of textitsemi-symmetries in QUBO matrices. We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
arXiv Detail & Related papers (2024-12-18T12:05:18Z)
Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
Two algorithms are proposed to solve the Euclidean Distance Geometry problem. First algorithm converges linearly to the true solution. Second algorithm demonstrates strong numerical performance on both synthetic and real data.
arXiv Detail & Related papers (2024-10-08T21:19:22Z)
Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
arXiv Detail & Related papers (2024-10-03T15:04:01Z)
A quantum central path algorithm for linear optimization [5.450016817940232]
We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $varepsilon$-optimality. In the standard gate model (i.e., without access to quantum RAM), our algorithm can obtain highly-precise solutions to LO problems using at most $$mathcalO left( sqrtm + n textsfnnz (A) fracR_1
arXiv Detail & Related papers (2023-11-07T13:26:20Z)
An entanglement perspective on the quantum approximate optimization algorithm [0.0]
We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits. We also investigate the entanglement spectrum in connection with random matrix theory.
arXiv Detail & Related papers (2022-06-14T17:37:44Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z)
Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
arXiv Detail & Related papers (2022-03-01T19:47:16Z)
Multiplicative updates for symmetric-cone factorizations [0.0]
We introduce and analyze the symmetric-cone multiplicative update (SCMU) algorithm for computing cone factorizations. We show that the squared loss objective is non-decreasing along the trajectories of the SCMU algorithm.
arXiv Detail & Related papers (2021-08-02T09:23:39Z)
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
We study the asymmetric low-rank factorization problem: [mathbfU in mathbbRm min d, mathbfU$ and mathV$.
arXiv Detail & Related papers (2021-06-27T17:25:24Z)
Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z)
Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
arXiv Detail & Related papers (2020-10-22T19:14:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.