2005/01/25 by Gatis Midrijānis, Gatis Midrijanis, Midrijanis, Gatis
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0501142
10 pages
openalex publication_date 2005/01/25 · arxiv created 2005/06/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness from algorithms). Firstly, we show that D(f) = O(Q1(f)3) for any total function f, where D(f) is the minimal number of queries made by a deterministic query algorithm and Q1(f) is the number of queries made by any quantum query algorithm (decision tree analog in quantum case) with one-sided constant error; both algorithms compute function f. Secondly, we show that for all total Boolean functions f holds R0(f)=O(R2(f)2 log N), where R0(f) and R2(f) are randomized zero-sided (a.k.a Las Vegas) and two-sided (a.k.a. Monte Carlo) error query complexities.