Multi-angle quantum approximate optimization algorithm
Abstract The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2022-04-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-022-10555-8 |
| _version_ | 1828839786419322880 |
|---|---|
| author | Rebekah Herrman Phillip C. Lotshaw James Ostrowski Travis S. Humble George Siopsis |
| author_facet | Rebekah Herrman Phillip C. Lotshaw James Ostrowski Travis S. Humble George Siopsis |
| author_sort | Rebekah Herrman |
| collection | DOAJ |
| description | Abstract The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices. |
| first_indexed | 2024-12-12T19:30:14Z |
| format | Article |
| id | doaj.art-378360ed501a4a5b90eb9bcfe60148e2 |
| institution | Directory Open Access Journal |
| issn | 2045-2322 |
| language | English |
| last_indexed | 2024-12-12T19:30:14Z |
| publishDate | 2022-04-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj.art-378360ed501a4a5b90eb9bcfe60148e22022-12-22T00:14:26ZengNature PortfolioScientific Reports2045-23222022-04-0112111010.1038/s41598-022-10555-8Multi-angle quantum approximate optimization algorithmRebekah Herrman0Phillip C. Lotshaw1James Ostrowski2Travis S. Humble3George Siopsis4Department of Industrial and Systems Engineering, University of Tennessee at KnoxvilleQuantum Computing Institute, Oak Ridge National LaboratoryDepartment of Industrial and Systems Engineering, University of Tennessee at KnoxvilleQuantum Computing Institute, Oak Ridge National LaboratoryDepartment of Physics and Astronomy, University of Tennessee at KnoxvilleAbstract The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.https://doi.org/10.1038/s41598-022-10555-8 |
| spellingShingle | Rebekah Herrman Phillip C. Lotshaw James Ostrowski Travis S. Humble George Siopsis Multi-angle quantum approximate optimization algorithm Scientific Reports |
| title | Multi-angle quantum approximate optimization algorithm |
| title_full | Multi-angle quantum approximate optimization algorithm |
| title_fullStr | Multi-angle quantum approximate optimization algorithm |
| title_full_unstemmed | Multi-angle quantum approximate optimization algorithm |
| title_short | Multi-angle quantum approximate optimization algorithm |
| title_sort | multi angle quantum approximate optimization algorithm |
| url | https://doi.org/10.1038/s41598-022-10555-8 |
| work_keys_str_mv | AT rebekahherrman multianglequantumapproximateoptimizationalgorithm AT phillipclotshaw multianglequantumapproximateoptimizationalgorithm AT jamesostrowski multianglequantumapproximateoptimizationalgorithm AT travisshumble multianglequantumapproximateoptimizationalgorithm AT georgesiopsis multianglequantumapproximateoptimizationalgorithm |