Quantum Applications

The field of quantum computing, which is based on the principles of quantum mechanics and uses so-called qubits as an information unit, has become increasingly relevant since the publication of quantum algorithms by Shor and Grover in the 1990s. But science has long been concerned with the possibility of a quantum computer – famous physicist Richard Feynman postulated in his 1982 paper “Simulating Physics with Computers” that in order to simulate a quantum system also a quantum computer is required. There are several approaches or models for such quantum computer architectures, see Quantum Gate Computing and Adiabatic Quantum Computing. By now, there is company D-Wave Systems to have built quantum annealing hardware based on Adiabatic Quantum Computing.

The lecture discusses the quantum annealing approach, which is based on the adiabatic theorem and is related to the algorithmic procedure of simulated annealing. In this context, applications for the solution of (combinatorial) optimization problems are discussed and a brief comparison between “classic” complexity and quantum complexity is given.

The aim of the lecture is to develop an understanding of the quantum mechanical foundations of quantum computing, to get to know formalizations and solution methods for (combinatorial) optimization problems, and to practice their practical application in the context of quantum annealing. We set value on both, mathematical and physical principles (theory) and the own application (practice).

A selection of the topics covered is:

  • Computer models
    • Turing machine, Von Neumann architecture
    • Approaches to the physical realization of quantum computers
    • Quantum Gate Computing vs. Adiabatic Quantum Computing
  • Fundamentals of quantum mechanics and quantum computing
    • State, observable, measurement
    • Hamiltonians, Schrödinger equation
    • Qubits and qubit operations
    • Superposition, entanglement and teleportation of states
    • Quantum algorithms
  • Optimization
    • Integer linear / binary / quadratic / combinatorial optimization
    • Optimization problems (e.g., SAT, Knapsack, TSP, QAP, VRP)
    • Classical complexity / quantum complexity
    • Exact and (meta) heuristic solution methods
  • Quantum annealing
    • Adiabatic algorithm, adiabatic theorem
    • QUBO and Simulated Annealing
    • Ising and Quantum Annealing
    • Problem Hamiltonians
    • D-Wave Systems' Quantum Annealing Hardware
  • Quantum Annealing Applications
    • Examples: Maximum Clique, Flight Gate Assignment, Robot Movement, Vehicle Routing, Portfolio Optimization