Google claims to have reached quantum supremacy

[SiliconWizard]

The name "Quirk" seems to have been wisely chosen here.

[RandallMcRee]

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!   
- 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.

[MyHeadHz]

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.

[RoGeorge]

The name "Quirk" seems to have been wisely chosen here.

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.   

[iMo]

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 

[RoGeorge]

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.

[RoGeorge]

https://www.technologyreview.com/f/614416/google-researchers-have-reportedly-achieved-quantum-supremacy/

From the FT article:

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.

Chinese quantum computer just upped the bar from 53...54 qubits (Google's Sycamore) to 56...66 qubits (Zuchongzhi).

Not very sure how the qubits are counted, it varies.   

Report:  https://phys.org/news/2021-07-chinese-milestone-qubit.html
Abstract:  https://arxiv.org/abs/2106.14734
Paper:  https://arxiv.org/pdf/2106.14734.pdf