The Day of Quantum Algorithms!

QuAlg20

22 September 2020

Part of the Quantum Week of Fun

 

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)

Abstract

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)

Abstract

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

• Quantum Algorithm for Simulating Hamiltonian Dynamics with an Off-diagonal Series Expansion, Itay Hen and Amir Kalev
• Quantum statistical query learning, Srinivasan Arunachalam, Alex Bredariol Grilo and Henry Yuen
• Characterising quantum correlations of fixed dimension, Hyejung Hailey Jee, Carlo Sparaciari, Omar Fawzi and Mario Berta
• Quantum algorithm for Petz recovery channels and pretty good measurements, Andras Gilyen, Seth Lloyd, Iman Marvian, Yihui Quek and Mark Wilde
• Variational Quantum State Eigensolver, Marco Vinicio Sebastian de la Roca, Kunal Sharma, Andrew Arrasmith and Patrick Coles
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms, Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio and Patrick Coles
• How to Teach AI to Play Bell Non-Local Games: Reinforcement Learning , Kishor Bharti, Tobias Haug, Vlatko Vedral and Leong Chuan Kwek
• Faster quantum polar decomposition, Procrustes and pretty-good measurements, Yihui Quek and Patrick Rebentrost
• Fast simulation of planar Clifford circuits, David Gosset, Daniel Grier, Alex Kerzner and Luke Schaeffer
• Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer, Cinthia Huerta Alderete, Shivani Singh, Nhung H. Nguyen, Daiwei Zhu, Radhakrishnan Balu, Christopher Monroe, C. M. Chandrashekar and Norbert M. Linke

Accepted Papers for Poster Contributions

• Thermodynamic fragments in magic state theories, Nikolaos Koukoulekidis and David Jennings
• An Adaptive Quantum Approximate Optimization Algorithm for Solving Combinatorial Problems on a Quantum Computer, Linghua Zhu, Ho Lun Tang, George Barron, Nicholas Mayhall, Edwin Barnes and Sophia Economou
• Characterization of QUBO reformulations for the maximum k-colorable subgraph problem, Luis Zuluaga, Rodolfo Quintero, David Bernal and Tamás Terlaky
• Quantum Ensemble for Classification, Antonio Macaluso, Luca Clissa, Stefano Lodi and Claudio Sartori
• Machine learning of noise-resilient quantum circuits, Lukasz Cincio, Kenneth Rudinger, Mohan Sarovar and Patrick Coles
• On the families of combinatorial and rotational quantum abstract detecting systems, J. Miguel Hernández Cáceres, Elias F. Combarro, José Ranilla and Ignacio F. Rúa
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets, Kunal Sharma, Marco Cerezo, Zoe Holmes, Lukasz Cincio, Andrew Sornborger and Patrick Coles
• Trainability of Quantum Neural Networks, Marco Cerezo, Kunal Sharma, Akira Sone, Tyler Volkoff, Lukasz Cincio and Patrick Coles
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time, Andrew Sornborger, Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick Coles, Benjamin Commeau, Joseph Gibbs and Kaitlin Gili
• A Quantum Interior Point Method for Semidefinite Optimization Problems, Brandon Augustino, Giacomo Nannicini, Tamás Terlaky and Luis Zuluaga
• Amplitude Estimation Without Phase Estimation with Approximate Oracles, Steven Herbert
• Decoding binary codes with the Quantum Approximate Optimization Algorithm,Markel Epelde, Ignacio F. Rúa and Elías F. Combarro
• Error mitigation with Clifford quantum-circuit data, Piotr Czarnik, Andrew Arrasmith, Patrick Coles and Lukasz Cincio
• Simultaneous Indirect Measurement of a Group of Pauli StringOperators with Minimal Overhead Ancilla Qubits, Sabine Pelton and Pejman Jouzdani
• Scattering in the Ising Model Using Quantum Lanczos Algorithm , Kubra Yeter Aydeniz, George Siopsis and Raphael Pooser
• Operator Sampling and Shot-frugal Optimization for Variational Algorithms ,Andrew Arrasmith, Lukasz Cincio, Rolando Somma, Patrick Coles and Jonas Kubler
• A quantum while loop for amplitude amplification, Pablo Andres-Martinez and Chris Heunen

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.

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: https://easychair.org/conferences/?conf=qualg20

Registration

Registration will be handled through the Quantum Week of Fun.

Organisers

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.

Sponsorship

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