Quantum lower bounds by polynomials

DOI10.1145/502090.502097zbMath1127.68404arXivquant-ph/9802049OpenAlexW2122780600WikidataQ56701652 ScholiaQ56701652MaRDI QIDQ5441359

Robert Beals, Richard Cleve, Michele Mosca, Harry Buhrman, Ronald de Wolf

Publication date: 11 February 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/9802049

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (only showing first 100 items - show all)

From Monte Carlo to quantum computation ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Query Complexity in Expectation ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ The power of various real-valued quantum queries ⋮ The quantum query complexity of the abelian hidden subgroup problem ⋮ Quantum algorithms for matching problems ⋮ On the black-box complexity of Sperner's Lemma ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Multi-query Quantum Sums ⋮ Bounds on the Fourier coefficients of the weighted sum function ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ Quantum separation of local search and fixed point computation ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Block sensitivity of weakly symmetric functions ⋮ Quantum query as a state decomposition ⋮ A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Quantum query complexity of almost all functions with fixed on-set size ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ A strong direct product theorem for quantum query complexity ⋮ Beyond quadratic speedups in quantum attacks on symmetric schemes ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Optimal separation in exact query complexities for Simon's problem ⋮ Optimal parallel quantum query algorithms ⋮ A note on the search for \(k\) elements via quantum walk ⋮ Nonadaptive quantum query complexity ⋮ Efficient quantum algorithms for simulating sparse Hamiltonians ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ From Quantum Query Complexity to State Complexity ⋮ Approximate span programs ⋮ Quantum and classical query complexities for generalized Simon's problem ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ Superiority of exact quantum automata for promise problems ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ A quantum algorithm to approximate the linear structures of Boolean functions ⋮ Unnamed Item ⋮ An improved lower bound on query complexity for quantum PAC learning ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Parity decision tree in classical-quantum separations for certain classes of Boolean functions ⋮ Optimality proofs of quantum weight decision algorithms ⋮ On the uselessness of quantum queries ⋮ EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS ⋮ Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$ ⋮ Unbounded-error quantum query complexity ⋮ Intricacies of quantum computational paths ⋮ Evolutionary algorithms for quantum computers ⋮ Analysis and applications of quantum walks ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function ⋮ Fourier 1-norm and quantum speed-up ⋮ Quantum lower bounds by entropy numbers ⋮ On the complexity of the multivariate Sturm-Liouville eigenvalue problem ⋮ The hardest halfspace ⋮ Extremal properties of polynomial threshold functions ⋮ Quantum certificate complexity ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Polynomial degree vs. quantum query complexity ⋮ Fourier concentration from shrinkage ⋮ On the parity complexity measures of Boolean functions ⋮ On the complexity of searching for a maximum of a function on a quantum computer ⋮ The quantum query complexity of the determinant ⋮ On the power of Ambainis lower bounds ⋮ Testing Juntas: A Brief Survey ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Unnamed Item ⋮ Block sensitivity of minterm-transitive functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exponential separation of quantum and classical online space complexity ⋮ On the solution of trivalent decision problems by quantum state identification ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Quantum algorithms for algebraic problems ⋮ Extended learning graphs for triangle finding ⋮ Query complexity of generalized Simon's problem ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Generic authenticated key exchange in the quantum random oracle model ⋮ Classical vs quantum random oracles ⋮ Quantum Queries on Permutations with a Promise ⋮ QCCA-secure generic key encapsulation mechanism with tighter security in the quantum random oracle model ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Enhanced algorithms for local search ⋮ Quantum and classical tradeoffs ⋮ Quantum communication and complexity. ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Evaluation of exact quantum query complexities by semidefinite programming ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities ⋮ Mathematical models of quantum computation ⋮ On exact quantum query complexity

This page was built for publication: Quantum lower bounds by polynomials