Vorlesung Quantenalgorithmen vom 11.02.03

Themen

• NP-Sprachen
• Die Klasse QMA=BQNP
• k-LOCAL HAMILTONIAN
• NP-Probleme und k-LOCAL HAMILTONIAN
  • 3-SAT<=3-LOCAL HAMILTONIAN
  • INDEPENDENT SET<=2-LOCAL HAMILTONIAN
• 5-LOCAL HAMILTONIAN ist QMA-vollständig

Literatur und Links zur Vorlesung

• Chapter 14: "The quantum analogue of NP: the class BQNP", in:
  A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi,
  Classical and Quantum Computation,
  Graduate Studies in Mathematics, vol. 47, AMS Press, 2002.
• Dorit Aharonov and Tomer Naveh.
  "Quantum NP - A Survey".
  quant-ph/0210077.
• Pawel Wocjan and Thomas Beth.
  "The 2-local Hamiltonian problem encompasses NP".
  quant-ph/0301087.
• Pawel Wocjan, Dominik Janzing, and Thomas Beth.
  "Treating the Independent Set Problem by 2D Ising Interactions with Adiabatic Quantum Computing".
  quant-ph/0302027.
• Alexei Kitaev and
• John Watrous.
  "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.
  Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 608-617, 2000.