Open Problems Related to Quantum Query Complexity

Abstract

I offer a case that quantum query complexity still has loads of enticing and fundamental open problems—from relativized QMA versus QCMA and BQP versus IP , to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.

Document Details

• Document Type: Pub Defense Publication
• Publication Date: Dec 21, 2021
• Source ID: 10.1145/3488559

Entities

People

• Scott Aaronson

Organizations

• United States Department of Defense
• University of Texas at Austin

Tags

Readers

• Applied Combinatorial Optimization and Logic Circuit Design.
• Aviation Science / Aeronautics.
• Graph Algorithms and Convex Optimization.

Technology Areas

• Quantum Computing
• Space