J'ai vu/lu pleins de vidéos, d'articles sur le sujet et à chaque fois ça parle de capacités fantastiques qu'apportent les qubits, j'ai même déjà vu des articles expliqués que ça allait permettre de casser instantanément tous les "cryptages" utilisant des nombres premiers. Mais sans jamais expliqué comment.

Je place ça au même niveau que les nostradamus de la singularité, d'ailleurs à ce sujet :

Akshell a écrit :
J'ai vu/lu pleins de vidéos, d'articles sur le sujet et à chaque fois ça parle de capacités fantastiques qu'apportent les qubits, j'ai même déjà vu des articles expliqués que ça allait permettre de casser instantanément tous les "cryptages" utilisant des nombres premiers. Mais sans jamais expliqué comment.

http://en.wikipedia.org/wiki/Shor's_algorithm

Merci, enfin même si je ne suis pas sur de mieux comprendre le problème.

« The factorization also needs huge amount of quantum gates. It increases with N as (log N)3. Thus factoring of a 4096-bit number requires 4,947,802,324,992 quantum gates. »

5 000 milliards de porte quantiques nécessaires, en même temps ? J'en ai l'impression.

« a quantum gate is a basic quantum circuit operating on a small number of qubits. »

« In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 × 5, using an NMR implementation of a quantum computer with 7 qubits. [...] Also in 2012, the factorization of 21 was achieved »

et pour comparaison, même si comparer un qubit à un transistor semble idiot :

« Six-Core Core i7/8-Core Xeon E5 (Sandy Bridge-E/EP) 2,270,000,000 transistors »

Même un gros CPU actuel ne fait que 2 milliards de transistors, ce qui fait quoi, 1 milliards de portes logiques au mieux ?

Du coup je reste tout aussi sceptique, l'échelle à atteindre pour réussir semble impossible à atteindre.

J'ai loupé un truc ?

Je crois comprendre que l'auteur du blog dont la phrase sur le nombre \log^3 N est tirée se plante un peu -- il semblerait que ce soit en fait (\log N is the number of bits of the key)
- O(\log^3 N) time (ce qui est tout à fait acceptable)
- O(\log N) space (i.e., "nombre de gates")

cf. commentaires, qui renvoient aussi vers un paragraphe du papier original de Shor.

Pas lu, mais ceci est censément une très bonne et accessible présentation de l'algorithme de Shor. Aaaronson est plus ou moins un dieu dans le domaine.

Oui, c'est un peu ça.

Ceacy a écrit :
- O(\log^3 N) time (ce qui est tout à fait acceptable)
- O(\log N) space (i.e., "nombre de gates")

Mais avec des valeurs ? je veux dire des entiers, des unités.

Haha Gingin je partage complètement ton avis.

Akshell a écrit :
Oui, c'est un peu ça.

Ceacy a écrit :
- O(\log^3 N) time (ce qui est tout à fait acceptable)
- O(\log N) space (i.e., "nombre de gates")

Mais avec des valeurs ? je veux dire des entiers, des unités.

De ce que j'ai compris,
Time : 72(\log N)^3, i.e. 5 000 milliards d'étapes/opérations (ce qui va plutôt vite) pour 4096-bit (ce qui est énorme)
Space: je ne connais pas la constante, mais \log N = 4096 dans l'example, et je m'attends à une constante pas très grande au vu du 72 de l'autre O().

Il devait pouvoir apporter un début de solution

Ceacy a écrit :
4096-bit (ce qui est énorme)

Tout à fait, c'est énorme.