Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.17442 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929605842042880 |
|---|---|
| author | Boulebnane, Sami Ciudad-Alañón, Maria Mineh, Lana Montanaro, Ashley Vaishnav, Niam |
| author_facet | Boulebnane, Sami Ciudad-Alañón, Maria Mineh, Lana Montanaro, Ashley Vaishnav, Niam |
| contents | In this work we develop theoretical techniques for analysing the performance of the quantum approximate optimization algorithm (QAOA) when applied to random boolean constraint satisfaction problems (CSPs), and use these techniques to compare the complexity of a variety of CSPs, such as $k$-SAT, 1-in-$k$ SAT, and NAE-SAT. Our techniques allow us to compute the success probability of QAOA with one layer and given parameters, when applied to randomly generated instances of CSPs with $k$ binary variables per constraint, in time polynomial in $n$ and $k$. We apply this algorithm to all boolean CSPs with $k=3$ and a large number of CSPs with $k=4$, $k=5$, and compare the resulting complexity with the complexity of solving the corresponding CSP using the standard solver MapleSAT, determined experimentally. We find that random $k$-SAT seems to be the most promising of these CSPs for demonstrating a quantum-classical separation using QAOA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17442 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Applying the quantum approximate optimization algorithm to general constraint satisfaction problems Boulebnane, Sami Ciudad-Alañón, Maria Mineh, Lana Montanaro, Ashley Vaishnav, Niam Quantum Physics In this work we develop theoretical techniques for analysing the performance of the quantum approximate optimization algorithm (QAOA) when applied to random boolean constraint satisfaction problems (CSPs), and use these techniques to compare the complexity of a variety of CSPs, such as $k$-SAT, 1-in-$k$ SAT, and NAE-SAT. Our techniques allow us to compute the success probability of QAOA with one layer and given parameters, when applied to randomly generated instances of CSPs with $k$ binary variables per constraint, in time polynomial in $n$ and $k$. We apply this algorithm to all boolean CSPs with $k=3$ and a large number of CSPs with $k=4$, $k=5$, and compare the resulting complexity with the complexity of solving the corresponding CSP using the standard solver MapleSAT, determined experimentally. We find that random $k$-SAT seems to be the most promising of these CSPs for demonstrating a quantum-classical separation using QAOA. |
| title | Applying the quantum approximate optimization algorithm to general constraint satisfaction problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.17442 |