Combinatorics of computing
Président: Eva Rotenberg
(Technical University of Denmark)
- KELLY BOOTHBY, D-Wave Systems
Discrete methods and applications in quantum annealing [PDF]
Quantum annealing is a model of quantum computing that, in its simplest form, can be thought of as a heuristic approach to solving discrete combinatorial optimization problems, such as MAX-CUT. More generally it can be used to generate large numbers of samples of low energy states of quantum systems in very short times. In this talk I will explain how to use a multitude of discrete methods, for example applications of graph minors and graph isomorphisms, to improve the performance of quantum annealing. I will then show how to apply such improved quantum annealing to a range of discrete optimization and discrete sampling problems.
- KRYSTAL GUO, Université libre de Bruxelles
Average mixing matrix of quantum walks. [PDF]
A quantum walk is a quantum process on a graph and is a computational primitive for quantum computation. A quantum walk is governed by its transition matrix which is unitary; since this process does not converge to a stationary distribution, we study the average behaviour of the quantum walk. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. We will present this matrix as the matrix of transformation of the orthogonal projection onto the commutant algebra of the adjacency matrix, restricted to diagonal matrices. Using this formulation, we find bounds on its rank, in particular for trees, with all eigenvalues distinct.
There has been a considerable success in approaching questions about continuous-time quantum walks with tools in algebraic graph theory and we will discuss several recent works, based on joint work with Chris Godsil, Gabriel Coutinho, Harmony Zhan and John Sinkovic.
- ANNA LUBIW, University of Waterloo
Token Swapping on Trees [PDF]
Given a graph with vertices $v_1, v_2, \ldots, v_n$ and tokens $1, 2, \ldots, n$, one on each vertex, the token swapping problem is to get token $i$ to vertex $v_i$ for all $i$ using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.
Token swapping on a tree is not known to be in P nor NP-complete. We present some partial results:
- An optimum solution may need to swap a leaf that has the correct token, disproving a conjecture of Vaughan.
- The approximation factor of 2 is tight for some known 2-approximation algorithms.
- Weighted coloured token swapping is NP-complete on trees, but solvable in polynomial time on paths and stars.
Joint work with: Ahmad Biniaz, Kshitij Jain, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, Alexi Turcotte
- CHRISTOPHER MARTIN VAN BOMMEL, University of Waterloo
Quantum Walks, State Transfer, and Entanglement [PDF]
Quantum walks are the quantum analogues of classical random walks and can be used to model quantum computations. If a quantum walker starts at a vertex of a graph and after some length of time, has probability 1 of being found at a different vertex, we say there is perfect state transfer between the two vertices. If instead, there is a time for which the probability can be made arbitrarily close to 1, we say there is pretty good state transfer between the vertices. We consider the quantum walk model determined by the XY-Hamiltonian, which can be considered as based on the adjacency matrix of the graph and briefly review results for state transfer on paths between two vertices, before discussing how to extend these ideas to starting states involving multiple qubits.
- LILY WANG, University of Waterloo
The Combinatorics of Nearest and Furthest Smaller Values [PDF]
A classical problem asks us to find, for each element $A[i]$ of an array of integers, the position of the nearest smallest element. Similarly, we can ask about the dual problem: for each element of an array of integers $A[i]$, what is the position of the furthest smaller element? In our paper, we discussed both these problems from a combinatorial perspective and considered algorithms to solve them. By examining results of permutations of distinct integers and behaviour of the algorithms, we find many classical combinatorial sequences such as the Stirling numbers, the Catalan numbers, the Bell numbers, and the harmonic numbers.