The Day of Quantum Algorithms!


22 September 2020

Part of the Quantum Week of Fun


Due to the ongoing COVID-19 pandemic, and the uncertainty about travel and public gatherings, we have made the difficult decision to make QuAlg20 a virtual event.

Full details about the arrangements will appear here nearer the time.


About the workshop

The Quantum Algorithms workshop aims to bring together leading researchers working on a range of topics from fundamental questions on quantum algorithms to practical applications for near term quantum computing. A range of invited and contributed talks will highlight recent novel results in the field to motivate discussions on open questions and future directions on the computational reach of quantum algorithms.

The scope of the workshop includes, but is not limited to, current hot topics in the field:

  • Quantum algorithms for optimisation and machine learning
  • Quantum random walks, oracular and algebraic algorithms
  • Experimental implementations of algorithms on small-scale quantum computers
  • Quantum advantage proposals and explorations of quantum speed-ups
  • Limitations and computational power of hybrid quantum-classical algorithms
  • Circuit complexity
  • Protocols for characterisation and mitigation of errors in quantum devices
  • Verification and benchmarking of quantum computations

Invited Speakers

  • Aram Harrow, Center for Theoretical Physics, Massachusetts Institute of Technology
  • Laura Mančinska, QMATH, Department of Mathematical Sciences, University of Copenhagen

Full schedule available here !

Invited Talks

Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs, Laura Mančinska

Time: 10:00 (GMT + 1), 22nd of September

Where? Video at Youtube Link Q&A on Slack (link in video description)

Over 50 years ago, Lovasz proved that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph [Acta Math. Hungar. 18 (1967), pp. 321–328]. In this work we prove that two graphs are quantum isomorphic (in the commut- ing operator framework) if and only if they admit the same number of homomorphisms from any planar graph. As there exist pairs of non-isomorphic graphs that are quantum isomorphic, this implies that homomorphism counts from planar graphs do not deter- mine a graph up to isomorphism. Another immediate consequence is that determining whether there exists some planar graph that has a different number of homomorphisms to two given graphs is an undecidable problem, since quantum isomorphism is known to be undecidable. Our characterization of quantum isomorphism is proven via a combinatorial characterization of the intertwiner spaces of the quantum automorphism group of a graph based on counting homomorphisms from planar graphs. This result inspires the definition of graph categories which are analogous to, and a generalization of, partition categories that are the basis of the definition of easy quantum groups. Thus we introduce a new class of graph-theoretic quantum groups whose intertwiner spaces are spanned by maps associated to (bi-labeled) graphs. Finally, we use our result on quantum isomorphism to prove an interesting reformulation of the Four Color Theorem: that any planar graph is 4-colorable if and only if it has a homomorphism to a specific Cayley graph on the symmetric group S4 which contains a complete subgraph on four vertices but is not 4-colorable.

Small quantum computers and large classical data sets, Aram Harrow

Time: 14:30 (GMT + 1), 22nd of September

Where? Video at Youtube Link Q&A on Slack (link in video description)

We introduce hybrid classical-quantum algorithms for problems involving a large classical data set X and a space of models Y such that a quantum computer has superposition access to Y but not X. These algorithms use data reduction techniques to construct a weighted subset of X called a coreset that yields approximately the same loss for each model. The coreset can be constructed by the classical computer alone, or via an interactive protocol in which the outputs of the quantum computer are used to help decide which elements of X to use. By using the quantum computer to perform Grover search or rejection sampling, this yields quantum speedups for maximum likelihood estimation, Bayesian inference and saddle-point optimization. Concrete applications include k-means clustering, logistical regression, zero-sum games and boosting.

Contributed Talks

Accepted Papers for Poster Contributions

Important dates

7th of August AoE Submission of abstract
1st of September Notification of decisions
22 September 2020 Workshop

Instructions for authors

The format of the Quantum Algorithms day will include invited speakers and contributed talks. We welcome contributions from all branches of physics, mathematics, computer science that are relevant to the main topic of the workshop. The workshop has no formal proceedings. Authors are invited to submit an abstract or a paper, with no restrictions on the format.

New - Best Student Paper Award!

A submission is eligible for the prize if and only if the main author is a student at the time of the submission and this student will present the work as a talk or as a poster. The student will be rewarded with a 500 GPB prize.

Please submit your papers through EasyChair:


Registration will be handled through the Quantum Week of Fun.


Programme Committee

  • Cristina Cirstoiu, Cambridge Quantum Computing
  • Harry Buhrman, Centrum voor Wiskunde en Informatica (CWI) and University of Amsterdam
  • Anuj Dawar, University of Cambridge

The local organisers are listed here.


Please contact Catie Isham if you would like to sponsor this workshop or any of the other events in the Quantum Week of Fun.

Loading posts...
Sort Gallery