One of the main challenges in quantum information is to find more applications for quantum computers, specifically new algorithms. This would further justify continuing investment into building large quantum computers. This work package aims at new quantum algorithms in several areas, optimizing them for (initially limited) quantum resources, and seeing how limited quantum resources can be aided by classical computers.
Workpackage Leader: Ronald de Wolf (CWI Amsterdam)
Significant achivements
- We designed several new quantum algorithms for optimisation problems, including for solving linear and semidefinite programs (based on quantum adaptations of multiplicative-weights and interior-point methods), for minimisation of submodular functions, and for finding a Hamiltonian cycle in a graph (by speeding up a dynamic programming approach). These quantum algorithms are typically polynomially faster than the best-possible classical algorithms. For example, we give the first polynomial quantum speed-up over the classical Held-Karp algorithm for Hamiltonian cycle (which is the decision version of TSP). However, we also give an exponential quantum speed-up in terms of the number of membership queries needed to implement a separation oracle in general convex optimisation problems.
- We designed several new quantum walk algorithms, including one that can find a marked item in a given graph in a time that is essentially the square-root of the time needed for classical random walks (classical hitting time). This solved a long-standing open problem.
- We gave a distributed algorithm that can compute the diameter D of an n-vertex graph in O(sqrt{Dn}) rounds of short nearest neighbour communication; classically this task requires roughly n rounds. This is the first example of a quantum speed-up in the CONGEST model of distributed computing.
- We analyzed in detail the resource requirements needed for certain quantum constraint solvers for NP-hard problems. We developed a python-based library framework for resource estimation of large quantum algorithms and used it to derive a space-efficient implementation of Montanaro’s backtracking algorithm.
- In a large quantum computing system, we expect quantum and classical resources to coexist and interact closely. We extended the Gottesman-Knill theorem and analyzed tradeoffs between the stabilizer parts of the input to a circuit and the cost of classically simulating it, and the role of magic states in stabilizer and matchgate circuits.