Foundations of Quantum Computational Advantage

21 talks

April 30, 2024 - May 03, 2024

C24020

Collection Type

Subject

Description

The workshop marks the halfway point of the similarly named (FoQaCiA, pronounced "focaccia") collaboration between researchers in Canada and Europe, funded as part of a flagship partnership between NSERC and Horizon Europe.

https://www.foqacia.org/

The goal of FoQaCiA is to develop new foundational approaches to shed light on the relative computational power of quantum devices and classical computers, helping to find the "line in the sand" separating tasks admitting a quantum speedup from those that are classically simulable.

The workshop will focus on the four central interrelated themes of the project:
1. Quantum contextuality, non-classicality, and quantum advantage
2. The complexity of classical simulation of quantum computation
3. The arithmetic of quantum circuits
4. The efficiency of fault-tolerant quantum computation

Our view is that the future success of quantum computing critically depends on advances at the most fundamental level, and that large-scale investments in quantum implementations will only pay off if they can draw on additional foundational insights and ideas

:: :: ::

Scientific Organizers:

Rui Soares Barbosa (INL - International Iberian Nanotechnology Laboratory)
Anne Broadbent (University of Ottawa)
Ernesto Galvão (INL - International Iberian Nanotechnology Laboratory)
Rob Spekkens (Perimeter Institute)
Jon Yard (Perimeter Institute)

:: :: ::

FoQaCiA is funded by:

Displaying 13 - 21 of 21

Emergence of noncontextuality under quantum darwinism

Barbara Amaral
Universidade de São Paulo
May 02, 2024

PIRSA:24050009
Quantum Information
Generalized contextuality as a necessary resource for universal quantum computation

David Schmid
Perimeter Institute for Theoretical Physics
May 02, 2024

PIRSA:24050010
Quantum Information
Contextuality, entanglement, magic: many qubits, many questions

Ravi Kunjwal
Aix-Marseille University
May 02, 2024

PIRSA:24050011
Quantum Information
Binary constraint systems and MIP*

William Slofstra
University of Waterloo
May 02, 2024

PIRSA:24050012
Quantum Information
Efficiently achieving fault-tolerant qudit quantum computation via gate teleportation

Nadish da Silva
Simon Fraser University (SFU)
May 02, 2024

PIRSA:24050013
Quantum Information
Probing the limits of classical computing with arbitrarily connected quantum circuits

Michael Foss-Feig
Quantinuum
May 02, 2024

PIRSA:24040094
Quantum Information
Quantum metrological limits in noisy environments

Sisi Zhou
Perimeter Institute for Theoretical Physics
May 03, 2024

PIRSA:24050015
Quantum Information
GOLD-PLATED SICS

Ingemar Bengtsson
University of Stockholm
May 03, 2024

PIRSA:24050016
Quantum Information
The how and why of translating between the circuit model and the one-way model of quantum computing

Miriam Backens
Université de Lorraine
May 03, 2024

PIRSA:24050004
Quantum Information

Emergence of noncontextuality under quantum darwinism

Barbara Amaral
Universidade de São Paulo
May 02, 2024

PIRSA:24050009
Quantum Information
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.
Generalized contextuality as a necessary resource for universal quantum computation

David Schmid
Perimeter Institute for Theoretical Physics
May 02, 2024

PIRSA:24050010
Quantum Information
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.
Contextuality, entanglement, magic: many qubits, many questions

Ravi Kunjwal
Aix-Marseille University
May 02, 2024

PIRSA:24050011
Quantum Information
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.
Binary constraint systems and MIP*

William Slofstra
University of Waterloo
May 02, 2024

PIRSA:24050012
Quantum Information
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).
Efficiently achieving fault-tolerant qudit quantum computation via gate teleportation

Nadish da Silva
Simon Fraser University (SFU)
May 02, 2024

PIRSA:24050013
Quantum Information
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.
Probing the limits of classical computing with arbitrarily connected quantum circuits

Michael Foss-Feig
Quantinuum
May 02, 2024

PIRSA:24040094
Quantum Information
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.
Quantum metrological limits in noisy environments

Sisi Zhou
Perimeter Institute for Theoretical Physics
May 03, 2024

PIRSA:24050015
Quantum Information
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.
GOLD-PLATED SICS

Ingemar Bengtsson
University of Stockholm
May 03, 2024

PIRSA:24050016
Quantum Information
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
The how and why of translating between the circuit model and the one-way model of quantum computing

Miriam Backens
Université de Lorraine
May 03, 2024

PIRSA:24050004
Quantum Information
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.

Title	Speaker(s)	Date	Talk Type	Info
Emergence of noncontextuality under quantum darwinism	Barbara Amaral	2024-05-02	Conference	View details
Generalized contextuality as a necessary resource for universal quantum computation	David Schmid	2024-05-02	Conference	View details
Contextuality, entanglement, magic: many qubits, many questions	Ravi Kunjwal	2024-05-02	Conference	View details
Binary constraint systems and MIP*	William Slofstra	2024-05-02	Conference	View details
Efficiently achieving fault-tolerant qudit quantum computation via gate teleportation	Nadish da Silva	2024-05-02	Conference	View details
Probing the limits of classical computing with arbitrarily connected quantum circuits	Michael Foss-Feig	2024-05-02	Conference	View details
Quantum metrological limits in noisy environments	Sisi Zhou	2024-05-03	Conference	View details
GOLD-PLATED SICS	Ingemar Bengtsson	2024-05-03	Conference	View details
The how and why of translating between the circuit model and the one-way model of quantum computing	Miriam Backens	2024-05-03	Conference	View details

Foundations of Quantum Computational Advantage

Format results