Author Topic: Google claims to have reached quantum supremacy  (Read 1185 times)

0 Members and 1 Guest are viewing this topic.

Offline rfeecs

  • Frequent Contributor
  • **
  • Posts: 681
  • Country: us
Google claims to have reached quantum supremacy
« on: September 20, 2019, 10:44:39 pm »
https://www.technologyreview.com/f/614416/google-researchers-have-reportedly-achieved-quantum-supremacy/

From the FT article:
Quote
Google claims to have built the first quantum computer that can carry out calculations beyond the ability of today’s most powerful supercomputers, a landmark moment that has been hotly anticipated by researchers.

A paper by Google’s researchers seen by the FT, that was briefly posted earlier this week on a Nasa website before being removed, claimed that their processor was able to perform a calculation in three minutes and 20 seconds that would take today’s most advanced classical computer, known as Summit, approximately 10,000 years.

The researchers said this meant the “quantum supremacy”, when quantum computers carry out calculations that had previously been impossible, had been achieved.
 

Offline SilverSolder

  • Frequent Contributor
  • **
  • Posts: 978
  • Country: 00
Re: Google claims to have reached quantum supremacy
« Reply #1 on: September 21, 2019, 12:20:26 pm »
Is it available as an Arduino shield?
 
The following users thanked this post: tom66, nctnico, KL27x, Jacon, SiliconWizard

Online Bud

  • Super Contributor
  • ***
  • Posts: 3749
  • Country: ca
Re: Google claims to have reached quantum supremacy
« Reply #2 on: September 21, 2019, 12:24:18 pm »
Claimed by "google researchers", not verified by independent experts.  :=\
Facebook-free life and Rigol-free shack.
 
The following users thanked this post: Cyberdragon

Offline SiliconWizard

  • Super Contributor
  • ***
  • Posts: 4057
  • Country: fr
Re: Google claims to have reached quantum supremacy
« Reply #3 on: September 23, 2019, 02:49:22 pm »
Also just look at the "but, but" paragraph.

Supremacy my ass. :popcorn:
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #4 on: September 23, 2019, 04:28:39 pm »
I believe Google, just that they probably didn't use quantum particles to do the calculations.  With quantum particles there isn't much hope to scale up the number of qubits.

It is possible to run the same type of quantum algorithms, with the same speed advantages, using something very similar with analog computing techniques and true random noise.

Offline wraper

  • Supporter
  • ****
  • Posts: 10626
  • Country: lv
Re: Google claims to have reached quantum supremacy
« Reply #5 on: September 23, 2019, 04:33:30 pm »
It is possible to run the same type of quantum algorithms, with the same speed advantages, using something very similar with analog computing techniques and true random noise.
BS, maybe you heard about quantum analogue computing and made this nonsense conclusion.
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #6 on: September 23, 2019, 05:08:12 pm »
I'm currently working at building one.  I don't want to publish before seeing it running, just to be sure the idea is correct.  The hardware is nothing like million $$$ cryogenic devices or so.  Instead, it is made with COTS (commercial on the shelf) parts, almost hobby level hardware.

Also, I'm not the only one trying to run quantum algorithms with all their speed advantages, but without using quantum particles.   

This month I learned that there are at least two claims (that I know of) that they already built running prototypes, and it feels very frustrating.  So far, they seem to be using different techniques than mine, so there is still hope that I'll not be totally scooped.

Offline wraper

  • Supporter
  • ****
  • Posts: 10626
  • Country: lv
Re: Google claims to have reached quantum supremacy
« Reply #7 on: September 23, 2019, 05:16:50 pm »
I'm currently working at building one.  I don't want to publish before seeing it running, just to be sure the idea is correct.  The hardware is nothing like million $$$ cryogenic devices or so.  Instead, it is made with COTS (commercial on the shelf) parts, almost hobby level hardware.

Also, I'm not the only one trying to run quantum algorithms with all their speed advantages, but without using quantum particles.   

This month I learned that there are at least two claims (that I know of) that they already built running prototypes, and it feels very frustrating.  So far, they seem to be using different techniques than mine, so there is still hope that I'll not be totally scooped.
Non quantum computer cannot have quantum superposition which is the reason of their calculation speed. You simply cannot do vast number of computations simultaneously on usual hardware.
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #8 on: September 23, 2019, 05:52:09 pm »
Non quantum computer cannot have quantum superposition which is the reason of their calculation speed. You simply cannot do vast number of computations simultaneously on usual hardware.

That's exactly how I thought at first.  Now I think quite contrary.

Only when I went into details, looking at the hardware implementation of various types of existing quantum computers, I realized that it should be possible to implement the same functionality of qubits and quantum gates without using quantum particles.

Quantum superposition is not what makes quantum computing so special.  It appears to be so when looking at the formalism of quantum algorithms, but it's not the key element.  Of course, having this conclusions only on paper doesn't matter much.  They can still be wrong.  That's why I'm trying now to build a physical prototype, not just a software simulation, so to experimentally test those conclusions.
« Last Edit: September 23, 2019, 05:53:52 pm by RoGeorge »
 

Offline SilverSolder

  • Frequent Contributor
  • **
  • Posts: 978
  • Country: 00
Re: Google claims to have reached quantum supremacy
« Reply #9 on: September 23, 2019, 08:41:16 pm »
Non quantum computer cannot have quantum superposition which is the reason of their calculation speed. You simply cannot do vast number of computations simultaneously on usual hardware.

That's exactly how I thought at first.  Now I think quite contrary.

Only when I went into details, looking at the hardware implementation of various types of existing quantum computers, I realized that it should be possible to implement the same functionality of qubits and quantum gates without using quantum particles.

Quantum superposition is not what makes quantum computing so special.  It appears to be so when looking at the formalism of quantum algorithms, but it's not the key element.  Of course, having this conclusions only on paper doesn't matter much.  They can still be wrong.  That's why I'm trying now to build a physical prototype, not just a software simulation, so to experimentally test those conclusions.

Superpositioning can of course be (slowly) simulated by a digital computer,  as we all know.  Are you saying you think it can be more quickly simulated on an analogue computer - perhaps some type of mesh architecture?

It is in any case always going to be slower than "the real thing" - no?
 

Offline rfeecs

  • Frequent Contributor
  • **
  • Posts: 681
  • Country: us
Re: Google claims to have reached quantum supremacy
« Reply #10 on: September 23, 2019, 08:49:20 pm »
Only when I went into details, looking at the hardware implementation of various types of existing quantum computers, I realized that it should be possible to implement the same functionality of qubits and quantum gates without using quantum particles.

I read something like that recently:
"'Poor man's qubit' can solve quantum problems without going quantum"
https://phys.org/news/2019-09-poor-qubit-quantum-problems.html
 

Offline rfeecs

  • Frequent Contributor
  • **
  • Posts: 681
  • Country: us
Re: Google claims to have reached quantum supremacy
« Reply #11 on: September 23, 2019, 08:57:43 pm »
This video may be what the Google paper is about.  (I found turning on closed captioning was helpful):
https://youtu.be/gylmjTOUfCQ

This sounds something like:
   I will prove that my quantum computer is superior to a conventional computer at solving at least one specific problem... and that problem is simulating a quantum computer.  :o
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #12 on: September 23, 2019, 09:29:22 pm »
The YouTube video is from March, wasn't the retracted announcement of quantum supremacy from last week this month?

Yes the phys.org you posted is one recent announcement, from Purdue University, the previous one I know is from Linköping University:
https://phys.org/news/2019-09-poor-qubit-quantum-problems.html
https://phys.org/news/2019-09-quantum.html

And then is the retracted Google announcement, that nobody knows what it is about.

It was quite a sour surprise to see them popping all of a sudden, in the same month.   :-\

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #13 on: September 23, 2019, 11:06:28 pm »
It is in any case always going to be slower than "the real thing" - no?

I think it will have the same speed as a quantum computer.

Same speed, and I'm not even considering the unfairness everybody is using right now to compare digital computers with quantum computers.  To detail what I mean by unfairness, when the big-O is calculated for a classic algorithm, they are considering only 1 bit questions, while for quantum algorithms big-O is calculated for questions about all the qubits at once.  I don't know why is this practice, is hard for me to believe that nobody really seen this unfairness.

For example, when the "guess my number" big-O is calculated, usually it is used the half-split method, so the question put to the "oracle" is "is your number in the first or in the second half of the given interval", and the oracle respond with yes/no, so only one bit, hence O(log n), while for the quantum algorithm they ask the oracle "what number did you pick", and the "oracle" answers with all the qubits at once by simply telling the number I chose, so the secret number is always guessed in one step, so O(1).  Very unfair way to question the oracle, if you ask me.  A fair thing would have been to use the parallelism for classic algorithm, too, not only for the quantum algorithm, and then the classic computer would have responded in 1 step, same as the quantum one.



At minute 27:27 there is a drawing of the quantum algorithm "guess my number", where the secret number (hardcoded) is 1101.  If instead of qubits we use normal bits, and instead of quantum CNOT gates we use classical XOR gates, then either the quantum or the classical computer will guess the secret number in one try, with big-O=1.

This suggests that there might be no advantage at all for quantum computers, but this is a software research and at the moment I'm interested in hardware.

Does anybody else noticed the unfairness when calculating big-O for the classical algorithm, or am I losing something obvious?
« Last Edit: September 23, 2019, 11:12:30 pm by RoGeorge »
 

Online Marco

  • Super Contributor
  • ***
  • Posts: 4551
  • Country: nl
Re: Google claims to have reached quantum supremacy
« Reply #14 on: September 24, 2019, 03:23:44 am »
I googled for the paper so you don't have to.
 
The following users thanked this post: RoGeorge, imo

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #15 on: September 24, 2019, 07:58:35 am »
Thank you for finding the paper.  :-+
Looks like they used a quantum computer indeed, their "Sycamore" processor.

What I don't get is if that is a scientific paper or a journal article.  Also I don't get it why?  Doing a research just to be able to say "Quantum Supremacy" seems to me like writing "First!" in the comments section of a YouTube video.   ;D  Must be something else I am missing.

Anyway, why did they take the announcement back?

Online maginnovision

  • Super Contributor
  • ***
  • Posts: 1316
  • Country: us
Re: Google claims to have reached quantum supremacy
« Reply #16 on: September 24, 2019, 08:00:12 am »
Maybe because it was a machine built to solve a problem rather than a machine you could make solve problems. That seemed to be IBM's issue with it.
 

Offline golden_labels

  • Regular Contributor
  • *
  • Posts: 142
  • Country: pl
Re: Google claims to have reached quantum supremacy
« Reply #17 on: September 24, 2019, 09:23:40 am »
People forget the history so easily!

Do you remember magnetism and then electricity? When they were very young? Everything was “magnetic” or “electric”, and that was widesread in quackery too. This is the same phenomenon we’re observing now with buzzwords like “quantum” and “AI”.

I believe Google might have created what they claim they did. There is no reason to lie for the very same reason US had no reason to fake moon landing: just like NASA had all the means of sending astronauts to the moon in 1969, quantum computing alone is quite boring news in 2019. Both just had to use the resources very well to achieve some new goal, which no one else have reached before. The catch is that Google hasn’t made anything extremely new. They made it “quantum” to bring media attention. At the same time they’ve probably progressed in data mining algorithms much more, but who wants to listen about crunching numbers, pages of maths and being 1.004% better than foo?

If the general public — and investors and speculators are the general public — doesn’t have a slightest idea about some topic, you can make them attach any meaning to it in their brains (in this case: “modern”, “faster”, “better”) and then use the term to invoke the corresponding feelings. It bears little resemblance to what is actually offered by given solution, but it sound good. And all the “buts” are needed, but they shouldn’t be seen as something negative. They’re inherent to the technology. Quantum computing will solve many problems much faster, but no one ever promised it will solve everything faster. There are problems, and most of those faced by an average person fall into this category, which are linear in their nature and using quantum computing will not make them magically faster. No, you will not get a billion FPS in your favourite game if you would run it on a quantum computer. ;)

RoGeorge:
Can you post a proof that, while resources grow linearly, the size of problems your computing method can solve grows at least exponentially with fast falling error probability? If not, you are missing something.
Worth watching: Calling Bullshit — protect your friends and yourself from bullshit!
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #18 on: September 24, 2019, 09:32:25 am »
Maybe because it was a machine built to solve a problem rather than a machine you could make solve problems. That seemed to be IBM's issue with it.

My understanding is that the Sycamore chip is a generic quantum computer, and it can run various other quantum algorithms.  For that paper they program it with a specific quantum algorithm, one that will be particularly difficult to implement with a classic computer.

It is very hard for me to believe that Google will take the time to develop the Sycamore chip just to say "First!" in quantum supremacy.

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #19 on: September 24, 2019, 02:20:16 pm »
RoGeorge:
Can you post a proof that, while resources grow linearly, the size of problems your computing method can solve grows at least exponentially with fast falling error probability? If not, you are missing something.

Not exactly a formal proof, but I can show an example that highlights why the computing complexity in terms of big-O analysis is the wrong question to ask.

Let's play again the "guess my secret number", this time with classical hardware only.  Somebody pick a "secret" number, in the range 0..255.  Let's try to find the secret number.

One approach will be to start asking one by one about each number:
- Is it 0?
- No.
- Is it 1?
- No.
- Is it 2?
- No,
... And so on until we find the "secret" number.  This algorithm will find the secret number in at most 256 steps.  In computer science, this algorithm is said to be be of a complexity of O(n), so at most 256 steps in our example

Another approach, much faster, is the so called "cut in half" method, AKA binary search.  Things go like this:
- Is it bigger than 127?
- No.
- Is it bigger than 63?
- Yes.
... And so on until we find the secret number.  This algorithm is said to have a complexity of O(log n), so in at most 8 steps for our example, it is guaranteed we will find the "secret" number.

OK.  Pretty boring so far.  Now, let's take a step back and see what we were really doing in the last algorithm.  In fact, we were asking for the secret number bit by bit.  Asking if the number was bigger than 127 is equivalent of saying "tell me the most significant bit of the secret number".  So, the binary search algorithm can be, as well, written like this:
- Tell me the first (most significant) bit!
- 0
- Tell me the second bit!
- 1
... and so on, until we get all the 8 bits of the "secret" number.

OK.  So what?  Well, there is yet another algorithm that is guaranteed to solve our problem in exactly one step, so O(1).  This best possible algorithm works like this:
- Tell me the secret number!   ;D
- 75.

Problem solved in one step.  Now, why we don't "ask" our classical computers just "tell me the darn answer", and solve any algorithm in one step?

The answer is trivial, but we were "trained" to disregard it.  Any classical computer is a 1 bit serial machine, AKA a Turing Machine.  Essentially, a classic computer executes everything step by step, with a width of 1 bit.  Yes, we do some tricks and now we all have 64 bits computers, but note that this 64 is a fixed number, no matter what algorithm we are running.  We can not truly adjust the number of parallel bits processing according to the solutions space of each algorithm.  We are doing the best we can we those 64 we have.  64 bits is better than a 1 bit Turing machine, but essentially it is still a serial machine.

What I am trying do show here is that the O(log n) limitation comes from the topology of current classical computers: they are serial machines, not parallel machines.



Now, even if it were to have computers where the width of a word can be adjusted upon wish, according to each algorithm, we still couldn't be as fast as an analog computer, or quantum one.

In fact, we already have the technology for adjustable width parallel digital computer in the form of FPGAs, so why the digital computer with a serial architecture is the king, at not the parallel computer?  Because parallel digital computing doesn't scale well with big number of bits, while the serial one can scale up pretty well, but only up to to a point.  From that point on, we realize that our serial architecture can not cope with some algorithms that tend to have a nasty big-O.

To conclude:

1.  For now we have the following technologies:
- one bit serial Turing machine
- a few bits (64) parallel machine, but the architecture is still a serial
- other tricks to achieve adjustable width parallelism (yet still digital), e.g. distributed computing, multicore, etc.
- purely parallel digital machines, like a FPGA
- then there is analog computing and quantum computing

2.  The problems where the number of steps for a given algorithm escalates too fast with big numbers might be mitigated by using parallel algorithms instead of serial algorithms.

3.  To mellow down the number of steps even more, instead of digital algorithms with only 2 states (0/1) per bit, we can try analog algorithms, where the number of states "encoded" by each "analog bit" is virtually infinite.  This is helpful because analog algorithms can operate now with a much broader range of values, virtually infinite number of values for each "analog bit".  In practice, it is not possible to get infinite resolution from an analog value, but still, it's better than having only 2 possible values per bit, as in the 0/1 digital computing.  Note that classical analog computing operates with contiguous values situated in R (real numbers).

4.  Then, there is quantum computing, where each qubit value is a contiguous range of values situated in C (complex numbers),  until the qubit is "collapsed" into a 0/1 at the final step of a computation (a contiguous C qubit is turned into a digital 0/1 bit by the measurement gate, which is always the last gate in any quantum algorithm).

In the end, the speed of solving a computation problem is given by a combination between algorithm type, numbers type (digital, real or complex) and computer architecture type (serial or parallel).  Ultimately, the proper combination between all these possible speeding factors is a mix dictatet by the availability technologies.

Offline SilverSolder

  • Frequent Contributor
  • **
  • Posts: 978
  • Country: 00
Re: Google claims to have reached quantum supremacy
« Reply #20 on: September 24, 2019, 05:32:26 pm »
I get the sense that understanding quantum computing requires some kind of mental leap - it is not explainable in terms of classic computer science (or analog electronics)?

Each qubit is essentially in all possible states at the same time...   hard to implement when you're a dimension or two short of a dollar!
 

Offline SiliconWizard

  • Super Contributor
  • ***
  • Posts: 4057
  • Country: fr
Re: Google claims to have reached quantum supremacy
« Reply #21 on: September 24, 2019, 05:39:24 pm »
And then, there's the quantum entanglement.
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #22 on: September 25, 2019, 04:47:26 am »
I get the sense that understanding quantum computing requires some kind of mental leap - it is not explainable in terms of classic computer science (or analog electronics)?

Each qubit is essentially in all possible states at the same time...   hard to implement when you're a dimension or two short of a dollar!

A classic computer and a quantum computer doesn't have much in common.  It's like a crocodile and an airplane.  They both can "float" (calculate) except that one is swimming in a river and the other is flying in the sky.

A qubit is NOT in all the possible states at the same time.  That would be like saying a coin is both head and tail at once, which is incorrect.

Qubit.  You can visualize a qubit like an arrow anchored to a fixed point, but it can rotate freely around that point.  It's called a Bloch sphere.
https://en.wikipedia.org/wiki/Bloch_sphere

Entanglement is when you align the vectors of two or more Bloch spheres.

Superposition is when the vector in a Bloch sphere is oriented other than straight up or down.

A quantum gate "rotates" the Bloch sphere for a certain angle and in a certain direction, depending on the type of the quantum gate, or sometimes is "mirroring" the sphere.  Once you made yourself familiar with the Bloch sphere, you can open this webpage and run an example or build your own quantum circuit
https://algassert.com/quirk

Quirk runs in a normal webpage, nothing to install, and has "live" visualization of the intermediary values of the qubits at each step of the quantum algorithm/circuit.

Quirk is a quantum computer simulator, if you want a real quantum computer, you can make a free account to IBM-Q, and play with your own quantum circuits for free, either in simulation, or as a run on a real quantum computer.
https://www.ibm.com/quantum-computing/

Also, you need to FORGET about the cursed expressions like "Schrödinger's cat" and "spooky action at a distance".  Those are just wrong words used by journalist to confuse people and create hype.

Also, "quantum teleportation" is not teleportation in the sens that one object disappear from where it is now , then appears later in some other place.  "Quantum teleportation" is NOT teleportation.

One last thing, the formalism of qubits and quantum gates and quantum circuits stays the same between various types of quantum computers, but the hardware of quantum computers varies widely.  It's like C language stays the same either on paper, on a microcontroller or on multiprocessor server.

The hardware of a quantum computer can be made in many ways, either with trapped ions, or with photons, or Josephson junctions, or phonons, or some other crazy construction.  Also, to run a quantum computer you will need to control those ions/photons/junctions/whatever, so you will also need classic computer/s to "drive" the hardware of a quantum computer.
« Last Edit: September 25, 2019, 05:29:08 am by RoGeorge »
 

Online imo

  • Super Contributor
  • ***
  • Posts: 2270
  • Country: 00
Re: Google claims to have reached quantum supremacy
« Reply #23 on: September 25, 2019, 06:22:31 am »
It would be great if somebody with experience with the quirk webpage simulator would create a new topic, in for example General computing section (ie called "Quantum computing basics") and create an example with explanation on how to play with the simulation (or provides some hints how to proceed with those examples there).
 ::)
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #24 on: September 25, 2019, 06:57:32 am »
Quirk has instructions of how to use it https://github.com/Strilanc/Quirk/wiki/How-to-use-Quirk and a short video.

Offline SiliconWizard

  • Super Contributor
  • ***
  • Posts: 4057
  • Country: fr
Re: Google claims to have reached quantum supremacy
« Reply #25 on: September 25, 2019, 03:39:19 pm »
The name "Quirk" seems to have been wisely chosen here. ;D
 

Offline RandallMcRee

  • Frequent Contributor
  • **
  • Posts: 378
  • Country: us
Re: Google claims to have reached quantum supremacy
« Reply #26 on: September 25, 2019, 04:18:50 pm »
RoGeorge:
Can you post a proof that, while resources grow linearly, the size of problems your computing method can solve grows at least exponentially with fast falling error probability? If not, you are missing something.

Not exactly a formal proof, but I can show an example that highlights why the computing complexity in terms of big-O analysis is the wrong question to ask.

Let's play again the "guess my secret number", this time with classical hardware only.  Somebody pick a "secret" number, in the range 0..255.  Let's try to find the secret number.

One approach will be to start asking one by one about each number:
- Is it 0?
- No.
- Is it 1?
- No.
- Is it 2?
- No,
... And so on until we find the "secret" number.  This algorithm will find the secret number in at most 256 steps.  In computer science, this algorithm is said to be be of a complexity of O(n), so at most 256 steps in our example

Another approach, much faster, is the so called "cut in half" method, AKA binary search.  Things go like this:
- Is it bigger than 127?
- No.
- Is it bigger than 63?
- Yes.
... And so on until we find the secret number.  This algorithm is said to have a complexity of O(log n), so in at most 8 steps for our example, it is guaranteed we will find the "secret" number.

OK.  Pretty boring so far.  Now, let's take a step back and see what we were really doing in the last algorithm.  In fact, we were asking for the secret number bit by bit.  Asking if the number was bigger than 127 is equivalent of saying "tell me the most significant bit of the secret number".  So, the binary search algorithm can be, as well, written like this:
- Tell me the first (most significant) bit!
- 0
- Tell me the second bit!
- 1
... and so on, until we get all the 8 bits of the "secret" number.

OK.  So what?  Well, there is yet another algorithm that is guaranteed to solve our problem in exactly one step, so O(1).  This best possible algorithm works like this:
- Tell me the secret number!   ;D
- 75.

Problem solved in one step.  Now, why we don't "ask" our classical computers just "tell me the darn answer", and solve any algorithm in one step?

The answer is trivial, but we were "trained" to disregard it.  Any classical computer is a 1 bit serial machine, AKA a Turing Machine.  Essentially, a classic computer executes everything step by step, with a width of 1 bit.  Yes, we do some tricks and now we all have 64 bits computers, but note that this 64 is a fixed number, no matter what algorithm we are running.  We can not truly adjust the number of parallel bits processing according to the solutions space of each algorithm.  We are doing the best we can we those 64 we have.  64 bits is better than a 1 bit Turing machine, but essentially it is still a serial machine.

What I am trying do show here is that the O(log n) limitation comes from the topology of current classical computers: they are serial machines, not parallel machines.




Sorry, no.
All you have done is to fool yourself into thinking that Turing machines somehow dictate computer architecture. They are a mathematical construct that serves to illustrate, mathematically, that anything a turing machine can do, a parallel machine can do. Further, anything a parallel machine can do also a turing machine can do. They are equivalent in terms of the problems they can solve. You need to digest the implications of this.

https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

Now, that says nothing about how long it takes. That is a virtue. The arguments based on turing machines attain, therefore a universality and freedom from technology. So, yes, of course, you can build things faster than a turing machine, that is what intel, nvidia etc. make a living doing. That misses the point--its about the fundamental limits of computation, not the speed of computation.

So, to get back to your example. Sounds like a SAR ADC algorithm. Your last algorithm works for 8 bits--we need 256 comparator blocks....now lets scale up to 64. Ooops we need 2^^64, its not do-able. It does not scale.

So, yeah, I *was* taught that this would not work.
 

Offline MyHeadHz

  • Regular Contributor
  • *
  • Posts: 152
  • Country: us
Re: Google claims to have reached quantum supremacy
« Reply #27 on: September 25, 2019, 04:28:11 pm »
RoGeorge:
Can you post a proof that, while resources grow linearly, the size of problems your computing method can solve grows at least exponentially with fast falling error probability? If not, you are missing something.

Not exactly a formal proof, but I can show an example that highlights why the computing complexity in terms of big-O analysis is the wrong question to ask.

Let's play again the "guess my secret number", this time with classical hardware only.  Somebody pick a "secret" number, in the range 0..255.  Let's try to find the secret number.

One approach will be to start asking one by one about each number:
- Is it 0?
- No.
- Is it 1?
- No.
- Is it 2?
- No,
... And so on until we find the "secret" number.  This algorithm will find the secret number in at most 256 steps.  In computer science, this algorithm is said to be be of a complexity of O(n), so at most 256 steps in our example

Another approach, much faster, is the so called "cut in half" method, AKA binary search.  Things go like this:
- Is it bigger than 127?
- No.
- Is it bigger than 63?
- Yes.
... And so on until we find the secret number.  This algorithm is said to have a complexity of O(log n), so in at most 8 steps for our example, it is guaranteed we will find the "secret" number.


FYI, that method is simply called batch testing or group testing (generally depending on whether you are testing non-humans or humans).  The story of the development and implementations of the technique during WWII is a worthy rabbit hole if you are ever curious.

Dr. Dorfman's original paper (PDF, not pay-walled) is quite short and easy to digest, but goes into the practical statistical basics you need for planning and implementation of the technique. 

This is Wikipedia's page on the method and some history.
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #28 on: September 25, 2019, 05:12:33 pm »
The name "Quirk" seems to have been wisely chosen here. ;D

Quirk itself is very easy to use and intuitive, just drag and drop gates or indicators to those lines, and the vizualization of the results is the best:  the circuit is always live, with Bloch spheres animated even during editing a circuit.  Couldn't ask for more.  :-+

What makes it look complicated is the symbols for quantum gates and displays.  Those are symbols similar with gates or flip-flops from digital schematic diagrams, or transistors, resistors and so on in analog electronic schematics.

A quantum circuit starts from the most left side, and goes to the right side following those lines between the two grey areas named "Toolbox".  Quantum gates are "interpreted" from left to right, step by step (a step is a full column of gates on all the available lines) like the musical notes on musical scores.  Each line correspond to a qubit.

At the most left side of the quantum circuit are the initial values.  A quantum circuit always starts with all the qubits reset to "0", which in quantum notation is written as "|0>".  This "|0>" is called the bra-ket style notation.
https://en.wikipedia.org/wiki/Bra%E2%80%93ket_notation
Happily, in Quirk the initial |0> value can be easily changed by clicking on it, which is very good for situation where one want to see "what if" instead of |0>, this qubit is made |1>, or maybe something else.

All the qubits together form a register, same as bits that are processed together form a register (or word) in a classical computer.

You can think about a quantum algorithm flowing like a "signal" from left to right, along those line, at each step passing through a new column of gates.

The number of parallel lines (the width of the quantum register) is adjusted automatically by Quirk if you drag a gate lower than the already existing lines.

To delete a quantum gate, simply drag and drop it outside of the circuit.  Anywhere along the signal path can be inserted "Displays".  "Bloch" is one of the nicest Display, very useful to understand or debug a quantum circuit.  Displays are similar with voltage or current probing in LTspice or similar.

In real life, it wouldn't be possible to probe a quantum circuit somewhere along the signal path, that will completely destroy the quantum state.  However, this is a simulation, and we can use a Display wherever we like.  In real life, once you "read" the state of a qubit by a measurement process, it's game over, the state of the measured qubit collapses to either a "0" or a "1".

Note that at the right side of the signal paths, there are by default some displays attached, like a template, so we don't have to add it manually each time we want to look at the results.  Usually, any quantum circuit ends with a "measurement gate" on each qubit we want to read as a result.

Now, the tricky part is what each type of gates is doing, and how they rotate or mirror the qubits.  That can be find online by Googling "quantum gates", or starting from https://en.wikipedia.org/wiki/Quantum_logic_gate

If you just want to see a nice yet very simple and live animated example, click on the "Quantum Teleportation" example link (from the inside of the Quirk webpage) https://algassert.com/quirk
An animated quantum circuit should appear in Quirk.  On the first line, is the bit we want to "quantum teleport", or the "message".  On the last line is the qubit "received".

If you look at the first and second animated Bloch spheres, you can see the green dots are moving the same way (they are both moving according to the "message").  That's "quantum teleportation", which means rather to "copy" then to "teleport" the state from the first qubit into the fifth qubit.   ;D
« Last Edit: September 25, 2019, 05:20:51 pm by RoGeorge »
 
The following users thanked this post: imo

Online imo

  • Super Contributor
  • ***
  • Posts: 2270
  • Country: 00
Re: Google claims to have reached quantum supremacy
« Reply #29 on: September 25, 2019, 05:30:50 pm »
I spent some time starring at the examples, especially at the Quantum Fourier Transform.
I like the graphics at the right side.
I changed the inputs, and watched the results.
I have no idea what it does, what the input could be and what the results should be..
 :-//

PS: I have a gut feeling that when someone will define a simple example of a problem to solve, shows the quirk circuit and interprets the result, I am in  :D
« Last Edit: September 25, 2019, 05:47:35 pm by imo »
 

Offline RoGeorge

  • Super Contributor
  • ***
  • Posts: 1914
  • Country: ro
Re: Google claims to have reached quantum supremacy
« Reply #30 on: September 25, 2019, 06:41:42 pm »
You need to read about quantum gates first.  Without understanding what each gate does, there is no chance to understand a quantum schematic (AKA quantum algorithm).  You don't need to learn all types shown by Quark, but at least CNOT (Controlled NOT), Hadamard and Pauli gates, the ones from the 3rd group in the upper toolbar, named "Half Turns".

Probably the most simple circuit is to entangle two qubits, that would be a circuit with 2 gates, a Hadamard and a CNOT gate.

To understand quantum gates, at some point you will need to understand the bra-ket notation, probably it might require some linear algebra (arrays) with complex numbers, too.

Also, some basic notions about probabilities (most of the quantum algorithm does not return the result after a single run, like a classic algorithm returns, quantum algorithms are usually run hundreds and hundreds of times, and the results are "read" as a statistics of all the runs).

There are all kind of tutorials online.  See which one suits you better.  Anyway, the whole process won't be something you can learn in a weekend.  It will take longer than that.  Most productive way will be to search for some free online classes from a university, there are many.

See if this one suits you:
"Quantum computing for the determined"
https://www.youtube.com/playlist?list=PL1826E60FD05B44E4
which are Quantum Computing 101 Lessons by Michael Nielsen
https://www.youtube.com/user/mnielsencourses

Another path to learn will be to start with quantum mechanics and then go into quantum computing.  It depends if you are more inclined to math or to physics.
« Last Edit: September 25, 2019, 06:53:48 pm by RoGeorge »
 
The following users thanked this post: imo


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf