Name: Foundations of Quantum Computational Advantage
Start: 2024-04-30T08:00:00-04:00
End: 2024-05-03T17:00:00-04:00
Location: Perimeter Institute for Theoretical Physics

Foundations of Quantum Computational Advantage

from Tuesday, 30 April 2024 (08:00) to Friday, 3 May 2024 (17:00)

Tuesday, 30 April 2024

08:30 Registration
Registration
08:30 - 09:00

09:00 Opening Remarks
Opening Remarks
09:00 - 09:15
Room: PI/1-100 - Theatre
09:15 Values for compiled XOR nonlocal games - Connor Paddock (University of Ottawa)
Values for compiled XOR nonlocal games
- Connor Paddock (University of Ottawa)
09:15 - 10:00
Room: PI/1-100 - Theatre Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. However, the spatial separation between devices can be difficult to enforce in practice. To this end, Kalai et al. (STOC '23) initiated the study of compiled nonlocal games. The KLVY compilation procedure transforms any k-prover nonlocal into a game with a classical verifier and a single cryptographically limited quantum prover. Kalai et al. showed that their compilation procedure is sound against classical provers and complete for entangled provers. Natarajan and Zhang (FOCS '23) showed that the compiled two-prover CHSH game is sound against quantum provers. I will discuss recent work, showing that the compiler is sound for any two-player XOR game. I will also discuss challenges and open questions in extending results from nonlocal games to the compiled setting.
10:00 Reliable quantum computational advantages from quantum simulation - Juani Bermejo-Vega (Universidad de Granada)
Reliable quantum computational advantages from quantum simulation
- Juani Bermejo-Vega (Universidad de Granada)
10:00 - 10:45
Room: PI/1-100 - Theatre Demonstrating quantum advantages in near term quantum devices is a notoriously difficult task. Ongoing efforts try to overcome different limitations of quantum devices without fault-tolerance, such as their limited system size or obstacles towards verification of the outcome of the computation. Proposals that exhibit more reliable quantum advantages for classically hard-to-simulate verifiable problems lack, at the same time, practical applicability. In this talk we will review different approaches to demonstrate quantum advantages inspired from many-body quantum physics. The first of them use entangled quantum resources such as cluster states, which are useful to demonstrate verifiable quantum advantages based on sampling problems (Theory proposal Phys. Rev. X 8, 021010, 2018 and recent experimental demonstration arXiv preprint arXiv:2307.14424). The second probe measurement of many-body quantities such as dynamical structure factors in quantum simulation setups (Proceedings of the National Academy of Sciences 117 (42), 26123-26134).
10:45 Break
Break
10:45 - 11:15
Room: PI/1-124 - Lower Bistro
11:15 Cohomological description of contextual measurement-based quantum computations — the temporally ordered case - Robert Raussendorf (Leibniz University Hannover)
Cohomological description of contextual measurement-based quantum computations — the temporally ordered case
- Robert Raussendorf (Leibniz University Hannover)
11:15 - 12:00
Room: PI/1-100 - Theatre It is known that measurement-based quantum computations (MBQCs) which compute a non-linear Boolean function with sufficiently high probability of success are contextual, i.e., they cannot be described by a non-contextual hidden variable model. It is also known that contexuality has descriptions in terms of cohomology [1,2]. And so it seems in range to obtain a cohomological description of MBQC. And yet, the two connections mentioned above are not easily strung together. In a previous work [3], the cohomological description for MBQC was provided for the temporally flat case. Here we present the extension to the general temporally ordered case. [1] S. Abramsky, R. Barbosa, S. Mansfield, The Cohomology of Non-Locality and Contextuality, EPTCS 95, 2012, pp. 1-14 [2] C. Okay, S. Roberts, S.D. Bartlett, R. Raussendorf, Topological proofs of contextuality in quantum mechanics, Quant. Inf. Comp. 17, 1135-1166 (2017). [3] R. Raussendorf, Cohomological framework for contextual quantum computations, Quant. Inf. Comp. 19, 1141-1170 (2019) This is jount work with Polina Feldmann and Cihan Okay
12:00 Lunch
Lunch
12:00 - 13:00
Room: PI/2-251 - Upper Bistro
13:00 BosonSampling with a linear number of modes - Daniel Jost Brod (Universidade Federal Fluminense)
BosonSampling with a linear number of modes
- Daniel Jost Brod (Universidade Federal Fluminense)
13:00 - 13:45
Room: PI/1-100 - Theatre BosonSampling is one of the leading candidate models for a demonstration of quantum computational advantage. However, there are still important gaps between our best theoretical results and what can be implemented realistically in the laboratory. One of the largest gaps concerns the scaling between the number of modes (m) and number of photons (n) in the experiment. The original proposal by Aaronson and Arkhipov, as well as all subsequent improvements, required m to scale as n^2, whereas most state-of-the-art typically operate in a regime where m is linear in n. In this talk, I will describe how our recent work bridges this gap by providing evidence that BosonSampling remains hard even for m as low as 2n. I will review the template for proofs of computational advantage used in BosonSampling and other proposals, and discuss how we solved the new challenges that appear in this regime.
13:45 Gong Show
Gong Show
13:45 - 15:00
Room: PI/1-100 - Theatre IN PERSON - Lorenzo Catani, Matthew Fox, Hlér Kristjánsson, Gabrielle Tournaire VIRTUAL - Jonte Hance, Sidiney Montanhano, Shiroman Prakash, Amr Sabry

15:00 Break
Break
15:00 - 15:30
Room: PI/1-124 - Lower Bistro
15:30 Simulating 2D lattice gauge theories on a qudit quantum computer - Jinglei Zhang (University of Waterloo)
Simulating 2D lattice gauge theories on a qudit quantum computer
- Jinglei Zhang (University of Waterloo)
15:30 - 16:15
Room: PI/1-100 - Theatre Particle physics underpins our understanding of the world at a fundamental level by describing the interplay of matter and forces through gauge theories. Yet, despite their unmatched success, the intrinsic quantum mechanical nature of gauge theories makes important problem classes notoriously difficult to address with classical computational techniques. A promising way to overcome these roadblocks is offered by quantum computers, which are based on the same laws that make the classical computations so difficult. Here, we present a quantum computation of the properties of the basic building block of two-dimensional lattice quantum electrodynamics, involving both gauge fields and matter. This computation is made possible by the use of a trapped-ion qudit quantum processor, where quantum information is encoded in d different states per ion, rather than in two states as in qubits. Qudits are ideally suited for describing gauge fields, which are naturally high-dimensional, leading to a dramatic reduction in the quantum register size and circuit complexity. Using a variational quantum eigensolver we find the ground state of the model and observe the interplay between virtual pair creation and quantized magnetic field effects. The qudit approach further allows us to seamlessly observe the effect of different gauge field truncations by controlling the qudit dimension. Our results open the door for hardware-efficient quantum simulations with qudits in near-term quantum devices.
16:15 Free Time // Poster Session
Free Time // Poster Session
16:15 - 17:00
Room: PI/1-119 - Atrium

18:00 Banquet
Banquet
18:00 - 20:00
Room: PI/2-251 - Upper Bistro
Wednesday, 1 May 2024
10:00 Learning quantum objects - Amira Abbas (University of Amsterdam)
Learning quantum objects
- Amira Abbas (University of Amsterdam)
10:00 - 10:45
Room: PI/1-100 - Theatre Whilst tomography has dominated the theory behind reconstructing/approximating quantum objects, such as states or channels, conducting full tomography is often not necessary in practice. If one is interested in learning properties of a quantum system, side-stepping the exponential lower bounds of tomography is then possible. In this talk, we will introduce various learning models for approximating quantum objects, survey the literature of quantum learning theory and explore instances where learning can be fully time- and sample efficient.
10:45 Break
Break
10:45 - 11:15
Room: PI/1-124 - Lower Bistro
11:15 Programming Clifford Unitaries with Symplectic Types - Jennifer Paykin (Intel)
Programming Clifford Unitaries with Symplectic Types
- Jennifer Paykin (Intel)
11:15 - 12:00
Room: PI/1-100 - Theatre This talk will present work-in-progress towards a new programming methodology for Cliffords, where n-ary Clifford unitaries over qudits can be expressed as functions on compact Pauli. Inspired by the fact that projective Cliffords correspond to center-fixing automorphisms on the Pauli group, we develop a type system where well-typed expressions correspond to symplectic morphisms---that is, linear transformations that respect the symplectic form. This language is backed up by a robust categorical and operational semantics, and well-typed functions can be efficiently simulated and synthesized into circuits via Pauli tableaus.
12:00 Group Photo
Group Photo
12:00 - 12:05
Room: PI/1-119 - Atrium

12:05 Lunch
Lunch
12:05 - 13:00
Room: PI/2-251 - Upper Bistro
13:00 Unclonability and How it links quantum foundations to quantum applications - Mina Doosti (University of Edinburgh)
Unclonability and How it links quantum foundations to quantum applications
- Mina Doosti (University of Edinburgh)
13:00 - 13:45
Room: PI/1-100 - Theatre Quantum mechanics forbids the creation of ideal identical copies of unknown quantum systems and, as a result, copying quantum information. This fundamental and non-classical 'unclonability' feature of nature has played a central role in quantum cryptography, quantum communication and quantum computing ever since its discovery. However, unclonability is a broader concept than just the no-cloning theorem. In this talk, I will go over different notions of quantum unclonability and show how they link to many important questions and topics in quantum applications both in quantum machine learning and quantum cryptography. I will also broadly cover the link between unclonability and other fundamental concepts, such as randomness, pseudorandomness and contextuality.
13:45 Gong Show
Gong Show
13:45 - 15:00
Room: PI/1-100 - Theatre IN PERSON: Kim Vallée, Thomas Vinet VIRTUAL: Farid Shahandeh, Nitica Sakharwade, Shashank Virmani, Rafael Wagner, Roberto Dobal Baldijao

15:00 Break
Break
15:00 - 15:30
Room: PI/1-124 - Lower Bistro
15:30 Stabilizer operators and Barnes-Wall lattices - Vadym Kliuchnikov (Microsoft)
Stabilizer operators and Barnes-Wall lattices
- Vadym Kliuchnikov (Microsoft)
15:30 - 16:15
Room: PI/1-100 - Theatre We give a simple description of rectangular matrices that can be implemented by a post-selected stabilizer circuit. Given a matrix with entries in dyadic cyclotomic number fields $\mathbb{Q}(\exp(i\frac{2\pi}{2^m}))$, we show that it can be implemented by a post-selected stabilizer circuit if it has entries in $\mathbb{Z}[\exp(i\frac{2\pi}{2^m})]$ when expressed in a certain non-orthogonal basis. This basis is related to Barnes-Wall lattices. Our result is a generalization to a well-known connection between Clifford groups and Barnes-Wall lattices. We also show that minimal vectors of Barnes-Wall lattices are stabilizer states, which may be of independent interest. Finally, we provide a few examples of generalizations beyond standard Clifford groups. Joint work with Sebastian Schonnenbeck
Thursday, 2 May 2024
09:15 Emergence of noncontextuality under quantum darwinism - Barbara Amaral (University of São Paolo)
Emergence of noncontextuality under quantum darwinism
- Barbara Amaral (University of São Paolo)
09:15 - 10:00
Room: PI/1-100 - Theatre Quantum Darwinism proposes that the proliferation of redundant information plays a major role in the emergence of objectivity out of the quantum world. Is this kind of objectivity necessarily classical? We show that if one takes Spekkens’s notion of noncontextuality as the notion of classicality and the approach of Brandão, Piani, and Horodecki to quantum Darwinism, the answer to the above question is “‘yes,” if the environment encodes the proliferated information sufficiently well. Moreover, we propose a threshold on this encoding, above which one can unambiguously say that classical objectivity has emerged under quantum Darwinism.
10:00 Generalized contextuality as a necessary resource for universal quantum computation - David Schmid (University of Gdańsk)
Generalized contextuality as a necessary resource for universal quantum computation
- David Schmid (University of Gdańsk)
10:00 - 10:45
Room: PI/1-100 - Theatre A universal and well-motivated notion of classicality for an operational theory is explainability by a generalized-noncontextual ontological model. I will here explain what notion of classicality this implies within the framework of generalized probabilistic theories. I then prove that for any locally tomographic theory, every such classical model is given by a complete frame representation. Using this powerful constraint on the space of possible classical representations, I will then prove that the stabilizer subtheory has a unique classical representation—namely Gross's discrete Wigner function. This provides deep insights into the relevance of Gross's representation within quantum computation. It also implies that generalized contextuality is also a necessary resource for universal quantum computation in the state injection model.
10:45 Break
Break
10:45 - 11:15
Room: PI/1-124 - Lower Bistro
11:15 Contextuality, entanglement, magic: many qubits, many questions - Ravi Kunjwal (Aix-Marseille Université)
Contextuality, entanglement, magic: many qubits, many questions
- Ravi Kunjwal (Aix-Marseille Université)
11:15 - 12:00
Room: PI/1-100 - Theatre I will present some recent work on the interplay between contextuality, entanglement, and magic in multiqubit systems. Taking a foundational inquiry into entanglement in the Kochen-Specker theorem as our point of departure, I will proceed to outline some questions this raises about the role of these resources in models of multiqubit quantum computation. The purpose of this talk is to raise questions that can hopefully feed into the discussion sessions.
12:00 Lunch
Lunch
12:00 - 13:00
Room: PI/2-251 - Upper Bistro
13:00 Binary constraint systems and MIP* - William Slofstra (University of Waterloo)
Binary constraint systems and MIP*
- William Slofstra (University of Waterloo)
13:00 - 13:45
Room: PI/1-100 - Theatre Binary constraint system games are a generalization of the Mermin-Peres magic square game introduced by Cleve and Mittal. Thanks to the recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen, BCS games can be used to construct a proof system for any language in MIP*, the class of languages with a multiprover interactive proof system where the provers can share entanglement. This means that we can apply logical reductions for binary constraint systems to MIP* protocols, and also raises the question: how complicated do our constraint systems have to be to describe all of MIP*? In this talk, I'll give a general overview of this subject, including an application of logical reductions to showing that all languages in MIP* have a perfect zero knowledge proof system (joint work with Kieran Mastel), and one obstacle to expressing all of MIP* with linear constraints (joint work with Connor Paddock).
13:45 //
//
13:45 - 14:00
14:00 Colloquium - Combining Contextuality and Causality - Samson Abramsky (University College London)
Colloquium - Combining Contextuality and Causality
- Samson Abramsky (University College London)
14:00 - 15:00
Room: PI/1-100 - Theatre We describe an approach to combining contextuality with causality, which is general enough to cover causal background structure, adaptive measurement-based quantum computation, and causal networks. The key idea is to view contextuality as arising from a game played between Experimenter and Nature, allowing for causal dependencies in the actions of both the Experimenter (choice of measurements) and Nature (choice of outcomes). This is joint work with Rui Soares Barbosa and Amy Searle.
15:00 Break
Break
15:00 - 15:30
Room: PI/1-124 - Lower Bistro
15:30 Efficiently achieving fault-tolerant qudit quantum computation via gate teleportation - Nadish de Silva (Simon Fraser University)
Efficiently achieving fault-tolerant qudit quantum computation via gate teleportation
- Nadish de Silva (Simon Fraser University)
15:30 - 16:15
Room: PI/1-100 - Theatre Quantum computers operate by manipulating quantum systems that are particularly susceptible to noise. Classical redundancy-based error correction schemes cannot be applied as quantum data cannot be copied. These challenges can be overcome by using a variation of the quantum teleportation protocol to implement those operations which cannot be easily done fault-tolerantly. This process consumes expensive resources called 'magic states'. The vast quantity of these resources states required for achieving fault-tolerance is a significant bottleneck for experimental implementations of universal quantum computers. I will discuss a program of finding and classifying those quantum operations which can be performed with efficient use of magic state resources. I will focus on the understanding of not just qubits but also the higher-dimensional 'qudit' case. This is motivated by both practical reasons and for the resulting theoretical insights into the ultimate origin of quantum computational advantages. Research into these quantum operations has remained active from their discovery twenty-five years ago to the present. Our approach introduces the novel use of tools from algebraic geometry. The results in this talk will include joint work with Chen, Lautsch, and Bampounis-Barbosa.
16:15 Probing the limits of classical computing with arbitrarily connected quantum circuits - Michael Foss-Feig (Quantinuum)
Probing the limits of classical computing with arbitrarily connected quantum circuits
- Michael Foss-Feig (Quantinuum)
16:15 - 17:00
Room: PI/1-100 - Theatre Empirical evidence for a gap between the computational powers of classical and quantum computers has been provided by experiments that sample the output distribution of two-dimensional quantum circuits. Many attempts to close this gap have utilized classical simulations based on tensor network techniques, and their limitations shed light on the improvements to quantum hardware required to inhibit classical simulability. In particular, state of the art quantum computers having in excess of ~50 qubits are primarily vulnerable to classical simulation due to restrictions on their gate fidelity and their connectivity, the latter determining how many gates are required (and therefore how much infidelity is suffered) in generating highly-entangled states. Here, we describe numerical evidence for the difficulty of random circuit sampling in highly connected geometries.
Friday, 3 May 2024
09:15 Quantum metrological limits in noisy environments - Sisi Zhou (Perimeter Institute)
Quantum metrological limits in noisy environments
- Sisi Zhou (Perimeter Institute)
09:15 - 10:00
Room: PI/1-100 - Theatre The Heisenberg limit (HL) and the standard quantum limit (SQL) are two fundamental quantum metrological limits, which describe the scalings of estimation precision of an unknown parameter with respect to N, the number of one-parameter quantum channels applied. In the first part, we show the HL (1/N) is achievable using quantum error correction (QEC) strategies when the ``Hamiltonian-not-in-Kraus-span'' (HNKS) condition is satisfied; and when HNKS is violated, the SQL (1/N^1/2) is optimal and can be achieved with repeated measurements. In the second part, we identify modified metrological limits for estimating one-parameter qubit channels in settings of restricted controls where QEC cannot be performed. We prove unattainability of the HL and further show a ``rotation-generators-not-in-Kraus-span'' (RGNKS) condition that determines the achievability of the SQL.
10:00 GOLD-PLATED SICS - Ingemar Bengtsson (University of Stockholm)
GOLD-PLATED SICS
- Ingemar Bengtsson (University of Stockholm)
10:00 - 10:45
Room: PI/1-100 - Theatre There are well established conjectures about the symmetries of SIC-POVMs, and the number fields needed to construct them. If the dimension is of the form n^2 + 3 there is also an algorithm that allows us to calculate them, making use of Stark units in a subfield of the full number field. The algorithm works in the 72 dimensions where it has been tested. Joint work with (among others) Markus Grassl and Gary McConnell
10:45 Break
Break
10:45 - 11:15
Room: PI/1-124 - Lower Bistro
11:15 The how and why of translating between the circuit model and the one-way model of quantum computing - Miriam Backens (INRIA)
The how and why of translating between the circuit model and the one-way model of quantum computing
- Miriam Backens (INRIA)
11:15 - 12:00
Room: PI/1-100 - Theatre In the one-way model of measurement based quantum computing, unlike the quantum circuit model, a computation is driven not by unitary gates but by successive adaptive single-qubit measurements on an entangled resource state. So-called flow properties ensure that a one-way computation, described by a measurement pattern, is deterministic overall (up to Pauli corrections on output qubits). Translations between quantum circuits and measurement patterns have been used to show universality of the one-way model, verify measurement patterns, optimise quantum circuits, and more. Yet while it is straightforward to translate a circuit into a measurement pattern, the question of algorithmic "circuit extraction" -- how to translate general measurement patterns with flow to ancilla-free circuits -- had long remained open for all but the simplest type of flow. In this talk, we will recap the one-way model of quantum computing and then explain how the problem of circuit extraction was resolved using the ZX-calculus as a common language for circuits and measurement patterns. We also discuss applications.
12:00 Closing Remarks
Closing Remarks
12:00 - 12:15
Room: PI/1-100 - Theatre

12:15 Lunch
Lunch
12:15 - 13:15
Room: PI/2-251 - Upper Bistro

13:15 Free Discussion
Free Discussion
13:15 - 17:00