Mein Lieblingssatz in der Komplexitätstheorie ist der Zeithierarchiesatz. Dies geschah jedoch 1965. Ich wollte dann wissen, ob es etwas Ähnliches für Quantum Computing gibt. Wenn nicht, welche Personen / Gruppen arbeiten in dieser
Was ist die Zeitkomplexität (nicht die Abfragekomplexität) von Grovers Algorithmus? Es scheint mir klar , dass es , da es Iterationen und jede Iteration erfordert die Verwendung des Reflexionsbetrieb wiederum die Zeit in Anspruch nimmt Verwendung eines beliebigen Standardsatzes von...
In der Quanteninformationstheorie wird der Abstand zwischen zwei Quantenkanälen häufig mit der Diamantnorm gemessen. Es gibt auch eine Reihe von Möglichkeiten, um den Abstand zwischen zwei Quantenzuständen zu messen, z. B. den Spurabstand, die Wiedergabetreue usw. Der Jamiołkowski-Isomorphismus...
Im Grunde bin ich Physiker, und deshalb finde ich One-Way-Quantum-Computing brillant. Insbesondere das auf Graph State Measurement basierende Quantum Computing (MBQC) ist eine wirklich gute Entwicklung in der Quantum Computing-Forschung, wie sie von Raussendorf & Briegel entwickelt wurde . Man...
Es ist bekannt, dass Quantencomputer hinsichtlich der Komplexität von Abfragen strikt leistungsfähiger sind als ihre klassischen Gegenstücke . Gibt es andere (natürliche oder künstliche) Modelle, die in Bezug auf die Komplexität von Abfragen streng zwischen dem Quanten- und dem Klassischen liegen?...
Welche Universitäten haben einen starken Lehrplan für Quantencomputer und bieten irgendeine Art von Quantencomputer / Informationskursen / Forschung an? Das Ziel hier ist es, eine nützliche Liste für jemanden zu sammeln, der ein Studium in diesen Bereichen in Betracht zieht, und nicht zu...
Kürzlich haben Watrous et al. Bewiesen, dass QIP (3) = PSPACE ein bemerkenswertes Ergebnis ist. Das war, gelinde gesagt, ein überraschendes Ergebnis für mich und hat mich zum Nachdenken angeregt ... Ich fragte mich, was wäre, wenn Quantencomputer durch klassische Computer effizient simuliert werden...
Ist es möglich, algorithmisch zu testen, ob eine berechenbare Zahl rational oder ganzzahlig ist? Mit anderen Worten, könnte eine Bibliothek, die berechenbare Zahlen implementiert, die Funktionen bereitstellen, isIntegeroder isRational? Ich vermute, dass es nicht möglich ist und dass dies irgendwie...
Wenn es bei der klassischen Berechnung aus Neugier um Permutationsmatrizen und beim Quantencomputing um Einheitsmatrizen geht (von denen die Permutationsmatrizen eine Untergruppe sind), gibt es dann ein Rechenparadigma, das über die Einheitsmatrizen
Nehmen wir an, wir haben einen universellen Quantencomputer gebaut. Abgesehen von sicherheitsrelevanten Problemen (Kryptografie, Datenschutz, ...), welche aktuellen Probleme der realen Welt können davon profitieren? Ich interessiere mich für beides: Probleme, die derzeit für einen praktischen...
Die Quantenberechnung ist ein aktives Forschungsgebiet, das darauf abzielt, die Quantenphysik (z. B. Quantenverschränkung) zu nutzen, um die Leistungsfähigkeit von Computern zu verbessern (ändert nichts an der These von Church-Turing ). Was sind die wichtigsten Experimente zur Demonstration der...
Die negative Gegnermethode ( ) ist eine SDP, die die Komplexität von Quantenabfragen charakterisiert. Es ist eine Verallgemeinerung der weit verbreiteten Gegner-Methode ( A D V ) und überwindet die beiden Hindernisse, die der Gegner-Methode im Wege standen:A D V±ADV±ADV^\pmA D VADVADV Die...
Eine Sache, die Quantencomputer tun können (möglicherweise sogar mit nur BPP + log-tiefen Quantenschaltungen), ist die Fourier-Transformation einer Booleschen bewerteten Funktion in P zu approximieren.± 1±1\pm 1 Hier und unten, wenn ich über das Abtasten der Fourier-Transformation spreche, meine...
Wie allgemein bekannt ist, kann PARITÄT nicht in Schaltkreisen mit konstanter Tiefe in Polygröße durchgeführt werden, und tatsächlich erfordern Schaltkreise mit konstanter Tiefe die EXP-Anzahl von Gattern. Was ist mit QUANTUM-Schaltungen? a) Kann PARITÄT mit einer Quantenschaltung durchgeführt...
Die zeitbegrenzte Quantenberechnung ist offensichtlich sehr interessant. Was ist mit weltraumgebundener Quantenberechnung? Ich kenne viele interessante Ergebnisse für die Quantenberechnung mit sublogarithmischen Raumgrenzen und verschiedenen Arten von Quantenautomatenmodellen. Andererseits wurde...
(auch hier gefragt , keine Antworten) Ein -Quantenexpander ist eine Verteilung über die Einheitsgruppe mit der Eigenschaft, dass: a) , b) , wobei \ mu_H das Haar-Maß ist. Wenn wir anstelle von Verteilungen über Unitaries Verteilungen über Permutationsmatrizen betrachten, ist es nicht schwer zu...
In Mike und Ikes "Quantenberechnung und Quanteninformation" wird der Grover-Algorithmus ausführlich erklärt. In dem Buch und in allen Erklärungen, die ich online für Grovers Algorithmus gefunden habe, scheint es jedoch keine Erwähnung zu geben, wie Grovers Orakel aufgebaut ist, es sei denn, wir...
Wir betrachten häufig Komplexitätsklassen, bei denen wir in Bezug auf den Platz, den unsere Turing-Maschine verwenden kann, begrenzt sind, zum Beispiel: oder NSPACE ( f ( n ) ) . Es scheint, dass es in der frühen Komplexitätstheorie viel Erfolg mit diesen Klassen wie dem Raumhierarchiesatz und dem...
Kurze Frage. Was ist die Rechenleistung von "Quanten" -Schaltungen, wenn wir nicht einheitliche (aber immer noch invertierbare) Gatter zulassen und vom Ausgang verlangen, dass er mit Sicherheit die richtige Antwort gibt? Diese Frage handelt in gewissem Sinne davon, was mit der Klasse passiert, E Q...
Die Komplexitätsklasse BQP entspricht polynomiellen Zeitquanten-Subroutinen, die klassische Eingaben aufnehmen und eine probabilistische klassische Ausgabe ausgeben. Der Quantenratschlag modifiziert diesen, um Kopien einiger vorbestimmter Quantenratschlagzustände einzuschließen, jedoch mit...