A polynomial quantum query lower bound for the set equality problem

DOI10.1007/978-3-540-27836-8_83MaRDI QIDQ5466532zbMATH OpenOpenAlexFDO

Authors Gatis Midrijānis

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: The set equality problem is to tell whether two sets $A$ and $B$ are equal or disjoint under the promise that one of these is the case. This problem is related to the Graph Isomorphism problem. It was an open problem to find any $omega(1)$ query lower bound when sets $A$ and $B$ are given by quantum oracles. We will show that any error-bounded quantum query algorithm that solves the set equality problem must evaluate oracles $Omega(sqrt[5]fracnlnn)$ times, where $n=|A|=|B|$.

Recommendations

• SOFSEM 2004: Theory and Practice of Computer Science
• Quantum query complexity of subgraph isomorphism and homomorphism
• Quantum adversary lower bound for element distinctness with small range
• The quantum complexity of set membership
• The Quantum Query Complexity of Algebraic Properties

Cited in

(13)

• On separation between the degree of a Boolean function and the block sensitivity
• An exact quantum algorithm for a restricted subtraction game
• On exact quantum query complexity
• Unifying presampling via concentration bounds
• Superlinear advantage for exact quantum algorithms
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Quantum adversary lower bound for element distinctness with small range
• Query complexity in expectation
• Low-sensitivity functions from unambiguous certificates
• Boolean functions on \(S_n\) which are nearly linear
• Lifting Theorems for Equality
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• On the modulo degree complexity of Boolean functions

This page was built for publication: A polynomial quantum query lower bound for the set equality problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5466532)