Quantum lower bounds by quantum arguments
From MaRDI portal
Publication:5894821
DOI10.1006/jcss.2002.1826zbMath1015.68075OpenAlexW3041308142MaRDI QIDQ5894821
Publication date: 12 September 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://cds.cern.ch/record/428311
Related Items (42)
A query-efficient quantum algorithm for maximum matching on general graphs ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ On the quantum query complexity of local search in two and three dimensions ⋮ Quantum algorithms for matching problems ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ A strong direct product theorem for quantum query complexity ⋮ Optimal parallel quantum query algorithms ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ Quantum bounds for 2D-grid and Dyck language ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Franchised quantum money ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Optimality proofs of quantum weight decision algorithms ⋮ Evolutionary algorithms for quantum computers ⋮ Unnamed Item ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Identification of a reversible quantum gate: assessing the resources ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ On the power of non-adaptive learning graphs ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Quantum pattern matching fast on average ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ Quantum certificate complexity ⋮ Quantum algorithms for testing and learning Boolean functions ⋮ Polynomial degree vs. quantum query complexity ⋮ The quantum query complexity of the determinant ⋮ On the power of Ambainis lower bounds ⋮ Quantum counterfeit coin problems ⋮ Unnamed Item ⋮ A quantum evolving secret sharing scheme ⋮ Unnamed Item ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Quantum Queries on Permutations with a Promise ⋮ Unnamed Item ⋮ Entanglement flow in multipartite systems ⋮ Unnamed Item ⋮ RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC ⋮ Quantum Queries on Permutations ⋮ Evaluation of exact quantum query complexities by semidefinite programming ⋮ Unnamed Item ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- Hemispheroidal quantum harmonic oscillator
- On the distributional complexity of disjointness
- The quantum query complexity of approximating the median and related statistics
- CREW PRAM<scp>s</scp> and Decision Trees
- The Probabilistic Communication Complexity of Set Intersection
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- Quantum Algorithms for Element Distinctness
This page was built for publication: Quantum lower bounds by quantum arguments
