Exact quantum query complexity for total Boolean functions
classification
🪐 quant-ph
keywords
algorithmbooleancomputesexactlymakingquantumqueriesquery
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Boolean degree one functions on the Grassmann scheme
Exposition of the result that Boolean degree one functions on J_q(n,k) are trivial when min(k,n-k) >= 2 and n is large enough.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.