GT Informatique Quantique à venir
16/02/2024: Cette page n'est plus à jour, voir le site web de l'équipe. Elle a vocation à devenir une archive témoignant des efforts pour la création de cette équipe. Visiteur, tu es incité à aller à la nouvelle page du séminaire.
Le GT Informatique Quantique a lieu le mardi de 15h à 16h. Il est organisé par Yvan Le Borgne.
Pour recevoir les informations par e-mail, abonnez-vous à la liste de diffusion.
Les enregistrements des exposés sont disponibles en divers endroits. La page suivante, protégée par un login et un mot de passe disponible auprès des organisateurs recense toutes les videos: https://www.labri.fr/perso/borgne/GtInfoQuantique Les extérieurs peuvent contacter par courriel les organisateurs.
20 février 2024 Séance vidéo
(visionnage avec commentaires de la salle d'un exposé enregistré)
5 Mars 2024 Clément Maria
12 Mars 2024 Sébastien Labbé
26 Mars 2024 Maxime Cautrès
2 April 2024 Yanlin Chen
9 April 2024 Lev-Arcady Sellem
16 April 2024 Albert Rico, Jagiellonian University Kraków
30 April 2024 Gerard Munné, Jagiellonian University Kraków
28 May 2024 Enrique Rico, Bilbao
2024 Siddhartha Patra
GT passés
13 Février 2024 Idris Delsol, Paris Télécom
24-26 Janvier 2024 QuDATA Workshop
9 Janvier 2024 Grégory Brivady 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)
19 Décembre 2023 Yassine Hamoudi 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.
Lundi 11 Décembre 2023 à 14h et 15h15 Nicolas Lorente Deux exposés
Exposé de 14h: 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
Exposé de 15h: Autour du futur ordinateur à 127 qubit au pays basque
Résumé: À 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.
5 Décembre 2023 Razvan Barbulescu An Efficient Quantum Factoring Algorithm (Oded Regev, août 2023)
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)).
28 Novembre 2023 Sebastian Zur 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.
21 novembre 2023 Yvan Le Borgne Lecture de "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.
17 Octobre 2023 Razvan Barbulescu Le projet HQI (France 2030, piloté par 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.
26 Septembre 2023 Yvan Le Borgne Discrete bulk reconstruction (Aaronson,Pollack)
Compte-rendu de lecture de arXiv:2210.15601.
27 juin 2023 Nathan Moumique et Shrinidhi Teganahally Sridhara
Exposés de deux stagiaires en informatique quantique (L3 Physique et M1 informatique).
30 Mai 2023 Denis Rochette Universal asymmetric quantum cloning
In this talk, we present the concept of universal asymmetric quantum cloning, which allows the cloning of quantum states up to a certain precision. We study the set of achievable precision and provide a complete description for any dimension and any number of copies. Using representation theory techniques, we construct the corresponding quantum cloners. Surprisingly, our results show that the previous quadratic relations capture only a subset of the achievable precision set.
16 Mai 2023 Kostia Chardonnet The Many-Worlds Calculus: Representing Quantum Control.
We explore the interaction between two monoidal structures: a multiplicative one, for the encoding of pairing, and an additive one, for the encoding of choice. We propose a PROP to model computation in this framework, where the choice is parametrized by an algebraic side effect: the model can support regular tests, probabilistic and non-deterministic branching, as well as quantum branching, i.e. superposition. The graphical language comes equipped with a denotational semantics based on linear applications, and an equational theory. We prove the language to be universal, and the equational theory to be complete with respect to the semantics.
9 Mai 2023 Felix Huber Refuting spectral compatibility of quantum marginals
The spectral variant of the quantum marginal problem asks: Given prescribed spectra for a set of quantum marginals, does there exist a compatible joint state? The main idea of this work is a symmetry- reduced semidefinite programming hierarchy for detecting incompatible spectra. The hierarchy is complete, in the sense that it detects every incompatible set of spectra. The refutations it provides are dimension- free, certifying incompatibility in all local dimensions. The hierarchy equally applies to the sums of Hermitian matrices problem, to optimize trace polynomials on the positive cone, to the compatibility of invariants, and to certify vanishing Kronecker coefficients. [NDLR: Joint work with Nikolai Wyderka]
2 Mai 2023 Léo Colisson Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States Without Structure
Oblivious Transfer (OT) is an extremely powerful cryptographic primitive, as it was shown to be sufficient to perform multi-party computing. We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions...) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt.
In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and k-out-of-n OT.
At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing (too much) information on it, even in a non-interactive way and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstatesQIP and ZKstatesQMA.
(Jeudi) 27 Avril 2023 Daniele Oriti Quantum information structure of spacetime: tensor network tools, entanglement and holographic properties in quantum gravity states
Quantum information concepts and tools play an important and natural role in quantum gravity models based on spin network states. In particular, random tensor network techniques have found several interesting applications, recently, in the study of their entanglement properties and in identifying conditions for holographic behaviour. The talk will survey such exciting developments and other indications that quantum information could be the appropriate language for reconstructing geometry and spacetime from more fundamental quantum constituents.
25 Avril 2023 Mizanur Rahaman Accumulation of entropy in general quantum systems
The Asymptotic Equipartition Property (AEP) establishes the Shannon entropy as the relevant quantity for various problems involving independent and identically distributed (i.i.d.) random variables. In the quantum setting, the von Neumann entropy plays a similar role for i.i.d quantum states. In this talk, we will discuss how this fundamental property holds in quantum systems modelled by abstract algebras, thereby establishing this property in systems beyond finite dimensions. We also discuss a generalization of this property, which is known as Entropy Accumulation in this general framework.
This is a joint work with Li Gao and Omar Fawzi
11 Avril 2023 Marc-Olivier Renou Any Physical Theory of Nature Must Be Boundlessly Multipartite Nonlocal
[Note: no quantum background is needed to attend this talk]
Quantum correlations are obtained when multiple parties perform independent measurements on a shared quantum state. I will first do a pedestrian introduction to Bell’s seminal theorem (acknowledge by the last Physics Nobel price), which proves that some quantum correlations cannot be explain by any ‘Local Hidden Variable theory’: one cannot understand quantum correlations based on shared randomness. But what about alternative explanations for quantum correlations? For instance, what happens if we try to explain quantum theory with shared randomness and ‘exotic bipartite resources’ (generalising quantum bipartite entanglement)? With Xavier Coiteux-Roy and Elie Wolfe, we found that no such exotic theory can account for all quantum correlations as long as it satisfies ‘causality’, thus generalizing Bell's theorem. In this talk, I will explain that result, which certifies the fact that ‘No Bipartite-Nonlocal Causal Theory Can Explain Nature's Quantum Correlations’. I will also discuss the connections of this problem with distributed computing (e.g., arXiv:2212.02768): our proof is based on the inflation technic in which we assume the replicability of resources, showing that a concept commonly used in distributed computing is also of great interest in theoretical physics.
Based on arXiv:2105.09381, arXiv:2105.09380, arXiv:2201.12754
4 Avril 2023 - Yvan Le Borgne Retours de QIP 2023 Part 3 https://indico.cern.ch/event/1175020/
28 Mars 2023 - Yvan Le Borgne Retours de QIP 2023 Part 2 https://indico.cern.ch/event/1175020/
21 Mars 2023 - Yvan Le Borgne Retours de QIP 2023 Part I https://indico.cern.ch/event/1175020/
14 Mars 2023 - Adrian Tanasa On S. Aaronson's blog post "On black holes, holography, the Quantum Extended Church-Turing Thesis, fully homomorphic encryption, and brain uploading"
21 Février 2023 Attention exceptionnellement à 14h30 puis 16h Leonardo Novo (14h30) puis Adèle Hilico (16h)
Leonardo Novo Quantum search and optimization using quantum walks
Quantum walks, the quantum analogue of classical random walks, became an important framework for the development of quantum algorithms. In the first part of this talk I will review how continuous-time quantum walks, which evolve in time according to the Schrödinger equation, can be used to tackle search problems on graphs faster than their classical counterparts. In the second part of the talk I will mention some approaches to use continuous-time quantum walks for solving optimization problems as well as some open questions about their performance.
Adèle Hilico Introduction to neutral atom based Quantum Processor Unit hardware and laser requirements.
Mardi 24 janvier - Simon Martiel Calcul Quantique et HPC (commun avec GT SATANAS)
Après une rapide présentation des activités R&D d’Atos sur le calcul quantique, nous développerons deux sujets à la frontière en calcul hautes performances et calcul quantique. Nous présenterons les récents efforts pour la définition d’un framework basé sur C++ pour l’intégration de kernel quantiques au sein d’un flot de calcul classique. Nous survolerons ensuite certaines problématiques liées à la définition de kernels quantiques pour l’algèbre linéaire. Dans un second temps, nous aborderons le sujet de la simulation de processeurs quantiques via un système HPC classique. Nous présenterons le problème de la contraction de réseaux de tenseurs, ses liens avec le calcul hautes performances, ainsi que des résultats récents basés sur des techniques de méthodes formelles quantiques.
17 Janvier 2023 -Yvan Le Borgne Répétition de "Quantum computing now not under the law of large numbers ?"
Discussions autour de la présentation de nos activités à la réunion Quantum Matter Bordeaux 2023. https://qmbx23.sciencesconf.org/
10 Janvier 2023 -Maxime Cautrès Complexity of recognizing Dyck languages of bounded height with quantum query algorithms.
L'exposé se concentrera sur l'étude de la complexité quantique en requête (Quantum Query Complexity) de la reconnaissance des mots de Dyck de hauteur bornée. Pour cela, on redéfinira le modèle de circuit quantique à requête, les languages sans étoile ainsi que les mots de Dyck. Nous détaillerons les différents outils pour prouver de meilleurs bornes sur la complexité quantique en requête. Finalement, nous détaillerons légèrement le meilleur algorithme connu pour reconnaitre les mots de Dyck de hauteur bornée.
13 Décembre 2022- Luca Lionni Invariants LU et mesures aléatoires pour systèmes multipartis de grandes dimensions
Les mesures aléatoires sont un procédé visant à caractériser un état multiparti inconnu à partir d'une distribution de mesures locales faites dans des directions aléatoires (c'est-à-dire transformées par des isométries de façon aléatoire). Je présenterai des résultats pour les mesures aléatoires dans la limite où la dimension N des parties tend vers l'infini, pour les cas suivants: l'état isotropique biparti, et une famille-test de matrices densité multiparties, pour lesquelles on connaît la dépendance asymptotique en N des polynômes invariants sous isométries locales (appelés invariants LU). Je discuterai également de conclusions qu'on peut tirer sur les états quantiques dont les invariants LU ont un tel comportement asymptotique.
6 Décembre 2022-Yassine Hamoudi A sublinear-time quantum algorithm for approximating partition functions
Gibbs partition functions are ubiquitous in statistical physics and in combinatorial counting problems. They capture fundamental statistics, such as the free energy of a thermodynamic system or the number of independent sets of a graph. The problem of efficiently estimating partition functions is the object of intense research, both from a classical and a quantum algorithmic perspective. We present the first quantum algorithm whose running time is sublinear with respect to the logarithm of the size of the state space. Our result combines techniques from simulated annealing, Szegedy's quantum walks and quantum mean estimators. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of k-colorings, matchings or independent sets of a graph, and estimating the volume of a convex body.
29 Novembre 2022- Alex Grilo Hamiltonian complexity meets derandomization
The derandomization of MA, the probabilistic version of NP, is a long standing open question in classical complexity theory. On the other hand, Hamiltonian complexity lies in the heart of quantum complexity theory and has far-reached connections with condensed matter physics. In this talk, I will present a surprising connection between these two fields. More concretely, Iwill present the equivalence between a "stoquastic" version of the quantum PCP conjecture and the derandomization of MA. I will also discuss a related complexity class called StoqMA, and present some recents results regarding the consequences of error reduction for such a complexity class. This talk is based on a joint work with Dorit Aharonov, and a joint work with Dorit Aharonov and Yupan Liu.
22 Novembre 2022- Faedi Loulidi Measurement incompatibility vs. Bell non-locality: an approach via tensor norms.
Measurement incompatibility and quantum non-locality are two key features of quantum theory. Violations of Bell inequalities require quantum entanglement and incompatibility of the measurements used by the two parties involved in the protocol. We analyze the converse question: for which Bell inequalities is the incompatibility of measurements enough to ensure a quantum violation? We relate the two questions by comparing two tensor norms on the space of dichotomic quantum measurements: one characterizing measurement compatibility and the second one characterizing violations of a given Bell inequality. We provide sufficient conditions for the equivalence of the two notions in terms of the matrix describing the correlation Bell inequality. We show that the CHSH inequality and its variants are the only ones satisfying it. Based on arXiv:2205.12668.
8 Novembre 2022 Ravi Kunjwal Contextuality in composite systems: entanglement vs. the Kochen-Specker theorem
The Kochen-Specker (KS) theorem is often taken as a notion of nonclassicality that is independent of entanglement since it's provable on a three-dimensional Hilbert space. However, the smallest system on which both the KS theorem and entanglement are meaningful notions of nonclassicality is a two-qubit system. I will present some recent work on the necessity of entanglement in proofs of the KS theorem on multiqubit systems. We show two key results: firstly, that any proof of the KS theorem that uses KS sets necessarily requires entangled measurements, and secondly, that a statistical proof of the KS theorem with unentangled measurements on a multiqubit state exists if and only if this state can witness a Bell inequality violation. We also obtain an overall understanding of the relationship between unentangled Gleason and KS theorems on multiqudit systems in general. Time permitting, I will also discuss some implications of these results for the role of contextuality as a resource for multiqubit quantum computation with state injection. Based on arXiv:2109.13594.
11 octobre 2022- Giuseppe Di Molfetta Le calcul quantique distribué et ses applications
Au cours de ce séminaire, je résumerai certains des résultats que j'ai obtenus au cours de ces dernières années de recherche. Le contexte est celui du calcul quantique distribué spatialement. Je montrerai comment, en utilisant des objets typiques de l'informatique fondamentale, tels que les automates cellulaires quantiques, nous avons des applications pour la simulation quantique de théories physiques. Mais aussi de nouvelles idées d'architectures distribuées pour les nouvelles technologies quantiques à moyen terme, notamment pour achever la réalisation de mémoire quantique robuste.
27 septembre 2022- Yvan Le Borgne Sur les systèmes quantiques ouverts 2
20 septembre 2022- Yvan Le Borgne Sur les systèmes quantiques ouverts 1
21 Juin 2022- Adrien Poulalion The Continuous Hidden Subgroup Problem (CHSP)
The Hidden Subgroup Problem (HSP), which is at the basis of Shor algorithm, enables period-finding for functions acting on finite abelian groups. Many algorithms draw a quantum speedup from the method introduced by Kitaev in 1995 to solve this finite HSP, which relies on Quantum Fourier Transform. In 2014, Sean Hallgren and al. [1] proved that these principles can be extended to a broader frame including continuous oracles. In this presentation, we will see how to achieve period-finding on functions of R^m (we will call this the Continuous Hidden Subgroup Problem – CHSP), with a particular focus on the difficulties implied by the shift towards the continuous world (technical details in [2]). We will conclude with an arithmetical application to cryptology [1], which consists in solving the famous Pell-Fermat equation.
It will be delivered in English or French, depending on the audience.
7 Juin 2022- Adrian Tanasa On quantum walks
17 Mai 2022 Yvan Le Borgne Sur l'utilisation de Qiskit pour la création, transpilation et (la simulation d') exécution de circuits quantiques.
12 Avril 2022 Kaoutar Benlamine Quantum Machine Learning
Quantum Machine Learning is on the borderline between quantum computing and machine learning and deals with data processing in very large dimensions. It is a new area of study with the recent work on quantum versions of supervised and unsupervised algorithms. In this presentation, I will start by giving an overview of the general concepts of machine learning as well as the quantum computation, then I will show my contributions concerning the quantum one model clustering and multi model clustering. As regards the quantum one model clustering, I will present the quantum K-means version which is an unsupervised algorithm where I will show the different steps to transform a classical unsupervised algorithm to the quantum version. While multi model clustering concerns the collaborative approach of quantum K-means which is based on combining several clustering solutions to get a better solution in terms of clustering. The empirical results will be shown for both approaches.
22 Mars 2022 - Leonardo Novo Spatial search by continuous-time quantum walk
I will present two recent contributions about the performance of quantum search algorithms based on continuous-time quantum walks [1, 2]. First, I will present some general results about the performance of the algorithm introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], which uses a continuous-time quantum walk to find a marked node on a graph of n nodes. This algorithm is said to be optimal if it can find any of the nodes in the graph in O(sqrt(n)) time. I will present conditions, based on the spectrum of the Hamiltonian driving the quantum walk, that can be used to predict whether the algorithm is optimal on a given graph [1]. In the second part of the talk, I will present a new algorithm based on Hamiltonian evolution that finds marked nodes on any ergodic reversible Markov chain P quadratically faster than its classical hitting time [2]. This algorithm can be seen as a quantum walk on the edges of a Markov chain and its performance matches that of recent breakthrough result in the context of discrete-time quantum walk search algorithms. Our work finally closes the theoretical gap between the performance of continuous-time and discrete-time quantum walk approaches for search.
[1] Optimality of spatial search by continuous-time quantum walk, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 032214 (2020)
[2] Quadratic speedup for spatial search by continuous-time quantum walk, S Apers, S Chakraborty, L Novo, J Roland, arXiv:2112.12746
8 Mars 2022 - Yvan Le Borgne Lecture de "Free-fermion subsystem codes" de Chapman, Flammia et Kollar
1er Mars 2022 - Titouan Carette Quantum Wang Tiles
I will present ongoing work on the gathering in one unifying formalism of some notions of symbolic dynamic and quantum computing. This formalism relies on the string diagram notations for symmetric monoidal categories and is linked with graphical languages like the ZX or ZW calculi. I will introduce those different notions, give some preliminary results, and outline our expectations for this research program.
15 Février 2022 - Michel Bauer Une alternative 0-∞ quantique.
Après avoir décrit sans rentrer dans les aspects techniques nos motivations initiales, qui étaient de mieux comprendre l'ETH (the Eigenvalue Thermalization Hypothesis, l'hypothèse que les systèmes quantiques génériques manifestent de propriétés émergentes de thermalisation) nous présenterons un résultat qui est un sous-produit de nos efforts : une condition sous laquelle une suite aléatoire (en un sens que nous préciserons) de sous espaces orthogonaux de dimension finie dans un espace de Hilbert séparable engendre tout l'espace. Ce résultat quantique élémentaire est lié de façon inattendue à un paradoxe classique.
1er Février 2022 Razvan Barbulescu Le bactracking quantique
(d'après un article de Montonaro 2015)
L'algorithme de Grover a des ramifications qui permettent d'obtenir une accélération quadratique dans plusieurs problèmes comme la recherche de minimum ou l'amplification d'amplitude. En 2000 Grover et al. ont essayé sans succès de créer une variante pour les algorithmes de type backtracking qui prennent un temps sqrt(T) là où un ordinateur classique exécute un arbre backtracking à T noeuds. La solution utilise le langage créé par Markov pour étudier les marches aléatoires : décrire le comportement asymptotique des suites v_n = M^n v_0 où v_0 in C^N et M est une matrice N x N. Comme les algorithmes calculant des suites de ce type s'appelle algorithmes de marches aléatoires, on les appelle marches quantiques quand ils sont implantés sur des ordinateurs quantiques. On verra comment choisir une matrice M qui a une valeur propre égale à 1 si et seulement si une branche donnée de l'arbre de backtracking a au moins une solution. On conclue grâce au célèbre algorithme d'estimation de phase, créé par Kitaev en 1995 et qui est une ramification de l'algorithme de Shor pour la factoristion.
25 Janvier 2022 - Yixin Shen Provable quantum algorithms for SVP
The most important computational problem on lattices is the Shortest Vector Problem (SVP). We present new algorithms that improve the state-of-the-art for provable quantum algorithms for SVP, ie, we present a quantum algorithm that runs in time $2^{0.953n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and poly(n) qubits. In the Classical Memory with Quantum Random Access (QRACM) model our algorithm takes only $2^{0.873n+o(n)}$ time and requires a QRACM of size $2^{0.1604n+o(n)}$, poly(n) qubits and $2^{0.5n}$ classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to \cite{ADRS15} that has a time and space complexity $2^{n+o(n)}$. The time complexity of our quantum algorithms is obtained using a known upper bound on a quantity related to the lattice kissing number which is $2^{0.402n}$. We conjecture that for most lattices this quantity is a $2^{o(n)}$. Assuming that this is the case, our quantum algorithm runs in time $2^{0.750n+o(n)}$ and our quantum algorithm in the QRACM model runs in time $2^{0.667n+o(n)}$.
18 Janvier 2022- Cécilia Lancien Performance typique des critères d'intrication pour les états quantiques bipartites
Lorsqu'on a affaire à des systèmes quantiques composés de plusieurs sous-systèmes, une notion cruciale est celle de séparabilité vs intrication. Un obstacle en pratique est que le problème de décider si un état multipartite donné est séparable ou intriqué est en général difficile. Dans cet exposé nous présenterons deux *critères d'intrication* (i.e. des conditions nécessaires à la séparabilité, plus facile à vérifier que la séparabilité elle-même) pour les états bipartites: le critère de *positivité sous transposition partielle* et le critère de *k-extensibilité*. Nous décrirons ensuite deux façons de quantifier la performance typique (i.e. sur des états pris au hasard) de ces critères d'intrication. Nous verrons que toutes deux conduisent à la même (triste!) conclusion: sur des systèmes de grande dimension, ces critères d'intrication sont typiquement des approximations grossières de la séparabilité.
4 Janvier 2022 - Amélia Durbec (14h) puis Nicolas Delfosse (15h+epsilon)
Amélia Durbec (14h) : Dynamiques causales de graphes réversibles ou quantiques
Les dynamiques causales de graphes sont une double extension des automates cellulaires : la grille sous-jacente est étendue à un graphe arbitraire de degré limité et le graphe lui-même peut évoluer dans le temps. Nous présenterons deux formalismes permettant d'avoir un régime réversible et quantique respectivement. Dans le régime réversible, nous verrons qu’une dynamique causale de graphes peut être réversible tout en créant/détruisant des sommets, à travers trois différents modèles équivalents. Dans le régime quantique, nous introduirons une notion de produit tensoriel généralisé et une algèbre de nom afin d'obtenir un formalisme robuste, évitant la transmission instantanée d'information.
Nicolas Delfosse (15h): Two-dimensional implementations of quantum LDPC codes
Quantum LDPC codes are promising to reduce the cost of fault-tolerant quantum computing but can they really be implemented with current quantum hardware which typically looks like a 2D grid of qubits equipped with local gates? In this talk we will provide two answers to this question. First we will discuss obstructions to local implementation of quantum LDPC codes which suggest that quantum LDPC are impractical with 2D local quantum hardware. Second, we propose an implementation of quantum LDPC codes based on long-range connections. With this design, we obtain a threshold of 0.28% for a family of quantum LDPC codes using 49 physical qubits per logical qubit. For a physical error rate of 10^-4, this family reaches a logical error rate of 10^-15 using fourteen times fewer physical qubits than the surface code.
Based on joint work with Michael Beverland and Maxime Tremblay: arXiv:2109.14599 and arXiv:2109.14609.
14 Décembre 2021 - Ion Nechita Introductions aux théories probabilistes généralisées
Les théories probabilistes généralisées (GPT) offrent un cadre général pour décrire des théories physiques ayant une structure convexe. Je vais présenter le formalisme mathématique des GPTs en m'appuyant sur les exemples de la mécanique quantique et des probabilités classiques. La structure des états physiques des systèmes à deux (ou plusieurs) parties joue un rôle important en GPTs; je vais présenter les différents produits tensoriels qui nous permettent de définir ces ensembles d'états. Je vais conclure en discutant les notions d'intrication, distinguabilité d'etats et de clonage en GPT. Une référence récente : https://arxiv.org/abs/2103.07469
30 novembre 2021 - Romain Alléaume Which (quantum) cryptographic world do we live in?
Quantum cryptography has grown rapidly over the past 50 years and in particular over the past decade. Initiated by Wiesner in the 1970s (and then Bennett and Brassard in the 80s) based on intuitions and groundbreaking ideas about the nature of quantum information, it has now evolved into a large field, ranging from quantum communication engineering to foundations of quantum computer science. With the EuroQCI initiative, quantum cryptography is also expected to pave the way towards the development of a European quantum industry. In my talk, I will review some aspects of the ongoing European efforts towards further development of quantum cryptography to which we actively take part at Telecom Paris. I will in particular discuss the cryptographic underpinning of quantum key distribution (QKD) and of its possible applications in cybersecurity. A central, and disputed question on that matter being the security gain that can (or can’t) be achieved with QKD, depending on the security model that is considered. I will then present our work on the development of new quantum cryptography protocols, coined as Quantum Computation Timelock, in an alternative security model. Time permitting, I will also discuss the question of security certification of quantum cryptographic hardware and our recent work on that matter.
23 novembre 2021 -Jonas Landman Algorithmes quantiques pour le machine learning
Ces dernières années, la réalisation d'ordinateurs quantiques revêt un intérêt important. Pour autant, à quoi serviront ces machines? En particulier, pouvons-nous savoir si les algorithmes quantiques pourront être utilisés dans le domaine de l'apprentissage automatique, pour le long terme ou le court terme? Nous montrerons comment relier les principes fondamentaux du machine learning et de l'informatique quantique par l'algèbre linéaire. Ces résultats sont ensuite utilisés pour développer de nouveaux algorithmes quantiques (produit de matrices, estimation de distances) en particulier pour l'apprentissage automatique non supervisé (k-means, spectral clustering) et en réseau de neurones (FNN, CNN, OrthogonalNN). Cela nous permettra de définir de nombreuses procédures fondamentales, notamment en analyse vectorielle et en analyse de graphes. Nous analyserons la complexité de ces algorithmes quantiques par rapport à leur version classique, et étudierons des effets aléatoires dus à la nature quantique du calcul.
16 novembre 2021 - Xavier Caruso La méthode d'amplification d'amplitude
Dans ce (court) exposé, je reviendrai sur l'algorithme de Grover et expliquerai comment celui-ci peut-être adapté pour résoudre à une variété plus générale de problèmes. J'expliquerai, en particulier, comment cette extension s'applique à la recherche de collisions d'une fonction.
9 novembre 2021 - Yassine Hamoudi (à 16h car depuis la Californie) Compromis temps-mémoire quantiques et application à la recherche de collisions
Deux méthodes prédominent pour démontrer des bornes inférieures temporelles dans le modèle de requêtes quantiques : la méthode polynomiale et la méthode par adversaire. Bien que très puissantes, ces techniques sont souvent difficiles et peu intuitives à appliquer. Dans cet exposé, je présenterai une version simplifiée et généralisée d'une nouvelle méthode "d'enregistrement de requêtes quantiques" introduite par Mark Zhandry en 2019. Cette approche permet de reprouver de façon intuitive plusieurs bornes existantes, mais également d'obtenir de nouveaux résultats concernant la complexité en mémoire. Je détaillerai notamment une application aux attaques de collisions avec faible mémoire quantique, montrant que toute attaque quantique optimale en temps nécessite un espace de calcul important.
19 octobre 2021 - Yvan Le Borgne Bornes inférieures en complexités en requêtes quantique d'après Childs (II)
12 octobre 2021 - Yvan Le Borgne Bornes inférieures en complexités en requêtes quantique d'après Childs (I)
28 septembre 2021 - Peter Hines
Logics, Categories, and Foundations
The purpose of this talk is to give compare and contrast two distinct approaches to quantum foundations : the `quantum logic' of J. von Neumann & G. Birkhoff, and the `categorical semantics' introduced by S. Abramsky and B. Coecke.
No background in logic or category theory is assumed; the talk aims to present the motivation, basic definitions, and properties from a fairly high-level perspective. There is a particular emphasis on whether some meeting point may be found between the two approaches : can we find a a logical perspective on the categorical program, or give a `categorification' of the structures used in 'quantum logic'?
In an attempt to do do, we investgate the structure of partial isometries on Hilbert spaces, with particular reference to quantum teleportation. This illustrates some stark differences between the two approaches.
21 septembre 2021 - Géraud Sénizergues
Mixed circuits versus unitary circuits.
29 Juin 2021 et 6 Juillet 2021 - Arnaud Casteigts
Introduction à la complexité algorithmique et petit survol des classes de complexité usuelles
Dans cet exposé, je présenterai quelques notions de bases en complexité algorithmique. Je présenterai notamment les notations asymptotiques, les différents types de problèmes (décision, recherche, etc.), quelques classes de complexités fréquentes (P, NP, L, EXP, PH, PSPACE), la notion de réduction entre problèmes et celle de complétude d'une classe. Puis j'évoquerai BPP, BQP et la notion de séparation de classe par oracle.
22 Juin 2021- Stefan Ataman
Quantum metrological concepts in interferometry
In this talk I will discuss some interesting concepts in quantum metrology. I will use the Mach-Zehnder interferometer as an example but the whole discussion can be easily adapted to other types of interferometers. Starting from the error propagation formula I will define the phase sensitivity for a given type of interferometric measurement. I will also introduce and discuss a very important concept, namely the Fisher information. This information naturally translates into the quantum language and we arrive at what is called the quantum Fisher information (QFI). This concept would be of minimal use if it weren't for a very strong result, namely the famous (quantum) Cramér-Rao bound (QCRB). This is an information-theoretical result, disregarding the detection scheme and thus gives a universal upper bound for the performance of an interferometer and a given input quantum state. For example, we can use it to asses how close to optimality realistic detection schemes are. Examples will be given for coherent and squeezed states of light. Indeed, using squeezed states allows one to cross the standard quantum limit and get closer to what is usually called the Heisenberg limit.
15 juin 2021- Peter Hines
On Oracles in Quantum Algorithms
Quantum algorithms can often be thought of as "returning some 'global information' about a classical function" -- the period of the function in question, whether it is constant or balanced, the number of inputs that lead to a particular output, etc. In theoretical work, these classical functions are commonly treated as 'black boxes'; oracles that act classically on some computational basis, but are coherent (i.e. superposition-preserving) on arbitrary inputs.
At some stage, we need to move beyond the view of such oracles as black boxes, and consider how they may be implemented.
For many reasons -- discussed in this talk -- oracles need to be implemented as quantum circuits, without the use of higher-level programming constructs such as feedback, recursion, or conditional iteration. The purpose of this talk is to consider how or whether we may nevertheless translate classical computations defined using such tools into the quantum circuit paradigm.
This is a non-trivial question, closely related to John Myers' critique of David Deutsch's "Quantum Turing Machines" and Noah Linden & Sandu Popescu's "Halting Problem for Quantum Computers". We approach it by looking at classical computations defined in terms of conditional iteration, based on the very common paradigm of 'unlabeled transition systems'. We characterise when such computations may be performed by coherence quantum circuits, and give a compilation procedure that allows us to do so, based on some standard tools from theoretical computer science.
This procedure is efficient -- it requires a logarithmic space overhead & linear time overhead, and garbage collection is performed automatically. As a consequence, we may take a classical computation described by (for example) a reversible space-bounded Turing machine, and produce a coherent quantum circuit that performs the same calculation.
8 juin 2021 - Faedi Loulidi
Normes tensorielles et jeux quantiques
Dans cet exposé on va introduire les inégalités de Bell. On se focalisera sur une inégalité connue sous le nom de CHSH. On introduira la notion de jeu quantique ainsi que son lien naturel avec les notions de normes sur des tenseurs.
1er Juin 2021 - Stéphane Dartois
Jeux d'isomorphismes de graphes et notions d'isomorphismes généralisés
18 mai 2021 - Stéphane Dartois
Sur les matrices de densité
4 mai 2021 - Jean-François Bony
Programmes quantiques adiabatiques
Dans les exposés précédents, les algorithmes quantiques présentés utilisaient principalement des portes. Mais il existe aussi une approche basée sur l'évolution de hamiltoniens quantiques. Ces derniers, plus proches de la mécanique quantique, sont possiblement plus faciles à réaliser.
1) Après quelques rappels sur l'équation de Schrödinger en dimension finie, on énoncera le théorème adiabatique.
2) Puis, on présentera le fonctionnement des algorithmes quantiques adiabatiques.
3) Enfin, on démontrera l'équivalence entre algorithmes à portes et algorithmes adiabatiques.
27 avril 2021 - Xavier Caruso
Algorithme de Grover et applications
L'algorithme de Grover est un célèbre algorithme quantique qui
permet, étant donnés une fonction f : X -> Y (représentée par
un circuit Uf qui la calcule) et un élement y dans son image,
de trouver un antécédent de y en ne faisant que O(sqrt(|X|))
appels au circuit Uf.
Dans cet exposé, j'expliquerai le fonctionnement de l'algorithme
de Grover et montrerai comment celui-ci peut être aussi utilisé
pour accélérer la recherche de collisions (i.e. étant donnée une
fonction f non injective, pour trouver deux éléments ayant la
même image).
Si le temps le permet, j'expliquerai également la méthode dite
d'amplification de phase qui permet, sous de faibles hypothèses,
de booster fortement la probabilité de réussite d'un algorithme.
13 Avril 2021 - Yvan Le Borgne
Analyse de l'algorithme de Schöning pour k-sat et lectures sur la startup Pasqal
6 Avril 2021 - Yvan Le Borgne
Sur un problème de vérification de satisfiabilité de formule SAT utilisé dans une démonstration d'avantage quantique
30 Mars 2021 - Razvan Barbulescu
L'impact de l'ordinateur quantique en cryptographie
Dans cette séance nous prenons un point de vue historique. Nous faisons
le point sur les problèmes calculatoires utilisés en cryptographie et
leur complexité. Nous comparons leur avantage et désavantage respectif.
Nous rappelons les autorité gouvernemantales qui calcules les tailles
des clés et présentons la date de standardisation de chaque primitive
mathématique en cryptographie.
16 Mars 2021 - Gilles Zémor
(Codes LDPC Quantiques, Episode 2)
Nous aborderons les percées très récentes (automne 2020) qui permettent de dépasser significativement la barrière de la racine carrée du nombre de qubits pour la distance minimale d'un code LDPC.
2 Mars 2021 - Xavier Caruso
Sur l’implémentation de l’algorithme de Shor
L'algorithme de factorisation de Shor est un algorithme quantique qui permet de factoriser un nombre entier en temps polynomial en la taille de l'entrée. Dans cet exposé, j'expliquerai comment implémenter concrètement cet algorithme sur un processeur quantique (supposé parfait) dont les seules primitives sont la porte CNOT et les portes de translation de phase. Nous verrons en particulier que la factorisation d'un entier de n
bits ne requiert que 2n+3 qubits.
23 Février 2021 - Exposé à Harvard à 15h30 de Jian Wei Pan
From Multi-Photon Entanglement to Quantum Computational Advantage
Mardi 9 Février 2021 - Gilles Zémor
Codes LDPC quantiques
Un code LDPC (Low Density Parity-Check) est un code stabilisateur défini par des générateurs de petits poids. Nous ferons un état de l'art des connaissances sur les codes
LDPC quantiques, en partant du code de Kitaev, la plus ancienne construction de code LDPC. Nous verrons que toutes les autres constructions connues sont, au moins en partie, de nature topologique, et que l'on peut les considérer comme dérivées de la construction
d'origine de Kitaev.
Nous aborderons les percées très récentes (automne 2020) qui permettent de dépasser significativement la barrière de la racine carrée du nombre de qubits pour la distance minimale d'un code LDPC.
Mardi 26 Janvier 2021 - Ion Nechita
Suprématie quantique : l'expérience du groupe Martinis (Google)
Je reviendrai sur la notion de suprématie quantique discutée dans l'exposé précédent, et sur l’approche de l'échantillonnage de circuits aléatoires suivie par le groupe de Google. Je vais présenter les mathématiques derrière les circuits quantiques aléatoires et des probabilités de sortie de ces circuits. Comprendre comment ces probabilités peuvent être obtenues avec des méthodes classiques joue un double rôle. D’une part, cela permet de valider l'expérience de Google, c.à.d. de vérifier que les valeurs obtenues sont bien celles prédites par la mécanique quantique. D’une autre part, des résultats de théorie de complexité (classique) semblent indiquer qu’il est impossible de simuler classiquement les probabilités de sortie des circuits quantiques aléatoires. Enfin, j’essayerai de montrer comment dans l’article “Quantum supremacy using a programmable superconducting processor” tous ces arguments sont utilisés ensemble pour revendiquer la "suprématie" quantique.
Mardi 12 Janvier 2021 - Jean-François Marckert
Les arguments des détracteurs de l'informatique quantique
Mardi 15 décembre 2020 à 15h - Stéphane Dartois
Calcul quantique et anyons 3, l'exemple des anyons de Fibonacci
Mardi 8 décembre 2020 à 15h - Stéphane Dartois
Calcul quantique et anyons 2, détour par les anyons abéliens de Kitaev
Mardi 1er décembre 2020 à 15h - Stéphane Dartois
Calcul quantique et anyons 1, l'exemple des anyons de Fibonacci
Mardi 24 novembre 2020 à 15h - Yvan Le Borgne
Quelques élements sur les marches quantiques
Mardi 17 Novembre 2020 à 15h - Yvan Le Borgne
Expérimentations d'IBM sur le processeur quantique Falcon 2 (Informatique)
Mardi 10 Novembre 2020 à 15h - Yvan Le Borgne
Expérimentations d'IBM sur le processeur quantique Falcon 1 (Physique)
Mercredi 24 Juin 2020 à 15h15 - Géraud Sénizergues
Calcul quantique: le cadre mathématique 3
Mercredi 10 Juin 2020 à 15h15 - Géraud Sénizergues
Calcul quantique: le cadre mathématique 2
Mercredi 3 Juin 2020 à 15h15 - Géraud Sénizergues
Calcul quantique: le cadre mathématique 1
Mercredi 27 Mail 2020 à 15h15 - Gilles Zémor
Introduction aux codes correcteurs quantiques (Partie 2)
Mercredi 20 Mail 2020 à 15h15 - Gilles Zémor
Introduction aux codes correcteurs quantiques (Partie 1)
Mercredi 13 Mai 2020 à 15h15 - Yvan Le Borgne et Géraud Sénizergues
Théorème de non-clonage, BB84, et téléportation quantique
Mercredi 6 Mail 2020 à 15h15 - Xavier Caruso
Vers les algorithmes de Simon et Shor (suite) par Xavier Caruso
(Algorithme de Shor)
Mercredi 29 Avril 2020 à 15h15 - Stéphane Dartois + Xavier Caruso
(L'enregistrement est disponible dans le salon où s'est déroulé le GT)
Equation de Schrödinger et évolution unitaire par Stéphane Dartois
Résumé du premier exposé:
Dans cet exposé nous introduirons l'équation de Schrödinger comme l'équation d'évolution des états quantiques, nous verrons alors qu'elle implique une évolution unitaire, ce qui justifie le paradigme du calcul réversible en calcul quantique.
Vers les algorithmes de Simon et Shor par Xavier Caruso
Résumé :
(Algorithme de Simon)
Transparents : http://www.labri.fr/perso/borgne/Talk/gt5b-simon.pdf
Chaque exposé durera 30 minutes.
Mercredi 22 Avril 2020 à 15h15 - Géraud Senizergues
Algorithme de Deutsch et de de Deutsch-Jozsa par Géraud Senizergues
(L'enregistrement est disponible dans le salon où s'est déroulé l'exposé)
Dans cet exposé, je présenterai l'algorithme de Deutsch-Jozsa selon le plan suivant:
- Boolean functions vs unitary operators
- Deutsch algorithm over boolean functions
- Advocate devil's criticism
- Quantum parallelism
- Deutsch-Josza algorithm over boolean functions.
Les transparents : http://www.labri.fr/perso/borgne/Talk/gt4-deutsch.pdf
Mercredi 15 Avril 2020 à 15h15 - Stéphane Dartois
Petit survol de la mécanique quantique
Salon BBB (enregistrement disponible)
Résumé:
Dans cet exposé du GT informatique quantique, je présenterai un petit
survol de la mécanique quantique. Je discuterai quelques morceaux d'histoire,
les tous premiers problèmes physiques bizarres qui ont mis sur la piste de la
mécanique quantique. Je ferai ensuite un saut dans le temps pour discuter la
fameuse "dualité onde-particule". J'énoncerai par la suite les principes de
base de la mécanique quantique en termes plutôt simples. Puis si le temps le
permet je décrirai la version analytique du problème d'Einstein-Podolski-Rosen
et des inégalités de Bell. Cet exposé est le premier d'une petite série et sera
le moins technique de la série. La technicité ira croissante au long de la
présentation mais devrait rester très raisonnable, avec zéro équation pour la
première moitié de l'exposé, et rien qui ne dépasse les toutes premières années
de licence (il sera par contre nécessaire de prendre certains faits pour
acquis).
http://www.labri.fr/perso/borgne/Talk/gt3-survol-mecanique-quantique.pdf
Mercredi 8 Avril 2020 à 15h15 - Yvan Le Borgne
Circuits logiques classiques et quantiques
Salon BB, enregistrement disponible.
Résumé :
Après le survol du premier exposé, nous reprenons plus précisément la
description des différents types de circuits logiques. Pour plusieurs
types, nous présentons explicitement des ensembles universels de
quelques de portes. Ils sont dits universels car ces portes, combinées
dans des circuits, permettent d'implémenter toutes les fonctions
étudiées. C'est l'occasion d'introduire progressivement une notation
matricielle pour la description du calcul. À l'occasion nous
effleurerons la notion de code correcteur (surtout classique et par
répétition) et d'une expérience d'interférence (Mach-Zehnder)
distinguant les phénomènes quantiques des probabilités.