Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908634383908864 |
|---|---|
| author | Moghadam, Ali Hadizadeh Kazemikhah, Payman Aghababa, Hossein |
| author_facet | Moghadam, Ali Hadizadeh Kazemikhah, Payman Aghababa, Hossein |
| contents | The clique problems, including $k$-CLIQUE and Triangle Finding, form an important class of computational problems; the former is an NP-complete problem, while the latter directly gives lower bounds for Matrix Multiplication. A number of previous efforts have approached these problems with Quantum Computing methods, such as Amplitude Amplification. In this paper, we provide new Quantum oracle designs based on the 1-factorization of complete graphs, all of which have depth $O(n)$ instead of the $O(n^2)$ presented in previous studies. Also, we discuss the usage of one of these oracles in bringing the Triangle Finding time complexity down to $O(n^{2.25} poly(log n))$, compared to the $O(n^{2.38})$ classical record. Finally, we benchmark the number of required Amplitude Amplification iterations for another presented oracle, for solving $k$-CLIQUE. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_16827 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems Moghadam, Ali Hadizadeh Kazemikhah, Payman Aghababa, Hossein Quantum Physics The clique problems, including $k$-CLIQUE and Triangle Finding, form an important class of computational problems; the former is an NP-complete problem, while the latter directly gives lower bounds for Matrix Multiplication. A number of previous efforts have approached these problems with Quantum Computing methods, such as Amplitude Amplification. In this paper, we provide new Quantum oracle designs based on the 1-factorization of complete graphs, all of which have depth $O(n)$ instead of the $O(n^2)$ presented in previous studies. Also, we discuss the usage of one of these oracles in bringing the Triangle Finding time complexity down to $O(n^{2.25} poly(log n))$, compared to the $O(n^{2.38})$ classical record. Finally, we benchmark the number of required Amplitude Amplification iterations for another presented oracle, for solving $k$-CLIQUE. |
| title | Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2308.16827 |