scientific article
From MaRDI portal
Publication:3549652
zbMATH Open1232.68052arXivquant-ph/0611054MaRDI QIDQ3549652FDOQ3549652
Authors: Peter Høyer, Troy Lee, Robert Špalek 
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)
- 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
- Quantum vs. classical proofs and subset verification
- On exact quantum query complexity
- Quantum separation of local search and fixed point computation
- Provably secure key establishment against quantum adversaries
- Optimal parallel quantum query algorithms
- Quantum Query Algorithms Are Completely Bounded Forms
- A stronger LP bound for formula size lower bounds via clique constraints
- Quantum counterfeit coin problems
- Quantum attacks against iterated block ciphers
- Title not available (Why is that?)
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- 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
- All classical adversary methods are equivalent for total functions
- Quantum algorithms for finding constant-sized sub-hypergraphs
- Quantum query algorithms are completely bounded forms
- 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
- Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- 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
- Extended learning graphs for triangle finding
- Quantum property testing for bounded-degree graphs
- 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)
