View
108
Download
0
Category
Preview:
Citation preview
1
Complexité de requêtes du problème de collision
et de problèmes liés
C. Dürr (LRI - Orsay)
travail avec Harry Buhrman, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf
v1
2
Utiliser les algorithmes quantiques connusShor :
Problème de sous-groupe caché
Grover : Recherche du minimum, Problème de collision,Recherche du median
Trouver de nouveaux algorithmes quantiques
Utiliser de nouveaux opérateurs unitairesTransformée de
Hadamard Deutsch-Jozsa, Bernstein-Vazirani
Transformée de Fourier Simon, Shor
Matrice de HaarHøyer-Neerbek-Shi
Matrices de Hadamardvan Dam
3
Problème de collision
Entrée : f:[N]Z
0 1 … i j N-1
Chercher : i,j[N] tel que f(i)=f(j), ij
f :
Z :
4
0 1 … i N-1
Problème d’intersection
Entrée : f:[N]Z g:[M]Z
Chercher : i[N], j[M] tel que f(i)=g(j)
f :
Z :
0 1 … j M-1 : g
5
Modèles de complexité
Modèle de requêtesOn compte le nombre d’appels à f ou g
Modèle de comparaisonsOn ne peut pas lire directement f ou gSeuls des comparaisons f(i)<f(j), g(i)<g(j),
f(i)<g(j) sont possibles et comptéesAucune hypothèse n’est faite sur Z, sauf
qu’il est muni d’un ordre
6
Entrée: f:[N]{0,1}
Outil recherche quantique
Trouver (avec proba ½): i[N], tel que f(i)=1en appelant f O(N½) fois
f(i)=0
f(i)=1
[Grover]
7
Complexité classique/quantique
Rechercher zZ dans f:[N]Z
cas général (f n’est pas forcément triée)
(N), (N½) [Grover]
cas f triée(log N), (log N)
0.53 log N par [Fahri,Goldstein,Gutman,Sipser]
log3N+O(1) par [Høyer,Neerbek,Shi]
8
Outil amplification quantique
Entrée : Algorithme A avec probabilité de succès p
Répéter O(p-½) fois Apour probabilité de succès ½
succès
[Brassard,Høyer,Mosca,Tapp]
9
Borne inférieure par réduction
Problème de recherchepour h:[N]{0,1} trouver i tel que h(i)=1(N½) [Bennet,Bernstein,Brassard,Vazirani]
Problème de collisionf: i i+h(i)
Donc le problème de collision est (N½)
f:
10
Intersection: cas f trié
Chercher j[M] tel que g(j)f([N])
ce test coûte log(N)
Cette recherche coûte M tests Coût total O(M log(N))
j
f([N])
f: :g
… et N<M
11
A B
Intersection: cas général
Trouver une intersection entre f et g– Chercher A[N], |A|=k
et B[M], |B|=k2 tel que f(A)g(B){}
Trouver une intersection entre f(A) et g(B)– Trier f(A)– Chercher jB tel que g(j)f(A)
j
f(A)
f: :g
coûte O(k log k)
coûte O(k2 log k)
coûte O((MN/k3) k log k)
=O ((MN/k) log k)
12
Complexité
Meilleur choix de k avec kmin(N, M)
NMN2 N2<M
(M)
O(N½M¼logN)
O(N¾logN)
O(M½logN)
13
Intersection: cas f et g triées
Application possibleQuestion à google.com “Calcul quantique”Réponse: éléments en commun de
tableaux précalculées et triées (une par mot clé)
… et N=M
f: 4 7 8 12 15 21 22 27 29 32 34
g: 5 8 11 26 22 26 32
14
Sous-problème
f:
f est découpé en blocs de taille r
a
fi : restriction de f au i-ième bloc
g: b
g’i : restriction de g au bloc de taille r, commençant au premier b, tq g(b)f(a)
collision?
Sous-problèmes (f’i,gi) définis pareillement
0 i N/r
15
Algorithme
Le problème initial a une solution si et seulement si un parmi les 2N/r sous-problèmes a une solution (“est positif”)
• Recherche quantiquement un sous-problème positif
• Appliquer récursivement cet algorithme aux sous-problèmes
16
Complexité T(N)
T(N) c’(N/r)½(log(N+1)+T(r))
Appel récursif
Recherche binaire du début de bloc
Recherche quantique d’un sous-problème
Choisir r=log2(N)
T(N) c’’ (N/r)½ T(r)
pour des constantes c’,c’’
17
Complexité
T(N)=O(N½clog*(N))
Logarithme itéré
log(i)(x) = log log … log (x)
log*(x) = min{i 0 : log(i)(x) 1}
Fonction presque constante
clog*(N) = o(log(i)(N)) pour tout i
pour une constante c
18
Entrée : graphe G(V,E), n=|V|, m=|E|Trouver : a,b,c V tel que
(a,b), (b,c), (c,a) E
Recherche naïveRecherche quantique sur (a,b,c)V3
Complexité de requêtes O(n3/2)
Recherche de triangles
19
Pour graphes épars
• Recherche quantique d’une arête (a,b)E
• Recherche quantique d’un 3-ième sommet c tel que (b,c), (c,a) E
• Amplifier quantiquement la probabilité de succès
… m=o(n2)
O(m½) requêtes
O(n½) requêtes
O(m½) répétitions
Au total O(n+(nm)½)
20
Récapitulatif classique/quantique
Collision dans f 2-to-1 (i !j f(i)=f(j))
(N½), O(N)[Brassard,Høyer,Tapp]
Collision dans f(N), O(N¾logN), (N½ logN)
[Høyer,Neerbek,Shi]
Intersection entre f et g triées(N), O(N½clog*(N))
Triangles(n2), O(n+(nm)½)
21
Problèmes difficiles
Pour f : [N]Z Parité des collisions
trouver la parité du nombre de i,j (i<j) tel que f(i)=f(j)
Sans collisiontrouver i qui n’est pas en collision avec un j
Hors imagetrouver zZ tel que z n’est pas dans
l’image de f
… même quantiquement (N)
22
Directions futures
Trouver une borne inférieure pour le problème de collision dans f 2-to-1
Fermer le fossé entre les deux bornes pour le problème de collision
Dans le modèle de requêtes, utiliser le fait que pour f : [N][N]
∑j f(j) avec =e2i/N
est 0 pour f sans collision et diff. de 0 pour f avec une unique collision
Recommended