Exact quantum query complexity for total Boolean functions
| dc.creator | Midrijanis, Gatis | |
| dc.date | 2004-03-23 | |
| dc.date | 2004-03-27 | |
| dc.date.accessioned | 2026-07-07T06:09:22Z | |
| dc.date.available | 2026-07-07T06:09:22Z | |
| dc.description | We will show that if there exists a quantum query algorithm that exactly computes some total Boolean function f by making T queries, then there is a classical deterministic algorithm A that exactly computes f making O(T^3) queries. The best know bound previously was O(T^4) due to Beals et al. | |
| dc.description | 5 pages, corrected grammar, some comments added | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0403168 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0403168 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/91935 | |
| dc.subject | Quantum Physics | |
| dc.title | Exact quantum query complexity for total Boolean functions | |
| dc.type | text |