Les Journées Informatique Quantique sont organisées par le groupe de travail Informatique Quantique (GT_IQ) du GdR IM. Elles se dérouleront au LIG à Grenoble.
Présentation
Les Journées Informatique Quantique ont pour but de rassembler la communauté travaillant dans les différents domaines que recouvre l'informatique quantique. Une série d'exposés permettra de prendre connaissance des travaux des participants. Les jeunes chercheurs, tout particulièrement les doctorants et post-doctorants, sont vivement encouragés à présenter leurs résultats récents ou travaux en cours.
Exposé invité
Ross Duncan, University of Strathclyde.
Programme
Jeudi 26 Novembre Après-midi
Lieu: Salle de réception (rez de chaussée) de la MJK
13h Accueil
14h - 14h 55 Ross Duncan, The ZX-calculus, strong complementarity, and non-locality.
15h - 15h 30 Simon Perdrix, Supplementarity is Necessary for Quantum Diagram Reasoning
15h 35 - 16h 05 Quanlong Wang, Minimality of ZX-calculus for stabiliser quantum mechanics
16h 05 - 16h 25 Pause café
16h 30 - 17h Stefano facchini, Quantum random walks on curved space-time
17h - 18h Réflexion sur le GDR
Vendredi 27 Novembre matin:
Lieu: Salle de réception (rez de chaussée) de la MJK
9h 15 - 9h 45 Frédéric Grosshans, Factoring Safe Semiprimes with a Single Quantum Query
9h 50 - 10h 20 Alex Bredariol Grilo, Multiprover games and quantum PCP.
10h 25 - 10h 45 Pause café
10h 45 - 11h 15 Leonardo Disilvestro, Adapting quantum stabilizer codes to the Spekkens' toy model
11h 20 - 11h 50 Ruben Y. Cohen, Entanglement distribution across a quantum peer-to-peer network
Vendredi 27 Novembre Après-midi
Lieu: Amphitéatre (1er étage) de la MJK
14h - 14h 30 Iordanis Kerenidis Quantum Recommendation Systems
14h 35 - 15h 05 Niraj Kumar, Quantum Fingerprinting with Coherent States for Multiple Clients
15h 05 - 15h 20 Pause café
15h 25 - 15h 55 Theodoros Kapourniotis, On optimising quantum communication in verifiable quantum computing
16h - 16h 30 Kaushik Chakraborty, Arbitrarily long relativistic bit commitment
Informations pratiques
La rencontre se déroulera à la Maison Jean Kuntzmann (MJK) sur le campus scientifique de Grenoble.
Adresse : 110 rue de la Chimie à St Martin d'Hères.
Accès : Tram ligne B ou ligne C, arrêt Bibliothèque Universitaire.
Quelques adresses pour manger
Abstracts
The ZX-calculus, strong complementarity, and non-locality.
Ross Duncan University of Strathclyde.
The ZX-calculus is a graphical formal language for quantum computing based on the fact that the Z and X spin observables are *strongly* complementary. I’ll introduce the calculus, give some examples of its use in verifying quantum programs. The concept of strong complementarity is a novel idea introduced by the calculus, and relates to the underlying group structure of the eigenstates of the two observables — I’ll show how this can be used to reproduce the famous GHZ/Mermin non-locality argument.
Adapting quantum stabilizer codes to the Spekkens' toy mode.
Leonardo Disilvestro, LTCI, Telecom ParisTech.
Quantum theory is believed to provide improvements both in computational power and security with respect to classical information theory. In order to better understand the origin of these improvements, we translate emblematic quantum protocols to Spekkens' toy model - a local hidden variable theory which is phenomenologically very close to quantum theory. Despite the toy model non being able to provide any computational speed up with respect to quantum theory, we see that it can still provide similar security statements as in the quantum case. We notice how the existence of anticommutation relations between toy measurements and toy transformations and the existence of `toy purifications' seems to be sufficient to implement many quantum protocols within the toy model. In particular, we show that error correction, secret sharing, and blind and verified computation are indeed possible in the toy model along with providing a proof of the impossibility of toy-bit commitment. Our results firstly suggest that purifications and anticommutaiton relations provide the structure behind the existence of these protocols within quantum theory; and secondly, the ability to perform blind and verified computation in the toy model strongly suggest that not only steering is a sufficient property for such a protocol, but that any probabilistic theory featuring purification is indeed apt to implement blind and verified computation.
Minimality of ZX-calculus for stabiliser quantum mechanics
Quanlong Wang, Universite de Lorraine, Region Lorraine, LORIA, Nancy, France
Stabiliser quantum mechanics (QM) is an extensively studied fragment of pure state quantum theory where the only allowed operations are preparations or measurements in the computational basis and unitary transformations belonging to the Clifford group. It is of central importance in areas such as error-correcting codes or measurement-based quantum computation. Instead of the standard Dirac or matrix notations, Stabilizer QM can be modelled by an intuitive graphical language called ZX-calculus, which is a formal system developed for quantum mechanics and quantum information processing with built-in rewrite rules. The corresponding ZX-calculus for stabiliser QM is composed of diagrams and rules involving multiple of π/2 only. It is known that the ZX-calculus is complete for stabiliser QM, meaning that any equality (up to a global scalar) that can be derived using matrices can also be derived pictorially. However, there is no result on what the minimal rules are for the ZX-calculus in the sense that each rule cannot be derived from the other rules. Here we propose a new system of rules of ZX-calculus for stabiliser QM. We prove that the new system of rules is sound, and is equivalent to the old one. Furthermore, we prove that each rule in the new system is necessary.
Arbitrarily long relativistic bit commitment
Kaushik Chakraborty, André Chailloux, Anthony Leverrier Inria, EPI SECRET,
Bit commitment is one of the most important primitives in the domain of two-party cryptography, where one party Alice commits a bit b to another party Bob with a constraint that the parties don’t trust each other. The security requirement for Alice is that she doesn’t want Bob to have any information about her commitment before the reveal phase . This is called hiding property. The security requirement for Bob is that he doesn’t want Alice to be able to change her commitment after the commit phase. This is called binding property. It is proven that designing a secure bit commitment protocol with perfect hiding and binding is impossible, even in quantum domain [1]. But secure bit commitment can be achieved if we combine quantum theory with special relativity - more precisely with the law that information cannot propagate faster than the speed of light [2]. There are many secure commitment protocols based on this relativistic model but every one of them suffers from the fact that to achieve arbitrary long commitment time the parties should be separated spatially very far apart, which is impractical in practice. In this work, we examined a protocol due to Lunghi et al. [3] and improved their security bound against classical adversaries. Indeed, according to their security analysis the required resources scale double exponentially with the commitment time, making the protocol impractical for realistic applications. For instance, with the optimal con- figuration on Earth (meaning that each party has agents occupying antipodal locations on Earth), the commitment time is limited to less than a second. Here, we provide a new security analysis of the same protocol, establishing that the dependence is in fact linear, provided that the dishonest player is classical. This implies that arbitrary long commitment time can be achieved even if both parties are only a few kilometers apart.
[1] D.Mayers, Phys. Rev. Lett. 78 , 3414 (1997).
[2] A.Kent, Phys. Rev. Lett. 83 , 1447 (1999),
[3] T.Lunghi, J.Kaniewski, F.Bussieres, R.Houlmann, M.Tomamichel, S.Wehner, and H.Zbinden, Phys. Rev. Lett. 115 , 030502 (2015)
Entanglement distribution across a quantum peer-to-peer network
Ruben Y. Cohen, Emmanuel Jeandel, Perdrix Simon and Frédéric Grosshans (Presenter : Ruben Y. Cohen, Université Paris-Sud )
Quantum repeaters have been proposed to overcome the practical distance limit of quantum communication between two parties. Here, we go beyond this linear scheme and explore the possibilities offered by an arbitrary network of such repeaters, connecting N clients. We model these networks by undirected graphs where each vertex corresponds to a client and each edge to a quantum repeater sharing a maximally entangled pair between the two connected peers. A client can either perform a Bell measurement between two qubits or keep only one qubit. In a single time step, two vertices (the sender and the receiver) can share entanglement if they are connected by a continuous path in the graph: the vertices along the path have to perform a Bell measurement and classically communicate their results to the sender and the receiver. Furthermore, the above strategy allows to simultaneously share EPR pairs between several pairs of clients if the corresponding paths are vertex disjoint. If the main cost of such a network is proportional to the number of repeaters, the efficiency of a network is obtained by comparing the number P of EPR pairs that can be shared simultaneously in the worst case, to the resources used to generate the graph i.e. the total number E of edges. P is upper bounded by half of the minimal degree C of the graph, and hence half of the average degree: P≤C/2≤E/N and also by the non-orientable genus of the graph g : P≤g+1. We construct two graph families (almost) saturating this degree bound: one is the complete join of a clique of order 2P and an stable set of order N-2P; the other is the Cartesian product of a cycle and a complete graph.
Factoring Safe Semiprimes with a Single Quantum Query
Frédéric Grosshans, Thomas Lawson, François Morain, Benjamin Smith (Presenter : Frédéric Grosshans, CNRS)
Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a quantum order finding algorithm (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to 1/2, these classical routines fail, and the QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. We present a new quantum factoring algorithm based on the QOFA which is better than SFA at factoring safe semiprimes, an important class of numbers reputed to be the hardest to factor. With just one call to the QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalising this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non strong semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.
Quantum Fingerprinting with Coherent States for Multiple Clients
Niraj Kumar, Eleni Diamanti and Iordanis Kerenidis (Presenter Niraj Kumar Telecom Paristech)
Communication complexity studies the amount of communication required by separate parties to jointly compute a task. A general communication complexity is modeled as having Client1 and Client2 who receive input(s) x;y in { 0 ; 1} respectively. Their task is to jointly compute a binary function f(x,y) with minimum inter communication as possible. Our work focuses on simulta- neous message passing (SMP)[1] model (Figure 1) involving a Referee and two servers Alice(A) and Bob(B) who have multiple ( l ) clients connected to them. Each client receives an n bit input and every client from server A wants to check for equality with the input of some other client in server B. The communication between the server and Referee is limited by k channels. During the protocol run, the only communication that is possible is client -> server and server -> referee. Direct communications between client -> client or server -> server is forbidden. The function can trivially be computed if the all the clients send their n bit inputs to the server and server relays it to the Referee via the k chan- nels. But this would involve high communication costs if the input size is big. With the objective of minimizing this cost, the players can instead make a fingerprint of their inputs which would be considerably smaller in size which achieves the same task of computing f( x,y) with a small error probability. We first talk about the best classical fingerprinting protocol [2]. The clients create the fingerprint of length 2 sqrt(n) + O(1) bits and send them to the servers who eventually sends it to the referee. The referee compares it with the fingerprint from a client of the other server and returns the result. One such equality succeeds with an error probability 0.25 . Next we define the quantum fingerprin- ting protocol with qubits. The objective is to look at the protocol from implementation point of view. Ideally, the use of single photons for implementing the quantum fingerprint is a highly challenging task because of the limitation in preparing single photon qubits with high accuracy. Instead we use coherent states the prepare quantum fingerprints. Since our model involves multiple clients with multiple equalities, we propose a novel idea of using frequency multiplexing of the coherent finger- printing states with k channels, to have a gain in communication costs compared to the best classical protocol. We also talk about the communication resources involved in the protocol, Transmitted Information, Energy and Time taken , and compare them in the classical and quantum scenarios.
[1] H. Buhrman, R. Cleve, J. Watrous, R. de Wolf, "Quantum Fin- gerprinting", Phys. Rev. Lett. 87, 167902(2001).
[2] L. Babai and P.G. Kimmel, "Randomized Simultaneous Mes- sages : Solution Of A Problem Of Yao In Communication Com- plexity", 12th Annual IEEE Conference on Computational Com- plexity(1997).
Quantum Recommendation Systems
Iordanis Kerenidis LIAFA
We present a quantum algorithm for recommendation systems with running time O(poly(k)∗ polylog(mn)), where k is the rank parameter. The rank of the recommendation matrix is usually assumed to be constant and in any case much smaller than the dimension of the matrix. Recommendation systems have been studied extensively in the classical world and in most cases they perform a reconstruction of a matrix and hence run in time polynomial in its dimension.
On optimising quantum communication in verifiable quantum computing
Theodoros Kapourniotis Télécom Paristech
In the absence of any efficient classical schemes for verifying a universal quantum computer, the importance of limiting the required quantum resources for this task has been highlighted recently. Currently, most of efficient quantum verification protocols are based on cryptographic techniques where an almost classical verifier executes her desired encrypted quantum computation remotely on an untrusted quantum prover. In this work we present a new protocol for quantum verification by incorporating existing techniques in a non-standard composition to reduce the required quantum communication between the verifier and the prover.
Multiprover games and quantum PCP.
Alex Bredariol Grilo LIAFA
The celebrated PCP theorem asserts that all languages in NP admit randomized Verifiers that only check a constant number of bits of the proof. This theorem can be also cast into two likewise statements: the NP-hardness of approximation of MAX-SAT up to some constant factor and NP-hardness of approximation of the maximum acceptance probability of a multiprover game up to constant additive factor. A quantum PCP theorem would state that all languages in QMA admit quantum Verifiers that only check a few number of qubits of the quantum proof. Towards a proof (or disproff) of a quantum PCP theorem, the QMA-hardness for gapped Local Hamiltonians (quantum version of MAX-SAT) was proved equivalent to the proof verification statement. In this work, we study the Quantum PCP conjecture through the lens of multiprover games, defining a specific type of games, called Lookup-table games, and proving that the quantum PCP is equivalent to approximating its maximum acceptance probability.
Quelques adresses pour manger
Sur le campus
Le martin's café
(à l'arrêt du tram) 401 Avenue de la Bibliothèque, 38400 Saint-Martin-d'Hères Téléphone :04 76 54 43 36Le canberra
430 Rue de la Passerelle, 38400 Saint-Martin-d'Hères Téléphone :04 76 82 44 39 (a aussi formule pizza)Cafettes étudiants
Le café littéraire
71 Ter rue des universités Domaine Universitaire 38400 St Martin d'HèresL'entracte
(pizza, steak haché frites...) Rue des universités (sous le restaurant Diderot) Domaine Universitaire 38400 St Martin d’HèresSandwicheries
(à l'arrêt du tram) le Factory (Bagels), le Camion (plat du jour, sandwitchs froids,hot dog, mini quiche), la camionnette (paninis,sandwitchs frites)En centre ville
A Confesse
(fondue) 27 Rue St laurent 38000 Grenoble Téléphone : 04 76 54 11 60le Namasté
(indien) 2 rue Renauldon, 38000, Grenoble, France 04 76 54 29 89Le cèdre
(libanais) 4 Rue Lazare Carnot, 38000 Grenoble Téléphone :04 76 47 42 20Chez lili
(chinois) 5 Rue Crepu, 38000 Grenoble Téléphone :04 80 38 82 54Organisateurs
 |
 |
 |