scientific article
From MaRDI portal
Publication:3002756
DOI10.4086/toc.2005.v001a003zbMath1213.68281arXivquant-ph/0305179OpenAlexW2112553910MaRDI QIDQ3002756
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0305179
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
quantum computationquantum query algorithmscomplexity of Boolean functionsquantum lower boundselement distinctness
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (32)
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Deterministic quantum search with adjustable parameters: implementations and applications ⋮ Near-optimal quantum algorithms for string problems ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Unnamed Item ⋮ Algorithmic Polynomials ⋮ Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations ⋮ The hardest halfspace ⋮ Unnamed Item ⋮ Element distinctness revisited ⋮ Quantum algorithm for the multicollision problem ⋮ Polynomial degree vs. quantum query complexity ⋮ On the power of Ambainis lower bounds ⋮ Quantum algorithm to find invariant linear structure of \(MD\) hash functions ⋮ A quantum evolving secret sharing scheme ⋮ Unnamed Item ⋮ Quantum Random Walks – New Method for Designing Quantum Algorithms ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ On the compressed-oracle technique, and post-quantum security of proofs of sequential work ⋮ Unnamed Item ⋮ Key establishment à la Merkle in a quantum world ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities
This page was built for publication:
