Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2014
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/1407.4345 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910591394775040 |
|---|---|
| author | Ellerman, David |
| author_facet | Ellerman, David |
| contents | By using a new way to encode Boolean functions in a reversible gate, an algorithm is developed in quantum computing over Z_2, symbolized QC/2, (as opposed to QC over C) that needs only one function evaluation to solve the Grover Database Search Problem of finding a designated record among 2^m records for any m. In the usual Grover algorithm in quantum computing over C, one needs essentially Sqrt(2^m) function evaluations as opposed to the average of (2^m)/2 functions evaluations needed in the classical algorithm. The one function evaluation of the QC/2 algorithm (for any m) represents such a super speedup, even over the Grover algorithm in QC/C, that one feels something has gone awry. Indeed, our analysis of the transparent calculations of Boolean functions over Z_2 shows that the classical algorithm is just repackaged in a rather obvious way in the single function evaluation of the QC/2 algorithm--whereas the calculations are hidden and non-transparent in the Grover QC/C algorithm using C. The conclusion in both cases (which is rather obvious in the QC/2 case) is that "counting function evaluations" is a false coin to measure speedup in the comparison between quantum and classical computing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1407_4345 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | In Quantum Computing Speedup Illusory?: The False Coin of "Counting Function Evaluations" Ellerman, David Quantum Physics 81P68 By using a new way to encode Boolean functions in a reversible gate, an algorithm is developed in quantum computing over Z_2, symbolized QC/2, (as opposed to QC over C) that needs only one function evaluation to solve the Grover Database Search Problem of finding a designated record among 2^m records for any m. In the usual Grover algorithm in quantum computing over C, one needs essentially Sqrt(2^m) function evaluations as opposed to the average of (2^m)/2 functions evaluations needed in the classical algorithm. The one function evaluation of the QC/2 algorithm (for any m) represents such a super speedup, even over the Grover algorithm in QC/C, that one feels something has gone awry. Indeed, our analysis of the transparent calculations of Boolean functions over Z_2 shows that the classical algorithm is just repackaged in a rather obvious way in the single function evaluation of the QC/2 algorithm--whereas the calculations are hidden and non-transparent in the Grover QC/C algorithm using C. The conclusion in both cases (which is rather obvious in the QC/2 case) is that "counting function evaluations" is a false coin to measure speedup in the comparison between quantum and classical computing. |
| title | In Quantum Computing Speedup Illusory?: The False Coin of "Counting Function Evaluations" |
| topic | Quantum Physics 81P68 |
| url | https://arxiv.org/abs/1407.4345 |