Optimization of a Quantum Subset Sum Oracle
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_ | 1866914962809552896 |
|---|---|
| author | Benoit, Angelo Schwartz, Sam Cytron, Ron K. |
| author_facet | Benoit, Angelo Schwartz, Sam Cytron, Ron K. |
| contents | We investigate the implementation of an oracle for the Subset Sum problem for quantum search using Grover's algorithm. Our work concerns reducing the number of qubits, gates, and multi-controlled gates required by the oracle. We describe the compilation of a Subset Sum instance into a quantum oracle, using a Python library we developed for Qiskit and have published in GitHub. We then present techniques to conserve qubits and gates along with experiments showing their effectiveness on random instances of Subset Sum. These techniques include moving from fixed to varying-width arithmetic, using partial sums of a set's integers to determine specific integer widths, and sorting the set to obtain provably the most efficient partial sums. We present a new method for computing bit-string comparisons that avoids arbitrarily large multiple-control gates, and we introduce a simple modification to the oracle that allows for approximate solutions to the Subset Sum problem via Grover search. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_01775 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimization of a Quantum Subset Sum Oracle Benoit, Angelo Schwartz, Sam Cytron, Ron K. Emerging Technologies Computational Complexity We investigate the implementation of an oracle for the Subset Sum problem for quantum search using Grover's algorithm. Our work concerns reducing the number of qubits, gates, and multi-controlled gates required by the oracle. We describe the compilation of a Subset Sum instance into a quantum oracle, using a Python library we developed for Qiskit and have published in GitHub. We then present techniques to conserve qubits and gates along with experiments showing their effectiveness on random instances of Subset Sum. These techniques include moving from fixed to varying-width arithmetic, using partial sums of a set's integers to determine specific integer widths, and sorting the set to obtain provably the most efficient partial sums. We present a new method for computing bit-string comparisons that avoids arbitrarily large multiple-control gates, and we introduce a simple modification to the oracle that allows for approximate solutions to the Subset Sum problem via Grover search. |
| title | Optimization of a Quantum Subset Sum Oracle |
| topic | Emerging Technologies Computational Complexity |
| url | https://arxiv.org/abs/2410.01775 |