Auteur/autrice : admin_qics

This PhD research project has been submitted for a funding request to “Quantum Information Center Sorbonne (QICS)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.

Abstract:

Quantum optomechanics and electromechanics is a fast growing field with promising applications in quantum information. Recently non-classical mechanical states have been realized. However, full control of a quantum mechanical mode, which is necessary for successful quantum information processing based on electromechanical systems, has yet to be demonstrated. This project aims to develop a novel quantum electromechanical device capable of obtaining full quantum control of a macroscopic mechanical resonator by integrating a phononic microcavity with a superconducting transmon qubit. We expect to achieve a very strong qubit-phonon coupling coefficient that will allow the realization of any quantum unitary operation on the phononic mode. This will have important applications in quantum information and quantum sensing. In addition this project opens the route to test the relevance of the quantum mechanics to the macroscopic world.

Objectives:

Quantum information processing with electromechanical devices requires full control over a non- classical mechanical state.

Although non-classical mechanical states have been recently demonstrated full control over these quantum mechanical states has yet to be achieved.

This project aims to develop a novel quantum electromechanical device, capable of obtaining full quantum control of a macroscopic mechanical resonator, based on a phononic cavity strongly coupled with a superconducting qubit.

This has the potential to pave the way towards successful quantum information processing based on electromechanical systems.

The main objectives of this project are to:
Integrate a phononic micropillar cavity with a transmon superconducting qubit.

Prepare arbitrary superpositions of phonon number states of the mechanical mode (including Fock and Schrodinger cat states).

Realize arbitrary quantum unitary operations on the mechanical mode.
This project will be done in collaboration with Benjamin Huard and Audrey Bienfait from ENS Lyon

Contact to submit your application :
Valia Voliotis, valia.voliotis@insp.jussieu.fr
Daniel Garcia Sanchez, daniel.garcia-sanchez@insp.upmc.fr

This PhD research project has been submitted for a funding request to “Quantum Information Center Sorbonne (QICS)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.

Since its early stages, quantum computing has had drastic consequences to cryptography. In the one hand, (full-scalable) quantum computers could be used to break widely used cryptosystems, given the celebrated Shor’s algorithm for factoring. On the other hand, quantum resources have also been used to realize cryptographic tasks that are otherwise impossible, for example quantum money (e.g. Wiesner’80), sharing private keys (e.g. Bennet and Brassard’84) or generating certifiable randomness (e.g. Colbeck’09). We remark that all of these primitives can be constructed in the quantum world unconditionally, meaning that we do not need to impose any computational assumption on the adversaries.

These results raise an ambitious possibility for the field of cryptography, namely the possibility of realizing every cryptographic primitive unconditionally with quantum resources.
Unfortunately, this was shown impossible, we know today several primitives that are not realizable even with quantum resources unconditionally (Mayers’97, Lo and Chau’97). Therefore, in order to be able to implement cryptographic protocols of interest, even in a quantum world, we must rely on computational assumptions.

We have seen that these computational assumptions come in two flavours. First, we see constructions based on the hardness of specific problems, such as factoring, lattices problems, etc. As spotted by Shor’s algorithm, the downside of this approach is that we are walking on thin ice by relying on particular assumptions and this brings us to the second, and more general, way of constructing cryptographic schemes. This second perspective in cryptography is to rely on the hardness of abstract problems with special properties. For example, we know how to construct some protocols based on the existence of one-way functions (OWF), which are functions that are easy to compute and hard to invert. We remark that these protocols work for any OWF that you might implement.

Recently, Grilo et al.’20 and Bartusek et al.’20 have independently proved that oblivious transfer can be built from OWF in the quantum world, which was an open problem since the protocol proposal of Bennet et al ‘96.(Roughly, in oblivious transfer, Alice has two messages m0 and m1 and Bob has a bit b. At the end of the protocol, Alice does not learn b and Bob learns mb, but not mb). These results are another example where quantum resources can help us implement cryptographic primitives from weaker assumptions, since there are strong indications that OT cannot be built from OWF in the classical world.

PhD project

The main goal in our project is to explore novel consequences that quantum computing could bring to Impagliazzo’s 5 worlds, specially its impact on cryptography. Despite the impressive success of quantum computation/cryptography, we remark that progress on this line has been very limited. Examples of questions that could be explored by the PhD candidate are:

Constant-round ZK proofs from OWF: There is strong evidence that zero-knowledge proofs (a fundamental cryptographic primitive) cannot be implemented in constant-round classically in the plain mode, i.e. without any trusted help (Katz’08). However, these no-go results rely on complexity theoretical assumptions that do not quantize. Thus, a natural open question that could be explore in this PhD project is the (in)feasibility of constant-round quantum zero-knowledge proofs (ideally from one-way functions). This could clarify which type of advantage quantum resources can provide on the construction of cryptographic primitives.

Role of quantum obfuscation in quantum cryptography: In the classical world, the concept of indistinguishable obfuscation (iO), which asks that the ofuscation of two programs with the same functionality cannot be distinguished, has been shown to be a very strong primitive that can enable the implementation of several cryptographic primitives which are not known to exist otherwise. To stress its usefulness, iO is frequently called « crypto-complete » in the classical scenario. Such a strong functionality comes of course with a cost: for decades the existence of secure iO schemes was elusive, until a very recent result of Jain, Lin and Sahai, which constructs iO from well-founded cryptographic assumptions.

The study of obfuscation in the quantum setting, specially its consequences, has been very limited. In particular, a direction that could be pursued in this PhD project would be to study the feasibility of strong quantum functionalities from quantum iO.

Lower bounds on quantum cryptographic protocols. Shoup’97 showed that in a « generic group » model, it is impossible to solve the discrete logarithm problem (or Diffie-Hellman) of a group of prime order p using O(sqrt(p)) group operations. Shor’s polynomial algorithm for discrete-log directly implies that such a lower bound does not hold in the quantum setting. One potential direction for this PhD project would be to study if such lower bounds on the computational complexity for quantum algorithms can be proven for other generic mathematical structures, for example the Couveignes hard homogeneous spaces (based on group actions) underlying the cryptographic constructions based on elliptic curves isogenies, a cryptographic assumption that has resisted to quantum attacks (so far).

Pertinence of the project 

This PhD concerns topics in the theoretical aspects (post-)quantum cryptography, a very important subject within the scope of QICS. The different background of both PhD supervisors (cryptography for D. Vergnaud and quantum computing for A. Grilo) combine in a very natural way to supervise this project.

Contact to submit your application :
Damien Vergnaud, damien.vergnaud@lip6.fr
Alex Bredariol Grilo, Alex.Bredariol-Grilo@lip6.fr

We list now some publications from the supervisors that are relevant for this proposal:

Grilo, Lin, Song, and Vaikuntanathan. Oblivious Transfer is in MiniQCrypt. Accepted at Eurocrypt 2021 and plenary talk at QIP 2021.

Alagic, Childs, Grilo and Hung. Non-interactive Classical Verification of Quantum Computation. TCC 2020 and contributed talk at QIP 2021.

Broadbent and Grilo. QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge, FOCS 2020 and plenary talk at QIP 2021

This PhD research project has been submitted for a funding request to “Quantum Information Center Sorbonne (QICS)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.

The main goal of this PhD project is to study the problems that lie in the intersection of quatum Hamiltonian complexity and (classical) derandomization. These are two important topics in the field of Computational Complexity theory of independent interest.

On the one hand, the derandomization problem asks if randomness increases the computational power of polynomial-time computation. More specifically, we are interested in the non- deterministic version of the derandomization conjecture, which roughly says that every problem whose solution can be verified by randomized algorithms can also be verified by deterministic ones. In technical terms, this is stated as NP = MA, where NP is the class of problems with efficient deterministic verification and MA is its randomized analog. It is widely believed that derandomization is possible,and this is supported by plausible assumptions (e.g. the existence of pseudorandom generators, etc.), but proving even weaker versions of this conjecture has been an active area of research.

On the other hand, Hamiltonian complexity lies in the heart of quantum complexity theory due to its relevance for physics and computer science. The central problem here is the following: given as input a local Hamiltonian H that describes the evolution of an n-particle quantum system, find an approximation of the ground-energy of H, which is the value of energy corresponding to the ground- state of H. The importance of this problem was put in evidence by Kitaev, who showed in 1999 that the approximation of the ground-energy of a Hamiltonian, up to an inverse polynomial additive error, is QMA-complete, where QMA is the quantum analog of NP. The quantum PCP conjecture states that approximating the ground-energy of a Hamiltonian up to a constant additive error remains QMA-complete. This conjecture has important consequences to complexity theory and condensed matter physics, e.g. it implies the existence of families of quantum systems with highly entangled states even at « room temperature ».

The surprising relation between derandomization and Hamitlonian complexity was proved by Aharonov and Grilo – one of the co-advisors in this project – (FOCS’19). More concretly, they show that proving the quantum PCP conjecture for a restricted family of quantum Hamiltonians, named Stoquastic Hamiltonians, is actually equivalent to the MA vs. NP questions. For the best of our knowledge, this is the very first approach to prove derandomization statements from results in quantum computing.

It is worthy to mention that stoquastic Hamiltonians arise naturally in quantum physics, and since they do not suffer of what is called the sign problem, they are more amenable to be tackled by classical techniques. Moreover, stoquastic Hamiltonians have practical importance, since, for example, they describe some non-universal quantum computers that were developed in practice, like D-Wave devices.

PhD project

The goal is to strengthen the connection between derandomization and Hamiltonian complexity that was initiated by Grilo and Aharonov.

More concretely, our plan is to try tackle intermediate steps towards a quantum PCP theorem for stoquastic Hamiltoanians. Attacking these « simpler » problems would not only provide valuable insights towards the stoquastic PCP conjecture, but it could also elucidate critical difficulties for the general version of these problems, which remain open.

We now describe some specific problems that could be explore by the PhD candidate:

Low-energy state generation: An important question in Hamiltonian complexity is the efficiency of creating low-energy states of Hamiltonians. Notice that there is always an efficient circuit that constructs the ground-state of classical Hamiltonians (but, finding such a circuit is a hard task since the problem is NP-complete). Quantumly, it is not expected that the ground-state of local Hamiltonians can be efficiently created since this contradicts some believed complexity theoretical assumptions, namely QCMA being different of QMA. However, it is unclear if this (conditional) impossibility also holds for low-energy states of the Hamiltonian. In this context, the No Low-energy Trivial States conjecture (NLTS) was proposed to study « toy » versions of this question. NLTS states that there is a family of Hamiltonians for which constant-depth quantum circuits cannot construct states with low energy. While this statement is reasonable, being even implied by the quantum PCP conjecture, it has been answered only partially and in restricted settings. In this project, we want to study the NLTS conjecture but restricted to stoquastic Hamiltonians. In particular, our goal is to use tools developed in Aharonov and Grilo, together with techniques related to Markov chains, quantum walks, and derandomization, to possibly disprove a stoquastic version of the NLTS conjecture.

Classical simulation of the evolution of stoquastic Hamiltonians. Adiabatic quantum computation is a computational model described by the evolution of quantum systems. Formally, it is defined by two Hamiltonians: the first one has an easy-to-prepare ground-state, whereas the second one encodes the computational problem that we want to solve. The computation is performed by slowly transitioning from the ground-state of the initial Hamiltonian into the ground-state of the final one, which would give us the answer for our computational problem. This model of computation was proposed hoping that it would lead to faster algorithms for combinatorial optimization problems and for this purpose it was used in the (non-universal) D-Wave’s machine. In particular, D-Wave’s devices implement the adiabatic evolution of stoquastic Hamiltonians. Bravyi and Terhal (SICOMP 2009) proved an efficient classical simulation of the adiabatic evolution of a natural subfamily of stoquastic Hamiltonians, namely frustration-free ones. On the other hand, in a recent results by Gilyén, Hastings and Vazirani (STOC 2021) gives some indication that the adiabatic evolution of stoquastic Hamiltonians is strictly more powerful than classical computation, by proving an oracle separation between them. In this project, we want to explore some of the graph-theoretical tools from Aharonov and Grilo, together with new combinatorial techniques from Hodge theory and derandomization to find larger families of Hamiltonians that can be classically simulated. This could be used to achieve further advances on the question « how quantum is the D-Wave machine? ». Moreover, another question in this direction is extending the oracle separation of Hasting to the non-deterministic setting, clarifying the landscape of the complexity of stoquastic Hamiltonians. Pertinence of the project

This PhD project has the potential to achieve important advances in our understanding of the computational power of sub-families of quantum Hamiltonians, which clearly lies in the scope of QICS.

Contact to submit your application :
Damian Markham, damian.markham@lip6.fr
Alex Bredariol Grilo, Alex.Bredariol-Grilo@lip6.fr

We list now some publications from the supervisors that are relevant for this proposal:

Antonio, Markham, Anders, Trade-off between computation time and Hamiltonian degree in adiabatic graph state quantum computation, NJP 16, 113070 (2014)

Aharonov, Grilo, and Liu. StoqMA vs. MA: the power of error reduction. Under submission. Aharonov and Grilo. Two Combinatorial MA-Complete Problems. ITCS 2021
Aharonov and Grilo. Stoquastic PCP vs. Randomness. FOCS 2019 and plenary talk at QIP 2020.

Petits projets pour le soutien et la promotion de l’information quantique et de son écosystème

Chères et chers membres de la communauté quantique de Sorbonne Université,

Comme vous le savez, l’Alliance Sorbonne Université a fondé en 2020 le Quantum Information Center Sorbonne (QICS) pour intensifier les interactions entre la recherche expérimentale, théorique et l’ingénierie en information quantique — calcul et communications quantiques —, tout en explorant les implications sociétales de cette nouvelle façon de traiter l’information. 

En janvier 2021, c’est le plan quantique français qui a été annoncé et qui promet des perspectives positives pour l’information quantique et son écosystème.
Cependant, nous avons fait le constat qu’actuellement un certain nombre de petits projets pouvaient se trouver difficiles à financer. 

Nous souhaitons donc, cette année, ouvrir un appel au fil de l’eau, pour encourager et favoriser le développement des projets de notre communauté en finançant, par exemple :
–      les gratifications de stage ;
–      l’achat de petits équipements (caméra vidéo, ou petit matériel pour un test expérimental) ;
–      la production d’outils de communication ou de médiation scientifique (podcast, vidéos, jeux, etc.)
–      l’organisation de séminaires, de workshops, de conférences ;
–      les déplacements / missions ;
–      ou tout autre activité pour laquelle les subventions peuvent être difficiles à obtenir.
Lancer cet appel, c’est vous proposer notre soutien financier mais aussi offrir une visibilité à vos projets d’équipes.

N’hésitez pas à partager cette information le plus largement possible et à nous envoyer vos contributions afin de participer au développement de projets quantiques d’envergure grâce à notre communauté.

L’équipe du QICS

5-6 month internship

Compulsory courses (18-24 ECTS)

• AQAlg: Advanced Quantum Algorithms, 6 ECTS, Shor algorithms, Quantum Fourier Transform, phase estimations and applications, quantum random walks , query complexity (algorithms, lower bounds), HHL algorithm and machine learning applications, hidden subgroup algorithms.
• AQCrypt: Advanced Quantum Cryptography, 6 ECTS, The use of quantum states has many cryptographic applications. This course includes advanced quantum key distribution (various technologies and protocols, security proofs, practical problems, full and semi-device independence), but also other cryptographic protocols (bit commitment, oblivious transfer in the noisy storage model, secret sharing, verification
• QIT: Quantum Information Theory, 6 ECTS, The quantum analogue of Shanon theory and complexity theory are very rich, with many applications: Mathematical foundations and link with programming, quantum Shannon theory (various entropies, super additivity, Holevo theorem); communication complexity, with lower bounds and exponential separations; channel theory; entanglement theory, nonlocal games, information causality; quantum complexity theory, BQP, QMA, QMA(2), QIP=QIP(3)=PSPACE=QPSPACE.
• PhQC: Photonics Quantum Computing, 6 ECTS, Photonics is an essential platform for quantum communications and a promising one for quantum computing. These platforms are centered around measurement based quantum computing (MBQC). We willl study: Graph-states (in continuous and discrete variables), Graph-based cryptographic protocols, MBQC, delegated blind/verified universal quantum computing, photonic graph states implementations.

Elective courses (6-12 ECTS) (subject to availability) »>

• NDA: Network Data Analysis, 6 ECTS, Introduction to probability and statistics. Bayes’s law. Data collection, parameter estimation and regression methods. Statistical fitting. Hypothesis testing and applications to identification of changes that influence the network operation. Clustering and classification. Time-series analysis.
• POSSO: Polynomial systems Resolution, 6 ECTS, Polynomial systems model static nonlinear situations. Their resolution is therefore more delicate than the resolution of linear systems, but nevertheless crucial since these systems appear naturally in post-quantum cryptology and various engineering sciences (robotics, biology, chemistry, artificial vision, etc.). In this course, we will study efficient algorithms allowing us to solve such systems and examples of applications will be studied.
• RDFIA: Pattern Recognition and Machine Learning for Image Understanding, 6 ECTS, this course presents theory and algorithms for classification and image understanding (Bayesian decision, machine learning, supervised and unsupervised learning, kernel-based methods, deep learning…). Illustrations are provided, on several applications for image classification.
• AAGA: Analyse d’Algorithmes et Génération Aléatoire (only in French), 6 ECTS, Ce cours introduit des méthodes pour étudier la complexité moyenne des algorithmes et la génération aléatoire de structures combinatoires. Divers types d’applications seront traitées, en liaison avec les structures arborescentes et l’algorithmique probabiliste.La seconde partie du cours introduit la combinatoire analytique afin d’étudier algorithmes et structures de données en moyenne.
• HPCA: Advanced High Performance Computing  (only in French), 6 ECTS, Algorithmes et techniques de programmation parallèles avancés pour le calcul haute performance. Conception , implémentation et optimisation des programmes parallèles sur des architectures hétérogènes et massivement parallèles (GPU, calcul haute performance à large échelle sur un grand nombre de noeuds …). Introduction aux langages standards pour le calcul haute performance (extensions de langage et directives de compilation), optimisation de code dans un contexte hétérogène : multi- architecture et multi-paradigme, algorithmes parallèles et leur stabilité numérique pour l’algèbre linéaire numérique, algorithmes parallèles minimisant les communications, calcul haute performance et reproductibilité, algorithmique asynchrone. Mise en pratique sur une application réelle (projet).
• Teaching units of SU Master of Physics, especially Lumi or ICFP, can also supplement the course offer.

Compulsory courses (18 ECTS)

• QIIntro: Quantum information overview, 6 ECTS, The objective is to give the student a broad overview of theoretical quantum information, including fundamental concepts (entanglement, teleportation, nonlocality, decoherence), quantum communication protocol (teleportation, quantum key distribution), quantum algorithms (Shor, Grover and VQE) and some notions of quantum error correction.
• PQIG: Quantum Information Group Project, 3 ECTS, Project with physics students: Work in small groups with students from various backgrounds on a Quantum information problem, performing a short review of the state-of-the-art and an experimentation.<
• PQIA: Advanced Quantum Information Project, 9 ECTS, Project work on Quantum information problem, performing a review, an analysis and an implementation of one or several solutions.

Elective courses (12ECTS) (subject to availability)

• ANum, 3ECTS, This unit is the natural continuation of  MODEL. Provide the knowledge in mathematical tools and algorithms in order to be able to solve concrete problems of large sizes. We will study in particular algorithms and their implementation frequently used in the field of scientific computing and data science. The applications will be very diverse and may change each year: for example, we will see applications in finance (calculation of the price of options), in simulation of structures for 3D printing, in imagery (image compression), in deep learning (stochastic gradient algorithm), etc. We will endeavor for each algorithm to propose versions allowing an efficient implementation on parallel machines. The algorithms will be coded in MATLAB or in Python.
• FLAG: Basics of Algebraic Algorithms, 6 ECTS, This course present algebraic algorithms for basic and building blocks problems, targeting quasi-optimal complexity. To do so, we shall rely on linear algebra modeling of the problem. However, we shall show that this modeling yields a linear system with a structure that can actually be solved faster than general algorithms allow us to. These problems find applications in computer algebra, cryptography, coding theory or robotics. A thorough implementation of these algorithms will also be studied.
• IG3D: Introduction to Computer Graphics, 6 ECTS,This course introduces the domain of 3D computer graphics, including geometric modeling and processing, image synthesis, with implementation in OpenGL and C/C++.
• NDM: Network Design and Modeling, 6 ECTS, Introduction to the problem of modeling and performance evaluation of systems. It aims at answering the following questions: Why models are important? When do we need to evaluate the performance of a system? How? What kinds of models and techniques are useful?
• HPC: High Performance Computing (only in French), 6 ECTS, Introduction au calcul haute performance et au parallélisme pour concevoir, implémenter et optimiser les programmes parallèles sur des architectures classiques (multi- processeurs et multi-cœurs). Les points suivants sont abordés : architecture des machines parallèles, algorithmique parallèle, parallélisme de données et de tâches, décomposition et équilibrage de charge, paradigmes standards de programmation parallèle sur machines à mémoire distribuée ou partagée (standards MPI et OpenMP), programmation mixte multi-thread / multi-processus, optimisation de code séquentiel pour le calcul haute performance, programmation vectorielle (SIMD), introduction à la parallélisation automatique. Mise en pratique sur une application réelle (projet).
• PC2R: Programmation Concurrente, Réactive et Répartie (only in French), 6 ECTS, L’objectif de ce cours est de comprendre la programmation concurrente et son utilisation pour l’expression d’algorithmes dans les modèles à mémoire partagée, distincte et répartie. Dans le modèle à mémoire partagée, on s’intéresse aux modèles de threads coopératifs et préemptifs puis à la programmation réactive pour récupérer la propriété de déterminisme. Dans le modèle à mémoire répartie on cherche à maîtriser le modèle client/serveur et de savoir déployer des objets répartis.