What physics can tell us about inferenc...Cristopher Moore
Conférence de Cristopher Moore organisée par le département de Physique.
Of all the interfaces between physics and computer science that have grown up in the last few decades, quantum computing is one of the most exciting. Much of this excitement was driven by Peter Shor’s 1994 discovery that quantum computers can efficiently factor large integers, and thus break the RSA public-key cryptosystem. After describing how Shor’s algorithm works, I will describe why many of us were hopeful that a similar algorithm could work for Graph Isomorphism, another problem not known to be efficiently solvable by classical computers. Our hopes were dashed by the representation theory of the symmetric group, to which I will give a friendly introduction. As a result, we now know that no quantum algorithm remotely similar to Shor’s will solve this problem.
Voir aussi
What physics can tell us about inferenc...
Les sables mouvants
Développements actuels en spintronique
La physique au LHC (Large Hadron Collide...
La physique au LHC (Large Hadron Collide...
La physique au LHC (Large Hadron Collide...
La physique au LHC (Large Hadron Collide...
Des dynamos industrielles aux champs mag...
La nanophotonique : éclats d’une lumièr...
Les gaz ultra-froids : un monde quantiqu...
Joining Microelectronics and Microionic...
Allers et retours entre physique et biol...
La dynamo turbulente : résultats récent...
Semiconductor Nanocrystals: Science and ...
Deux siècles de découvertes sur la capil...
Quantum Shot Noise: From Schottky to Bel...
Les polaritons de cavité : des condensat...
Un nucléaire durable pour une énergie d’...
Premier bilan de la mission spatiale Cas...
Matériaux d’indice négatif : avec Alice ...
Les archives ouvertes
La zététique, une éducation à l’autodéfe...
Cell surface mechanics during tissue mor...
Modélisation de la dynamique non-linéair...
Physics of Multicellularity
Nanovecteurs de médicaments et nanofiltr...
Le grand collisionneur d’hadrons
Mécanique et vibro-acoustique du piano
Gérer la contrainte carbone, un jeu d'en...
The Complex Physics of Climate Change : ...
Évaluation de la qualité du violon : co...
Quantum finite non-equilibrium thermodyn...
Hamiltonian Theory of Fractional Chern B...
Emerging and broken symmetries in turbul...
Inverse cascades and condensates
How masses have been generated in the ea...
Casimir energies and forces an accelerat...
How atoms and charges move in crystals ...
Science in society issues the example o...
The physical genome
Tracing the growth of massive black hole...
When the environment drives the system q...
Statistical physics of compressed sensin...
Some new results on the history of ancie...
Mesoscopic superconductivity what do we ...
Polymers, Message Passing, and London Un...
Quantum memories with cold atomic ensemb...
Analysis of fluid systems by optimizatio...
Carbon chelmistry and carbon balance in ...
Imaging magnetic fields at the nanoscal...
Black hole accretion and cosmic evolutio...
Physics of Cancer - The role of angiogen...
Quantum limit of heat flow across an ele...
Thermodynamics of strongly correlates ga...
Fast and slow quenches across second ord...
Conformal symmetry of critical fluctuati...
La physique surprise - Renouveler les ex...
Economic and financial crises, a physici...
Why do we see it that way ? 
A few applications of vector bundles in ...
A few applications of vector bundles in ...
Statistical physics of neural assemblie...
Auditory perception of temporal modulati...
Bacteria powered micro-devices
Mesures de précision et tests fondamenta...
The Ultimate Limit of Optical Fibers to ...
Hot topic in nanomedicine : how to overc...
Attosecond lasers : principles, metrolog...
Imaging of extrasolar planets : challeng...
2015 Planck full mission result
Nonequilibrium structures and glassy dyn...
Soft matter and cooking : a pedagogical ...
From water molecules to atmospheric circ...
Backaction of quantum measurement in sup...
From fundamental physics to the origins ...
LEDs for lighting - the physical and mat...
Nanoassembling for soft matter : fluidic...
Clustering of networks : From phase tran...
Dynamic nuclear polarization
The new role of time and events in compu...
Modelling the physics of galaxy formatio...
What keeps the magnetic field of the Ear...
Short wavelength radiation
From the basics of spintronics to some r...
Topological Mechanical Metamaterials
The universe before the big bang
How to pack and unpack spheres
Black holes reject their food
Electron quantum optics in ballistic con...
Electron quantum optics in ballistic con...
Cavity quantum electrodynamics with carb...
Controlling light propagation in comple...
SubTHz photons in the universe and in m...
Climat : y voir clair pour agir
Learning multiscale invariants from big ...
Diversity of immune receptor repertoire...
Biomicrofluidics and Mesobiotechnologie...
The building of the future: challenges a...
The Rosetta Mission
Non-linear responses, soft-modes and th...
Ergodicity : an historical perspective. ...
Is the forced two-dimensional model “goo...
What is the difference between a graphen...
The birth of gravitational astronomy
Making 'Living Matter' from the bottom u...
The birth of gravitational astronomy
The H boson and Beyond at the LHC
Hybrid organic perovskites : a new semic...
Exploring the outer solar system with st...
Physics and Sport
Charge storage in nanoporous carbons: Th...
General Relativity, Gravitational Waves ...
Multicolor and multicontrast nonlinear m...
Statistical-physics inspired modelling o...
Materials advances for better Li(Na)-io...
Cosmic connections : from cosmic rays t...
Analyse technique et économique du systè...
Gravitational Waves : Theory, Sources an...
Gravitational Waves : Theory, Sources an...
Atomic force microscopy provides new vis...
Understanding old masters’ painting tech...
Quantum simulations : from condensed mat...
The Single Molecule Game
Earthquakes ! In the laboratory...
Shortcuts to adiabaticity
On Effective Field Theory
Searching for Dark Matter
Electron and lattice dynamics in solids ...
Pluto revealed by the New Horizons missi...
Probing and controlling ultracold quantu...
Nanotechnology for single-molecule and s...
Undecidability in physics… and its conse...
Collective effects in transport systems...
The Nobel prize in Physics 2016: Topolog...
The ocean : A turbulent control system f...
Nonlinear fluctuating hydrodynamics and ...
The physics of exceptional points
Modeling solids and its impact on scienc...
What can we do with genes in medicine ? ...
Hydrodynamics and quantum anomalies
Light Control in complex media : from im...
Light Control in complex media : from im...
From quantum measurement to quantum simu...
De la topologie aux machines moléculaire...
From glass to vitrimers : a story of exc...
Tests of quantum mechanics and gravitati...
Stories of grains in fluids
Fluids of light in semiconductor lattice...
The direct observation of gravitational ...
Towards a Predictive Theory of Strongly-...
Nanopores in 2D Materials
Towards a renormalization group for netw...
Long-range propagation of ocean swell
Fast magnetic reconnection in space and ...
Dynamical fluctuations far from equilibr...
Graphene in the (Terahertz) Microwave
An introduction to quantum cryptography...
A tale of turbulence and gravity
Quand les ondes dessinent des motifs géo...
Nano-optics : an enabling tool for basi...
From “cognitive-type” neural microcircui...
Quantum Internet : Vision or Fiction ? 
Fast irreversible Markov chains and thei...
Quantum Inflation in the Planck Era and ...
Physics approaches of biological membran...
When random walkers help solving intrigu...
Extracting Order from Disorder : Periodi...
Statistics and Dynamics of Soft Wetting
A statistical physics perspective on som...
Quantum optomechanics with superfluid he...
Neuromorphic computing : overview and ch...
Slip of polymeric fluids
Dynamics of mixed turbulent / stably-st...
Pour en savoir plus sur l'aération et l...
Pratique de la mesure du CO2 dans les ét...
The spin glass cornucopia revisited
Twenty years of mesoscopic physics at EN...
Scale invariance for quantum fluids : so...
Ground based gravitational-wave astronom...
How a physical system can be turned int...
Probing the first galaxies and cosmic re...
Propagation and stabilization in time-va...
How personalised is our immune repertoir...
The Swampland Program in Quantum Gravit...
SARS-CoV-2: pathologies, mesure du risqu...
Quantum many-body physics with ultracol...
Quantum Science with Rydberg Atoms
On the nature of the glass transition
Quantum Chaos and the Foundations of Sta...
Cell iophysics : phase diagrams, phase p...
Odd turbulence
Universal scalings in evolving and stati...
Cristopher Moore
Cursus :
Cristopher David Moore, connu sous le nom de Cris Moore est un informaticien américain, mathématicien et physicien. Il est professeur à l'Institut de Santa Fe et a été professeur à l'Université du Nouveau-Mexique.
Cliquer ICI pour fermer Annexes Téléchargements :Dernière mise à jour : 22/11/2016
Liens utiles
Contact
Partenaires
Conditions d'utilisation
Mentions légales
Podcasts
> Colloquium DEC
> Les Ernest
> Les jeudis de l’archéologie
> Actualité critique
> Les jeudis de l’HPS
> Séminaire Médecine
Humanités
> Journée Georges Bram
> Les lundis de la philo
> Les Nuits de l’ENS
> Semaine du cerveau
> Séminaire général du
département d'informatique
> Séminaire général
de physique
> Séminaire Transferts culturels
> La Voix d’un texte
Savoirs ENS