email   Subscribe to the mailing list    calendar   Subscribe to iCalendar    zoom   Watch on Zoom

The seminar takes place on Tuesdays from 15:00 to 16:00 CET. It is located at LaBRI, either on ground floor (rooms 073, 076, amphi) or first floor (room 178). The talks are usually in english and broadcasted on Zoom.


Upcoming talks

14th May 2024 at 15:00 (Room 178)
Clémence Chevignard (INRIA Rennes) Reducing the Number of Qubits in Quantum Factoring

Based on https://eprint.iacr.org/2024/222

28th May 2024 at 15:00 (Room 178)
Enrique Rico Ortega (Bilbao, University of the Basque Country UPV/EHU) TBA

4th June 2024 at 15:00 (Room 178)
Laurent Miclo (Toulouse School of Economics, CNRS) Quantum walks, the discrete wave equation and Chebyshev polynomials

Based on https://arxiv.org/abs/2402.07809.

18th June 2024 at 15:00 (Room 076)
Soumik Ghosh (U. of Chicago) Quantum Pseudoentanglement


Past talks

2024

30th April 2024
Sébastien Labbé (LaBRI) Reading group on “The Penrose Tiling is a Quantum Error-Correcting Code”

Based on https://arxiv.org/abs/2311.13040.

30th April 2024
Gerard Munné (Jagiellonian University Kraków) Semidefinite programming bounds for quantum codes

The fundamental problem in coding theory is to determine the maximum size of an error-correcting code of given distance and block length. Here we approach this question by providing a semidefinite programming hierarchy to determine the existence of quantum codes with given parameters. The hierarchy is complete in the sense that every set of parameters for which no code exists is detected at some level of the hierarchy.

17th April 2024
Felix Huber (LaBRI) Quantum problems on graphs

Demi-journée scientifique du département Combalgo suivie d’un buffet dans l’atrium. 09h00-09h10 Cyril Gavoille (chef du département) Combalgo en 3 mots 09h10-09h55 Clara Marcille (équipe Graphe et Optimisation) From antimagic to equitable labellings 09h55-10h40 Felix Huber (équipe Quantique) Quantum problems on graphs 10h40-11h00 pause café-thé-gateauxw 11h00-11h45 Sébastien Bouchard (équipe Algorithmique Distribuée) Distributed Systems of Mobile Agents and Verification 11h45-12h30 Sébastien Labbé (équipe Combinatoire et Applications) Pavages apériodiques et expérimentations dans l’environnement SageMath 12h30-14h00 buffet dans l’atrium

16th April 2024
Albert Rico (Jagiellonian University Kraków) Entanglement detection with trace polynomials

We provide a systematic method for nonlinear entanglement detection based on trace polynomial inequalities. In particular, this allows us to employ multipartite witnesses for the detection of bipartite states, and vice versa. We identify pairs of entangled states and witnesses for which linear detection fails, but for which nonlinear detection succeeds. With the trace polynomial formulation a great variety of witnesses arise from immanant inequalities, which can be implemented in the laboratory through the randomized measurements toolbox.

16th April 2024
Soffía Árnadóttir (Technical University of Denmark) Quantum isomorphisms on Cayley graphs

In this talk, I will introduce quantum isomorphisms through the isomorphism game. I will then define group-invariant quantum Latin squares and their connection to quantum isomorphisms. We will see some representation theory and finally, I will introduce a method of constructing Cayley graphs that are quantum isomorphic.

9th April 2024
Lev-Arcady Sellem (Mines Paris) Quantum reservoir engineering for the protection of Gottesman-Kitaev-Preskill qubits

At first sight, dissipative processes are the source of quantum decoherence and limit the timescale over which a given system can be controlled. On the other hand, from a control point of view, the availability of dissipative processes also opens new avenues, in particular regarding the stabilization of quantum systems. This strategy, known as quantum reservoir engineering, can be traced back to the seminal work of Alfred Kastler on optical pumping. In this talk, we present how to exploit reservoir engineering to stabilize and control Gottesman-Kitaev-Preskill (GKP) qubits - a bosonic encoding exploiting exotic states of light or matter to reduce the hardware cost of quantum error correction. We propose a novel approach relying on nonlinear modular interactions with a dissipative auxiliary system to autonomously stabilize the GKP code. This approach robustly suppresses local noise processes; unlike previous proposals, it also suppresses the propagation of noise from the auxiliary system used for dissipation engineering itself. In a state-of-the-art experimental setup based on superconducting circuits, we estimate that the encoded qubit lifetime could extend several orders of magnitude beyond break-even.

2nd April 2024
Yanlin Chen (CWI, U. of Amsterdam) A quantum speed-up for approximating the top eigenvectors of a matrix


Finding a good approximation of the top eigenvector of a given d × d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity d^{1.5+o(1)} and one with time complexity \tilde{O}(d^{1.75}) that has a slightly better dependence on the precision of the approximation. Both provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω(d^2) queries to entries of A (and hence Ω(d^2) time). We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd^{1.5+o(1)}. We also prove a nearly-optimal lower bound of \tilde{Ω}(d^{1.5}) on the quantum query complexity of approximating the top eigenvector. Our quantum algorithms run a version of the classical power method that is robust to certain benign kinds of errors, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer, in different ways for the two algorithms.
  Our first algorithm used block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography algorithm that has essentially optimal sample complexity O(d log(d)/ε^2) and that comes with improved statistical properties compared to earlier pure-state tomography algorithms. Our second algorithm estimated the matrix-vector product one entry at a time, using a new “Gaussian phase estimation” procedure. We also develop a time-efficient process- tomography algorithm for reflections around bounded-rank subspaces, providing the basis for our top-eigensubspace estimation application.   This is the joint work with Ronald de Wolf and András Gilyén.  

26th March 2024
Maxime Cautrès (LIG) Vertex-minor universal graphs for generating entangled quantum subsystems

We study the notion of k-stabilizer universal quantum state, that is, an n-qubit quantum state, such that it is possible to induce any stabilizer state on any k qubits, by using only local operations and classical communications. These states generalize the notion of k-pairable states introduced by Bravyi et al., and can be studied from a combinatorial perspective using graph states and k-vertex-minor universal graphs. First, we demonstrate the existence of k-stabilizer universal graph states that are optimal in size with n=Θ(k2) qubits. We also provide parameters for which a random graph state on Θ(k2) qubits is k-stabilizer universal with high probability. Our second contribution consists of two explicit constructions of k-stabilizer universal graph states on n=O(k4) qubits. Both rely upon the incidence graph of the projective plane over a finite field 𝔽q. This provides a major improvement over the previously known explicit construction of k-pairable graph states with n=O(23k), bringing forth a new and potentially powerful family of multipartite quantum resources. Based on https://arxiv.org/abs/2402.06260.

5th March 2024
Clément Maria (Inria d’Université Côte d’Azur) A topological perspective on “quantumness”

In this talk, I will give an overview of the algorithmic aspects of quantum topology, a field of mathematics studying the topology of low-dimensional objects (knots, 3-manifolds) with algebraic tools originally designed for quantum physics. On the algorithmic side, early results show that the computation of the so called quantum topological invariants reveals rich dichotomy properties in parameterized complexity, randomized approximation, and quantum computing. I will present some results in the field and highlight how the diversity of tools offered by low dimensional topology has promising applications in standard quantum computing.

20th February 2024
Video session (N/A) New directions in quantum state learning and testing (Ryan O’Donnell)

We will be watching and commenting the video https://www.youtube.com/watch?v=MnxQ3oqTWgQ by Ryan O’Donnell.

13th February 2024
Idris Delsol (Télécom Paris) An information theoretic condition for perfect reconstruction

A new information theoretic condition is presented for reconstructing a discrete random variable X based on the knowledge of a set of discrete functions of X. The reconstruction condition is derived from Shannon’s 1953 lattice theory with two entropic metrics of Shannon and Rajski. Because such a theoretical material is relatively unknown and appears quite dispersed in different references, we first provide a synthetic description (with complete proofs) of its concepts, such as total, common and complementary informations. Definitions and properties of the two entropic metrics are also fully detailed and shown compatible with the lattice structure. A new geometric interpretation of such a lattice structure is then investigated that leads to a necessary (and sometimes sufficient) condition for reconstructing the discrete random variable X given a set {X1,…,Xn} of elements in the lattice generated by X. Finally, this condition is illustrated in five specific examples of perfect reconstruction problems: reconstruction of a symmetric random variable from the knowledge of its sign and absolute value, reconstruction of a word from a set of linear combinations, reconstruction of an integer from its prime signature (fundamental theorem of arithmetic) and from its remainders modulo a set of coprime integers (Chinese remainder theorem), and reconstruction of the sorting permutation of a list from a minimal set of pairwise comparisons.

26th January 2024
Workshop ANR QuDATA (Day 3) Program

9h00 - Yassine Hamoudi (LaBRI, CNRS Bordeaux) The NISQ Complexity of Collision Finding 10h00 - Maël Luce (IRIF, Univ. Paris-Cité) Distributed Grover Algorithm 11h00 - Simon Apers (IRIF, CNRS Paris) Quantum speedups for linear programming via interior point methods

25th January 2024
Workshop ANR QuDATA (Day 2) Program

9h00 - Félix Huber (LaBRI, Univ. Bordeaux) Semidefinite programming bounds for quantum codes 10h00 - Wouter Rozendaal (IMB, Univ. Bordeaux) A Renormalisation Decoder for Kitaev’s Toric Code 11h00 - Jens Siewert (UPV/EHU, Leioa - Spain) Correlation constraints and the Bloch geometry of two-party systems 14h00 - Simon Martiel (IBM Quantum, Paris) Shallower CNOT circuits on realistic quantum hardware 15h00 - Arthur Braida (ATOS & Univ. Orléans) Tight Lieb-Robinson bound for approximation ratio in Quantum Annealing 16h00 - Ion Nechita (CNRS Toulouse) Monogamy of highly symmetric states

24th January 2024
Workshop ANR QuDATA (Day 1) Program

14h00 - Yixin Shen (INRIA Rennes) Finding many Collisions via Reusable Quantum Walks 15h00 - Stéphane Dartois (CEA LIST, Univ. Paris-Saclay) Geometric multipartite entanglement and injective norm of uniform quantum states 16h00 - Leonardo Novo (INL Braga - Portugal) Quantum search and optimization with continuous-time quantum walks

9th January 2024
Grégory Brivady (Télécom Paris) Calcul quantique de la Maximum Mean Discrepancy de Distribution de Probabilités avec un noyau Gaussien

La Maximum Mean Discrepancy (MMD) permet de mesurer la distance entre distributions de probabilités. Son calcul est réalisé à l’aide des Kernel Mean Embedding, qui consistent à représenter les distributions dans des espaces de dimensions supérieur muni d’un produit scalaire, puis de calculer la distance dans cet espace [1]. Le swap-test [2] est une technique permettant d’estimer des produits scalaires avec un ordinateur quantique. En définissant la Quantum Mean Embedding (QME), le swap-test permet de rendre la complexité de calcul d’une estimation de la MMD indépendante du nombre d’échantillons [3], contrairement au cas classique où O(N²) calculs sont nécessaires pour N échantillons. Si la QME peut être préparée avec une complexité linéaire en le nombre d’échantillons, il est alors possible de réaliser un gain de complexité [3]. Je présenterai une implémentation du noyau Gaussien en terme de QME, qui pourrait permettre un tel gain. Ref: [1] K. Muandet, K. Fukumizu, B. Sriperumbudur, B. Schölkopf, Kernel Mean Embedding: A Review and Beyond (2017) [2] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Phys. Rev. Lett. 87, 167902 (2001) [3] J. M. Müler, K. Muandet, B. Schölkopf, Phys. Rev. Research 1, 033159 (2019)

2023

19th December 2023
Yassine Hamoudi (LaBRI) Quantum algorithms for solving zero-sum games

I will explain how quantum algorithms can compute the Nash equilibrium of zero-sum games more efficiently compared to classical algorithms. In particular, I will describe a quantum state preparation technique for sampling from any discrete probability distribution. The talk will highlight some common features and limitations in current quantum algorithms for solving optimization problems with rigorous guarantees.

11th December 2023
Nicolas Lorente (CFM – Materials Physics Center) Autour du futur ordinateur à 127 qubit au pays basque

À San Sébastien, le département d’éducation du gouvernment du Pays Basque a fait l’acquisition auprès d’IBM d’un ordinateur quantique à 127 qubits. Dans ce second exposé seront présentées une partie des activités scientifiques à l’université de San Sébastien en lien avec cet investissement.

11th December 2023
Nicolas Lorente (CFM – Materials Physics Center) Electron spin resonance with the scanning tunneling microscope: theory and design of simple quantum circuits on few-atom structures

A scanning tunnelling microscope (STM) can drive the spin evolution of a single atom, molecule or nanostructure on a solid surface [1]. A tunnelling electron current is localized on a single atom, while the bias is modulated at microwave frequencies. The measured current shows excitations attributed to a spin resonance (ESR). We have developed software to simulate virtually any instance of ESR-STM under realistic conditions of temperature, external fields, and conductance [2-5]. Here, we suggest the realization of the usual quantum circuit made up of one Hadamard and one CNOT gate that converts a product state to a Bell state. Quantum circuit is simulated with the interaction of two Ti atoms on an MgO substrate driven by a scanning tunneling microscope. The first step of the sequence (a Hadamard gate) is implemented to act on the first spin. The evolution onto the final state demonstrates the realization of the Hadamard gate, plus current-induced decoherence if a longer evolution time is used. To characterize our gate, we evaluate its fidelity on the desired Bell state. This allows us to discuss the performance of the simulated gate using tunnelling currents and solid state-hosted spins. References: [1] K. Yang et al. Science 366, 509 (2019) [2] J. reina-Gálvez et al PRB 100, 035411 (2019) [3] J Reina-Gálvez, Lorente, Delgado, Arrachea Phys. Rev. B 104, 245415 (2021) [4] J Reina-Gálvez, Wolf, Lorente Phys. Rev. B 107, 235404 (2023) [5] https://github.com/qphensurf

5th December 2023
Razvan Barbulescu (IMB) Reading group on “An Efficient Quantum Factoring Algorithm” (Oded Regev)

This algorithm is an improvement of Shor’s algorithm for factorization. Although the number of qubits is the same, O(n), the number of gates is reduced from O(n^2) to O(n^(3/2)).

28th November 2023
Sebastian Zur (CWI, U. of Amsterdam) Multidimensional Electrical Networks

Recently, Apers and Piddock [TQC ‘23] strengthened the natural connection between quantum walks and electrical networks by considering Kirchhoff’s Law and Ohm’s Law. In this talk, I will discuss the multidimensional electrical network by defining Kirchhoff’s Alternative Law and Ohm’s Alternative Law based on the novel multidimensional quantum walk framework by Jeffery and Zur [STOC ‘23]. This multidimensional electrical network allows one to sample from the electrical flow obtained via a multidimensional quantum walk algorithm and achieve exponential quantum-classical separations for certain graph problems. In analogy to the connection between the (edge-vertex) incidence matrix of a graph and Kirchhoff’s Law and Ohm’s Law in an electrical network, we also rebuild the connection between the alternative incidence matrix and Kirchhoff’s Alternative Law and Ohm’s Alternative Law.

21st November 2023
Yvan Le Borgne (LaBRI) Reading group on “High-threshold and low-overhead fault-tolerant quantum memory” (IBM Quantum)

Compte-rendu de lecture de arxiv:2308.07915 par Bravyi, Cross, Gambetta, Maslov, Rall et Yoder.

17th October 2023
Razvan Barbulescu (IMB) Presentation of the HQI Project (France 2030, led by J.-C. Lafoucrière (CEA))

Dans cet exposé, nous utilisons la présentation du projet Hybrid Quantum initiative pour faire un panorama de la recherche sur l’informatique quantique. Cela consiste en construction d’ordinateurs, correction des erreurs, optimisation, simulation, cryptanalyse etc.

26th September 2023
Yvan Le Borgne (LaBRI) Reading group on “Discrete bulk reconstruction” (Aaronson,Pollack)

Rentrée et compte-rendu de lecture de “ Discrete Bulk Reconstruction” de Aaronson et Pollack.

Older events