scientific article
From MaRDI portal
Publication:3549652
zbMATH Open1232.68052arXivquant-ph/0611054MaRDI QIDQ3549652FDOQ3549652
Robert Špalek, Peter Høyer, Troy Lee
Publication date: 5 January 2009
Full work available at URL: https://arxiv.org/abs/quant-ph/0611054
Title of this publication is not available (Why is that?)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Cited In (37)
- Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum and classical query complexities of local search are polynomially related
- Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
- Quantum query as a state decomposition
- On exact quantum query complexity
- Quantum Query Algorithms are Completely Bounded Forms.
- Quantum separation of local search and fixed point computation
- Optimal parallel quantum query algorithms
- Quantum Property Testing for Bounded-Degree Graphs
- Quantum Query Algorithms Are Completely Bounded Forms
- A stronger LP bound for formula size lower bounds via clique constraints
- Quantum counterfeit coin problems
- Title not available (Why is that?)
- Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- On convex complexity measures
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Evaluation of exact quantum query complexities by semidefinite programming
- Quantum algorithms for finding constant-sized sub-hypergraphs
- Title not available (Why is that?)
- Квантовые атаки на итерационные блочные шифры
- Improved quantum query algorithms for triangle detection and associativity testing
- Title not available (Why is that?)
- A strong direct product theorem for quantum query complexity
- Superlinear advantage for exact quantum algorithms
- On the power of non-adaptive learning graphs
- A query-efficient quantum algorithm for maximum matching on general graphs
- Quantum vs Classical Proofs and Subset Verification
- Optimal deterministic quantum algorithm for the promised element distinctness problem
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- Key establishment à la Merkle in a quantum world
- Title not available (Why is that?)
- All Classical Adversary Methods are Equivalent for Total Functions
- Extended learning graphs for triangle finding
- Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
- Quantum Algorithms for Classical Probability Distributions
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549652)
