Ich denke, ich habe noch ein paar Ideen, die ich hier mal loswerden will.
Ich denke, man kann Faktorisierung mit einem klassischen Ising-Hamiltonian lösen. Wenn die Einschwingzeit exponentiell in der Länge des Inputs wäre, hätten wir einen physikalischen Nachweis, dass Faktorisierung in NP liegt. Wenn nicht, hätten wir einen physikalischen Nachweis, dass Faktorisierung in P liegt. Eine Freundin meinte mal zu mir, dass wenn man beiweisen könnte, dass Faktorisierung in P liegt, dass dann P = NP wäre.
Ein physikalischer Beweis ist kein Beweis und reicht nicht aus. Aber es würde die momentane Annahme, dass P ungleich NP ist, untermauern.
Ich denke, man kann shortest distance on a lattice auf einen oder mehrere gekoppelte Festkörper mappen. Wenn ich die Kopplung kenne, kann ich einen befreundeten Mathematiker um einen No-Go-Beweis bitten. Aber bis dahin glaube ich, dass die Natur effizient minimieren kann. Ein diskretes Minimierungsproblem gegen die Natur zu verwenden spricht gegne meine physikalische Intuition. Ich weiß, dass ich damit alleine bin. Befreundete Informatiker fragen mich nach dem Mapping. Aber das ist nicht mein Job. Wenn ich das exakte Mapping wüsste, wäre ich reich. Es ist euer Job, zu beweisen, dass es ein solches Mapping nicht gibt.
Aber wenn man davon ausgeht, dass die Natur diskret ist (was wir durch Messung nicht beweisen können, da wir an die Planck-Grenze stoßen), dann kann man auch davon ausgehen, dass die Natur effizient auf diskreten Gittern faktorisieren kann. Nur der richtige Umwandlungsfaktor wäre dann noch unser Problem. Finde es und du brichst die besten aktuellen Kandidaten für Post-Quanten-Kryptographie, die aktuell besten Vorschläge für quantencomputersichere Verschlüsselung.
Ehrlich gesagt ist es mir egal, was die Informatiker sagen. Ja, vielleicht bin ich durchgeknallt. Ich habe zu wenig Ahnung von Komplexitätstheorie, um sagen zu können, ob diskrete Optimierung quantensicher ist. Aber wenn ich einen Verschlüsselungsalgorithmus habe, hätte ich gerne mehr Sicherheit, als sagen zu können „ok, seit X Jahren haben wir keinen Gegenbeweis gefunden“. Ich hätte gerne Krypto, die beweisbar sicher ist. Nicht angreifbar durch Brute Force.
Solche Kryptographie existiert. Das One-Time-Pad ist beweisbar sicher. Die Übertragung ist das Problem und die lässt sich in der Theorie beweisbar durch die Eigenschaften der Quantenmechanik (No-Cloning-Theorem) lösen. Ja, es gibt Angriffsvektoren, aber das ist ein Problem der Ingenieure. Wenn ich schon arbeite für irgendwas, will ich sicher sein, dass es beweisbar sicher ist. Und zumindest kann ich sagen, dass, solange der Dichtematrixformalismus hält, mein eines Protokoll zur Verifikation von Graph States sicher ist.
Ja, es ist extrem ineffizient. Aber es ist beweisbar sicher mit einer gewissen Wahrscheinlichkeit X. Das ist mehr, als aktuelle Kryptoalgorithmen von sich behaupten können xoxo.
Ja, vielleicht sind meine Ideen für die Tonne. Ja, vielleicht ist meine Intuition falsch. Ja, vielleicht gibt es den Beweis, dass n-dimensionale Gitter NP-hart sind. Aber noch habe ich meinen minikleinen Abschluss (Bachelor in Physik) und noch sagt mir meine Intuition, dass shortest distance on a lattice effizient berechenbar ist durch die Natur. Hiermit rufe ich eine Challenge aus.
Wer mir beweist, dass shortest distance on a lattice in NP liegt, kriegt von mir 1000 Euro. Wenn ich oder wer anders einen polynominalen Beweis findet für shortest distance on a lattice hätte bewiesen, dass P = NP, was die meisten von uns anzweifeln. Als jemand, der erstaunlich wenig Ahnung von Informatik hat, und vielleicht nur deshalb den Mut, shortest distance on a lattice zu kritisieren, gibts von mir 1000 Euro für einen entsprechenden polynominalen Beweis, der analoge Computer verwendet. Digitale Computer sind breit erforscht. Wir kennen ihre Grenzen in Sachen Komplexität. Aber ich hätte gerne einen Beweis, dass die Natur das auch weiß. Dass jeder Physiker, der von Minimierung spricht, diskret denken muss. Dass „Mathematische Methoden der Quantenmechanik“, wo Von Neumann die kontinuierliche Formulierung der Quantenmechanik verwendet, eigentlich für die Tonne ist und Chemiker mit linearer Algebra auskommen, statt Theoreme aus der Funktionalanalysis zu verwenden.
Ich will ihn haben, den Algorithmus, der für immer quantencomputersicher ist. Einen Beweis, der mir ein No-Go-Theorem für Quantencomputer gibt. Einen Algorithmus, bei dem sicher ist, dass niemals irgendwer sich einen Algorithmus für Quantencomputer ausdenkt, der ihn brechen kann. Ach ja, Analogcomputer sind in dem Fall ein Spezialfall für Quantencomputer im klassischen Limit.
Quantenkrypto ist sicher. Das OTP lässt sich mit Brute Force nicht angreifen. Und für die Algorithmen, die nicht nur Peer-2-Peer, sondern Quantennetzwerke aufs Horn nehmen, können wir beweisbar physikalische Schranken und Sicherheitsbeweise finden. Kann irgendein Informatiker das für sich behaupten in Sachen Kryptoalgorithmen?
Sorry für die dreiste Werbung für Quantenkrypto. Ich brenne einfach zu sehr für dieses Feld 😀
Hiermit eröffne ich die Wilde Jagd. Lasst eurer Phantasie freien Lauf und schreibt mir auf @sycramore bei Twitter
xoxo sycramore
Neueste Kommentare