Quantum Supremacy

[system]

“a model of computation may now be available that violates [the extended Church-Turing thesis]”

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[Marcel_Inf]

Quantum Supremacy
Heute erschien von vielen Google-Mitarbeitern und >= 30 Koautoren der Artikel „Quantum supremacy using a programmable superconducting processor“ (open-access PDF hier) in Nature. Sie schreiben:

@p. 509

The extended Church–Turing thesis formulated by Bernstein and Vazirani [55] asserts that any ‘reasonable’ model of computation can be efficiently simulated by a Turing machine. Our experiment suggests that a model of computation may now be available that violates this.

@Abstract

Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times—our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years.

Meinungen? (Jemand kann ja mal Prof. Wanka in der VL fragen! Hab BFS schon länger hinter mir :))

[rwanka]

---

@Marcel[Inf

Heute erschien von vielen Google-Mitarbeitern und >= 30 Koautoren der Artikel „Quantum supremacy using a programmable superconducting processor“ (open-access PDF hier) in Nature. Sie schreiben:

@p. 509

The extended Church–Turing thesis formulated by Bernstein and Vazirani [55] asserts that any ‘reasonable’ model of computation can be efficiently simulated by a Turing machine. Our experiment suggests that a model of computation may now be available that violates this.

Es geht um die Extension der Church-Turing-These, nämlich das von mir eingefärbte Wörtchen efficiently. In dem Aufsatz von Bernstein/Vazirani ist mit effizienten Simulationen durch Probabilistische Turingmaschinen gemeint:

@Bernstein/Vazirani

an efficient simulation is one whose running time is bounded by some polynomial in the running time of the simulated machine.

Es dreht sich also um den beweisbaren maximalen Zeitverlust in Abhängigkeit von der Eingabelänge in normalen Bits. Leider lassen Bernstein/Vazirani den Hinweis auf die Eingabelänge weg, weil das Messen in der Eingabelänge in der Komplexitätstheorie „Standard“ ist. Simulation umfaßt hier auch, daß die Turingmaschine jeden Lauf eines jeden Programms der simulierten Maschine effizient simulieren kann.

@Marcel[Inf

@Abstract

Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times—our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years.

Die Zahlen sind zwar, wenn sie denn stimmen (IBM hat ja bereits begründete Zweifel geäußert), beeindruckend. das Verhältnis von 200 Sekunden zu 10.000 Jahren ist ca. 6,342 · 10[sup]-10[/sup]. Würde diese Beschleunigung immer gelten, wäre der Zeitverlust einer Simulation auf einer Registermaschine 1,577 · 10[sup]9[/sup] = Θ(1). :-p

Daß die erweiterte Church-Turing-These damit hinfällig würde, sehe ich nicht. Das geht eben nicht durch ein Experiment. Man müßte z.B. ein Problem hernehmen, das mit Eingaben der Länge n, n beliebig, auf einem Quantencomputer in Zeit poly(n) gelöst werden kann, aber nicht durch eine, sagen wir ruhig, Registermaschine in Polynomzeit in n gelöst werden kann. Dann folgt, daß keine Simulation des Quantencomputers durch eine Turingmaschine im Bernstein/Vazirani-Sinn effizient sein kann, weil sie bei diesem einen Problem nicht effizient sein kann. Erst dann ist das oben markierte Wort jeden verletzt.

Das können die vielen Autoren ja man googlen.

Ich lasse mich natürlich gerne überraschen, aber solange keine mathematischen Beweise vorliegen, ist auch die erweiterte Church-Turing-These nicht widerlegt.

@Marcel[Inf

Meinungen? (Jemand kann ja mal Prof. Wanka in der VL fragen! Hab BFS schon länger hinter mir :))