Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917836294717440 |
|---|---|
| author | Nüßlein, Jonas Sünkel, Leo Stein, Jonas Rohe, Tobias Schuman, Daniëlle Linnhoff-Popien, Claudia Feld, Sebastian |
| author_facet | Nüßlein, Jonas Sünkel, Leo Stein, Jonas Rohe, Tobias Schuman, Daniëlle Linnhoff-Popien, Claudia Feld, Sebastian |
| contents | 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\%$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08824 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries Nüßlein, Jonas Sünkel, Leo Stein, Jonas Rohe, Tobias Schuman, Daniëlle Linnhoff-Popien, Claudia Feld, Sebastian Quantum Physics 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\%$. |
| title | Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.08824 |