Quantum algorithms (CMSC 858Q, Spring 2021): Project topic ideas

The following is a list of some potential project topics, with one or two key references for each. This list is by no means exhaustive, and you are welcome to choose a topic not on this list. (In particular, you might find other topics of interest in the Quantum Algorithm Zoo.)

• Algebraic problems
  • Quantum algorithms for solvable groups [Watrous]
  • Quantum algorithm for counting points on algebraic curves [Kedlaya]
  • Connection between the dihedral HSP and lattice problems [Regev]
  • Quantum algorithms for hidden shift problems [DHI] [Roetteler]
  • Quantum reductions for the HSP: Hidden translation and orbit coset [FIMSS]
  • Entangled measurements are required for the symmetric group [MRS] [HMRRS]
  • Quantum algorithms for arbitrary-degree number fields [EHKS] [BS16]
  
  
• Quantum walk
  • General framework for quantum walk search algorithms [MNRS]
  • Finding marked items with quantum walks [AGJK]
  • Verifying matrix products [BS06]
  • Testing group commutativity [MN]
  • Quantum walk speedup of backtracking algorithms [Montanaro]
  
  
• Quantum query complexity
  • Lower bounds for quantum state generation [AMRR]
  • Limitations on quantum algorithms for symmetric functions [AA] [Chailloux] [BCGKPW]
  • Adversary lower bounds for element distinctness, collision, and k-sum [Belovs] [BS12] [BR]
  • Time-space tradeoffs [KSW]
  • Triangle finding [Le Gall]
  • Superquadratic separations for total functions [ABBLSS] [ABK]
  • Limitations on quantum speedup for total functions [ABKRT]
  • Graph connectivity with cut queries [LSZ]
  
  
• Quantum simulation
  • Simulating lattice Hamiltonians [HHKL]
  • Simulation with nearly optimal dependence on spectral norm [Low]
  • Product formula error bounds [CSTWZ]
  • Quantum algorithms for quantum chemistry [LBGHMWB] [LBHSRRT]
  • Simulating low-energy states [SS]
  • Universality results for analog simulation [CMP]
  
  
• Other topics
  • Searching an ordered list [FGGS] [HNS]
  • Evaluating tensor networks [AL]
  • Unique sink orientation problem [Bacon]
  • Quantum dynamic programming [ABIKPV]
  • Quantum spectral sparsification [AW]

Web Accessibility