scientific article
From MaRDI portal
Publication:3549652
zbMath1232.68052arXivquant-ph/0611054MaRDI QIDQ3549652
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: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (36)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ 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 ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Quantum separation of local search and fixed point computation ⋮ Quantum query as a state decomposition ⋮ A strong direct product theorem for quantum query complexity ⋮ Optimal parallel quantum query algorithms ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Unnamed Item ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ On the power of non-adaptive learning graphs ⋮ Quantum vs Classical Proofs and Subset Verification ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Improved quantum query algorithms for triangle detection and associativity testing ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ On convex complexity measures ⋮ Quantum counterfeit coin problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Квантовые атаки на итерационные блочные шифры ⋮ Extended learning graphs for triangle finding ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Key establishment à la Merkle in a quantum world ⋮ Evaluation of exact quantum query complexities by semidefinite programming ⋮ Unnamed Item ⋮ On exact quantum query complexity ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound
This page was built for publication:
