Discretized Quantum Exhaustive Search for Variational Quantum Algorithms
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_ | 1866915737129451520 |
|---|---|
| author | Alfassi, Ittay Meirom, Dekel Mor, Tal |
| author_facet | Alfassi, Ittay Meirom, Dekel Mor, Tal |
| contents | Quantum computers promise a great computational advantage over classical computers, yet currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. Variational Quantum Algorithms (VQAs) have emerged as a leading strategy to address these limitations by optimizing cost functions based on measurement results of shallow-depth circuits. However, the optimization process usually suffers from severe trainability issues as a result of the exponentially large search space, mainly local minima and barren plateaus. Here we propose a novel method that can improve variational quantum algorithms -- ``discretized quantum exhaustive search''. On classical computers, exhaustive search, also named brute force, solves small-size NP complete and NP hard problems. Exhaustive search and efficient partial exhaustive search help designing heuristics and exact algorithms for solving larger-size problems by finding easy subcases or good approximations. We adopt this method to the quantum domain, by relying on mutually unbiased bases for the $2^n$-dimensional Hilbert space. We define a discretized quantum exhaustive search that works well for small size problems. We provide an example of an efficient partial discretized quantum exhaustive search for larger-size problems, in order to extend classical tools to the quantum computing domain, for near future and far future goals. Our method enables obtaining intuition on NP-complete and NP-hard problems as well as on Quantum Merlin Arthur (QMA)-complete and QMA-hard problems. We demonstrate our ideas in many simple cases, providing the energy landscape for various problems and presenting two types of energy curves via VQAs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17659 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Discretized Quantum Exhaustive Search for Variational Quantum Algorithms Alfassi, Ittay Meirom, Dekel Mor, Tal Quantum Physics Quantum computers promise a great computational advantage over classical computers, yet currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. Variational Quantum Algorithms (VQAs) have emerged as a leading strategy to address these limitations by optimizing cost functions based on measurement results of shallow-depth circuits. However, the optimization process usually suffers from severe trainability issues as a result of the exponentially large search space, mainly local minima and barren plateaus. Here we propose a novel method that can improve variational quantum algorithms -- ``discretized quantum exhaustive search''. On classical computers, exhaustive search, also named brute force, solves small-size NP complete and NP hard problems. Exhaustive search and efficient partial exhaustive search help designing heuristics and exact algorithms for solving larger-size problems by finding easy subcases or good approximations. We adopt this method to the quantum domain, by relying on mutually unbiased bases for the $2^n$-dimensional Hilbert space. We define a discretized quantum exhaustive search that works well for small size problems. We provide an example of an efficient partial discretized quantum exhaustive search for larger-size problems, in order to extend classical tools to the quantum computing domain, for near future and far future goals. Our method enables obtaining intuition on NP-complete and NP-hard problems as well as on Quantum Merlin Arthur (QMA)-complete and QMA-hard problems. We demonstrate our ideas in many simple cases, providing the energy landscape for various problems and presenting two types of energy curves via VQAs. |
| title | Discretized Quantum Exhaustive Search for Variational Quantum Algorithms |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2407.17659 |