Quantum Supremacy

[John Clark]

There is a rumor that a team of researchers at Google led by John Martinis have performed a calculation on a Quantum Computer in three minutes and 20 seconds that would have taken Summit, the most powerful conventional supercomputer in the world, 10,000 years to perform. The rumor started when a paper stating that was posted by the Google team, apparently accidentally, on a NASA website and then quickly taken down. It's not clear exactly what the calculation was about, they just said it “marks the first computation that can only be performed on a quantum processor". My guess is it was probably a weird function of some sort that would not be of much use to a scientist or engineer, but even so if true it would be a first proof of concept and be earthsharing. I suppose they want to check and recheck their work before they make a official announcement this important and that's why they took the article down.

 John K Clark 

[Alan Grayson]

On Saturday, September 21, 2019 at 6:23:18 AM UTC-6, John Clark wrote:

There is a rumor that a team of researchers at Google led by John Martinis have performed a calculation on a Quantum Computer in three minutes and 20 seconds that would have taken Summit, the most powerful conventional supercomputer in the world, 10,000 years to perform. The rumor started when a paper stating that was posted by the Google team, apparently accidentally, on a NASA website and then quickly taken down. It's not clear exactly what the calculation was about, they just said it “marks the first computation that can only be performed on a quantum processor". My guess is it was probably a weird function of some sort that would not be of much use to a scientist or engineer, but even so if true it would be a first proof of concept and be earthsharing. I suppose they want to check and recheck their work before they make a official announcement this important and that's why they took the article down.

What I don't understand is why a computer programmed to assume a superposition, say of two states, represents a system in both states simultaneously (which I find to be false for reasons previously stated), would speed up any calculation. Can anyone answer this question? AG 

 John K Clark 

[John Clark]

On Sat, Sep 21, 2019 at 8:29 AM Alan Grayson <agrays...@gmail.com> wrote:

> What I don't understand is why a computer programmed to assume a superposition, say of two states, represents a system in both states simultaneously (which I find to be false for reasons previously stated), would speed up any calculation. Can anyone answer this question? AG 

Well, if you're right about superposition then a Quantum Computer can't speed up a calculation, therefore if this rumor turns out to be true that would prove you are not right about superposition.

 John K Clark

 

[Alan Grayson]

My question is a conceptual one; why would assuming a superposition means what I earlier stated, speed up any calulation? AG 

 

[smitra]

On 21-09-2019 14:52, Alan Grayson wrote:
> On Saturday, September 21, 2019 at 6:40:50 AM UTC-6, John Clark wrote:
>
>> On Sat, Sep 21, 2019 at 8:29 AM Alan Grayson <agrays...@gmail.com>
>> wrote:
>>

>>> _> What I don't understand is why a computer programmed to assume

>>> a superposition, say of two states, represents a system in both
>>> states simultaneously (which I find to be false for reasons
>>> previously stated), would speed up any calculation. Can anyone

>>> answer this question? AG _

>>
>> Well, if you're right about superposition then a Quantum Computer
>> can't speed up a calculation, therefore if this rumor turns out to
>> be true that would prove you are not right about superposition.
>>
>> John K Clark
>
> My question is a conceptual one; why would assuming a superposition
> means what I earlier stated, speed up any calulation? AG
>

Richard Feynman who invented the conceptional idea of a quantum computer
had answered this question long before quantum algorithms that are used
today were invented. He simply argued that it the time it takes for a
classical computation to compute the properties of an interacting
quantum system with N degrees of freedom, increases exponentially as a
function of N. So, if a classical computer is running a particular
algorithm that can be mathematically shown to be equivalent to computing
a property of an N part quantum system, then you could just build that
quantum system and measure that property. One can then consider doing
that in a more practical way by constructing a universal quantum
computing device.

Saibal

[Alan Grayson]

What are you claiming; that a quantum computer isn't really designed to 

calculate anything, but rather simulates some quantum system? It's still

above my pay grade unfortunately. AG 

[smitra]

Once you get to a universal computing device the distinction doesn't
matter. I think David Deutsch was the one who showed how to get to a
universal quantum computer. Note that in the old days before we had
practical classical computers people used to numerically compute the
solution of differential equations by building an electric circuit
involving resistors, coils and condensers put together such that the
voltage or current at some point as a function of time would be
described by the same differential equation as the one they wanted to
solve.

Saibal

[spudb...@aol.com]

Please consider that for QC to succeed, to be supreme, it will have to generate many more successful operations per sec, then, digital computers. It the successful ops that matter, otherwise, we be praising D-Wave to the skies, lauding their multi-thousand entanglements. I am suspecting that the Martinis triumph was either in error, or, had been working on decryption. 

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv3prqzVNpzxuycCFzepa1P7Kt%3DTWLXbHs%2B6k4m2KGButQ%40mail.gmail.com.

[Lawrence Crowell]

Since quantum computers are in a superposition of various states a search down a branching tree, say a search along a maze, can be done in a superposition of states. This would appear to argue that a quantum computer can do an NP, nondeterministic polynomial or non-polynomial, problem in P time and space. Not quite, for in order to read the outcome there must be classical signals transmitted on state preparations and so forth. This means quantum computers are polynomial, but considered to be "bounded quantum polynomial." This means they are a considerable speed up, but not exponentially so.

What has me a little mystified is now they computed something for 3 minutes and 20 seconds. It would be an astounding breakthrough if the quantum computer ran continuously for that time. Decoherence will usually demolish a qubit within 10^{-5}sec, unless this employs some sort of quantum error correction code of a novel form. I suspect it ran the algorithms in time steps, where it ran for 10^{-6}sec, transferred to classical data that was used to prepare quantum states for the next quantum iteration and so forth.

LC

[Russell Standish]

It is rather easy to say that one's optimised algorithm using special
purpose hardware performs better than some naive implementation
running on a conventional computer. It is not so easy to show that it
beats the pants off all possible algorithm running on the conventional
computer.

For example, it is often the case that some simple algorithm can be
parallelised, and run many times faster on a parallel computer,
however that there is also a more complicated algorithm that is
inherently serial, but actually runs faster than the paralellised one.

I have a feeling that may have happened here. But I look forward to a
proper demonstration of quantum supremacy.


--

----------------------------------------------------------------------------
Dr Russell Standish Phone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellow hpc...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au
----------------------------------------------------------------------------

[John Clark]

On Sat, Sep 21, 2019 at 4:27 PM Lawrence Crowell <goldenfield...@gmail.com> wrote:

> Since quantum computers are in a superposition of various states a search down a branching tree, say a search along a maze, can be done in a superposition of states. This would appear to argue that a quantum computer can do an NP, nondeterministic polynomial or non-polynomial, problem in P time and space. Not quite, for in order to read the outcome there must be classical signals transmitted on state preparations and so forth. This means quantum computers are polynomial, but considered to be "bounded quantum polynomial." This means they are a considerable speed up, but not exponentially so.

I think that's a very reasonable assumption but it has not been proven, it hasn't even been proven that a conventional algorithm running on a conventional computer that would produce a exponential speedup does not exist; however very recently something interesting HAS been proven by Raz and Tal. This new result does not prove a quantum computer could solve all nondeterministic polynomial time problems in polynomial time but it does prove that even if, to virtually all mathematicians astonishment, it turned out that P=NP and even if we found an algorithm that could solve NP problems on a conventional computer in polynomial time there would STILL be a class of problems a conventional computers couldn’t solve efficiently but a quantum computer could. This new class of problems is very exotic and it's so new nobody knows yet if they are of fundamental interest in themselves or if they're interesting for no reason other than that a conventional computer can’t solve them but a Quantum Computer can.

Polynomial-time quantum algorithms can not be simulated by classical algorithms in polynomial-time 

John K Clark

[Jason Resch]

Some more details in this article:

https://fortune.com/2019/09/20/google-claims-quantum-supremacy/

Jason

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv06WBTrtG0GKhV6SpcQQrcxiAweEZ51uL7hVZjbq30LfQ%40mail.gmail.com.

[Philip Thrift]

I suppose all those with quantum programs ready to test, it's ready for you:

IBM’s new 53-qubit quantum ‘mainframe’ is live in the cloud

20 Sep 2019

IBM has boosted its growing stable of quantum computers with a new 53-quantum bit (qubit) device, the most powerful ever offered for commercial use.

Google announced a more powerful 72-qubit ‘Bristlecone’ model last year, but that was for its internal techies only. IBM’s, by contrast, feels significant because it can be used by absolutely anyone who can find a use for such a computer.

The new and still-to-be-named computer will sit in the company’s Quantum Computation Center in Poughkeepsie, New York State, which has recently turned into a hotbed for commercial development.

The facility also houses an array of older quantum computers, including one with 20 qubits (including the first Q System One launched in January), four with 5 qubits, and one with 14 qubits.

The involvement of Poughkeepsie is no coincidence – this is the heritage site where IBM built many of the mainframes that made its name synonymous with business computing.

Might quantum computers be on course to be the mainframes of the 21st century?

https://nakedsecurity.sophos.com/2019/09/20/ibms-new-53-qubit-quantum-mainframe-is-live-in-the-cloud/

@philipthrift

 

[Bruno Marchal]

That is not obvious at all, but has been very well illustrated by some quantum algorithm which does more quickly what we can conceive (perhaps wrongly) hard to do classical.

For example, with a quantum computer you can do 2^1000 different computations (but having the same length). Of course, you are not able to gain anything by looking a the result, but the quantum mechanism allows you to extract information from a Fourier transform made on all (2^1000) results, and this might give some information not accessible by a classical computer in any reasonable time, and speed some computation.  This is illustrated with the quantum algorithm to factorise large numbers (Shor). 

Mathematically, it is still an open problem if a quantum computer really speed-up the computations, but like with P = NP, most experts have few doubt that this is the case.

Now, Imo, just the double slit experiment, or the study of the hydrogen atom, shows that the superposition are physically real. It is the “one universe” idea which seems to me quite speculative, and just added for ideological coquetry. It is a form of 1p-plural solipsism. 

Bruno

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/9d4c2cb2-efc7-4664-860f-f7b68031128a%40googlegroups.com.

[John Clark]

On Mon, Sep 23, 2019 at 7:42 AM Bruno Marchal <mar...@ulb.ac.be> wrote:

> Mathematically, it is still an open problem if a quantum computer really speed-up the computations, but like with P = NP, most experts have few doubt that this is the case.

I think you mean P is not equal to NP, most mathematicians would be astonished if it turned out that P=NP .... but that doesn't mean it couldn't happen.

John K Clark

John K Clark

[Quentin Anciaux]

The sentence refers to "it is still an open problem if a quantum computer really speed-up the computations," not to P=NP. 

John K Clark

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv0YwDu4ZsG9mdVpPshCpbuBb0u-JMDttj_wQsw4LJrXtA%40mail.gmail.com.

--

All those moments will be lost in time, like tears in rain. (Roy Batty/Rutger Hauer)

[Alan Grayson]

What is P and NP? TIA, AG

[Lawrence Crowell]

Quantum computers do give a speed up, but it is not exponential in some way that permits P = NP. At least so far this has not been demonstrated. Quantum computing would maybe solve this as P = NP if the output could be done entirely in a nonlocal fashion, but quantum computing requires a classical communication of a result, or intermittent classical results, which spoils that hope. Quantum gravity may in some way come to the rescue, or at least expand the computability domain of quantum computing. We still though will have the issue of local operators and classical communications (LOCC).  The issue of P vs NP is very difficult as it turns out, and it appears to involve the Riemann zeta function.  There are potentially very deep results lurking here waiting to be found.

LC

[Bruno Marchal]

It is not too much badly explained here:

https://en.wikipedia.org/wiki/P_versus_NP_problem

Bruno

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/888621e9-e715-4a93-a293-faf51bbb1ab3%40googlegroups.com.

[Bruno Marchal]

On 23 Sep 2019, at 16:30, Alan Grayson <agrays...@gmail.com> wrote:

No problem. I meant P ≠ NP (hoping the “≠” pass correctly …).

But yes, P = NP would be astonishing for a vast majority of mathematicians.

Bruno

John K Clark

What is P and NP? TIA, AG

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/888621e9-e715-4a93-a293-faf51bbb1ab3%40googlegroups.com.

[Bruno Marchal]

On 23 Sep 2019, at 15:27, Quentin Anciaux <allc...@gmail.com> wrote:

Le lun. 23 sept. 2019 à 15:23, John Clark <johnk...@gmail.com> a écrit :

On Mon, Sep 23, 2019 at 7:42 AM Bruno Marchal <mar...@ulb.ac.be> wrote:

> Mathematically, it is still an open problem if a quantum computer really speed-up the computations, but like with P = NP, most experts have few doubt that this is the case.

I think you mean P is not equal to NP, most mathematicians would be astonished if it turned out that P=NP .... but that doesn't mean it couldn't happen.

John K Clark

The sentence refers to "it is still an open problem if a quantum computer really speed-up the computations," not to P=NP. 

That’s right too, actually. 

Bruno 

John K Clark

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv0YwDu4ZsG9mdVpPshCpbuBb0u-JMDttj_wQsw4LJrXtA%40mail.gmail.com.

--

All those moments will be lost in time, like tears in rain. (Roy Batty/Rutger Hauer)

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAMW2kAoAscdaVkBy0x9ZodrjuxiNK6k5Jz4%3D67-a4PVmSzHhMw%40mail.gmail.com.

[John Clark]

There is a excellent FAQ by Quantum Computer expert Scott Aaronson. Aaronson is noted for throwing cold water over claims of a breakthrough in his field, but not this time!  Aaronson is clearly excited, he compares Google's Quantum Computer to the Wright brothers 1903 flyer or Enrico Fermi's 1942 pile, the world's first nuclear reactor:

Scott’s Supreme Quantum Supremacy FAQ! 

[Bruno Marchal]

I follow well most of what Scott says on quantum computer Trump and Kirsten Gillibrand etc. 

He is wrong on Church’s thesis, but that is due to its implicit physicalist assumption, like so many, including Deutsch. He is just not doing theology, so it has no consequence for his physics, (and still less politics).

Bruno

John K Clark

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv14nnSJoYx2qto0y%2BWUTRQAW0-TAbi0Jf-tmDjEgGAa%2Bw%40mail.gmail.com.