Algorithmic Aspects of Quantum Computing

Project Topics

Your paper is due on April 21, before class. You are allowed to write at most 4 pages, using LaTeX with the IEEEtran.cls document class.

• Math into LaTeX, an introductory LaTeX book. Examples.
• The document class IEEEtran.tar.gz
• IEEETran.cls class usage and the resulting elephant

• The collision problem

  The collision problem is to decide whether a function is one-to-one or two-to-one, given that one of these is the case, see quant-ph/0111102, quant-ph/0112086.

• The hidden subgroup problems
  • Dihedral groups, see quant-ph/0302112 (Jeb Belcher)

  • Affine groups, see quant-ph/0211124

• Quantum algorithms for Pell's equation

  A quantum algorithm for solving the diophantine equation x²-dy²=1, see pell.

• An applet illustrating Shor's factoring algorithm (Bryan Graham)

• Quantum search of spatial regions (Samuel Rodriguez)

  Is it possible to speed up the search of a physical region? It is possible, see quant-ph/0303041

• Quantum lower bound for sorting (Nicolas Neumann)

  Comparison based sorting needs W(n log n) comparisons on a quantum computer, see quant-ph/0102078

• Quantum lower bounds by polynomials (Ge Xia)

  A lower bound technique for the number of black-box queries, see quant-ph/9802049.

• Quantum error correcting codes
  • Applet illustrating 5-qubit and 7-qubit QECCs. (Pradeep Kiran Sarvepalli)

  • Binary stabilizer codes [GF(4) paper, search for Peter Shor on IEEE xplore] (Santosh Kumar)

  • Nonbinary stabilizer codes have been discussed in quant-ph/0005008. (Keith Massie)

• Fault-tolerant quantum computing (Avanti Ketkar)

  A implementation of a quantum computer needs to be resilient against operational errors and decoherence errors Steane 99.

• Security proof of the BB84 protocol (Prasanth Nittala)

  A security proof of the quantum key distribution protocol by Bennett and Brassard, see quant-ph/0003004.

• Secure multiparty computation (Jimmie Hayes)

  The quantum version of secure function evaluation, see secure multiparty computation.

• Mutually unbiased bases (Adam Lacey)

  A important primitive in quantum cryptography MUB.

• The mean king's problem (Nikolai Sinitsyn)

  A neat application of mutually unbiased bases quant-ph/0101134

• The Kane quantum computer model (Larz Smith)

  A proposal to realize a quantum computer in silicon Kane 98

• Quantum computing with Josephson junctions

• Experimental realizations of quantum teleportation Marcikic et al. (Josh Dahms)