Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems

DOI10.4230/LIPIcs.TQC.2018.3OpenAlexW2796181412MaRDI QIDQ5889069

Ansis Rosmanis, Aleksandrs Belovs

Publication date: 26 April 2023

Full work available at URL: https://arxiv.org/abs/1712.10194

zbMATH Keywords

representation theoryquantum query complexityadversary bounddual learning graphs

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (1)

Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of non-adaptive learning graphs
• On the power of Ambainis lower bounds
• Complexity measures and decision tree complexity: a survey.
• The quantum query complexity of the hidden subgroup problem is polynomial
• Forrelation
• Adversary lower bound for the k-sum problem
• Sequential measurements, disturbance and property testing
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Separations in query complexity using cheat sheets
• Span programs for functions with constant-sized 1-certificates
• Quantum Query Complexity of State Conversion
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• Quantum lower bounds by quantum arguments

This page was built for publication: Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems