Google claims to have proved its supremacy with new quantum computer

Maybe someone can tell me what alchemy is good for besides turning lead into gold?

That untapped market of trillionaire hobby number theorists?

Error correction and control are vital for any system to be reliable.

Thankfully the ability to run simultaneously and vet against multiple outputs should overcome this fault for a time.

But even if it is not true, think how good can be QC without being good enough for quantum error correction. You're saying orders of magnitude improvements are needed to be able to do EC, but I'm sure useful and interesting things can be done with log(QV) of 100, only 5 times more than current record.

As the quote mentions, we'll need "many thousand qubits" to reach the point where society itself is getting new benefits out of things. These contrived cases help figure out how to scale the whole system.

Anyhow, with all these huge beautiful dilution fridges with their fancy gold plating and all that, the expense of QC is a rounding error relative to AI. It's still high-risk/high-reward and has seen a level of investment that's commensurate with that.

Also, I don't know who all thinks that these physicists like myself are making beaucoup bucks working on QC. I make far less than a software engineer at grubhub or something, and have taken the opportunity cost of getting a PhD and all that.

Now break the wooden stick in half while on the moon. In space. At absolute zero. While under acceleration. While spinning. While bombarding it with 10^100 neutrinos/second. And do it with 100'000 randomized iterations of the wooden fibers.

A quantum question that is "interesting" would also be similar to finding order out of disorder (e.g. factoring).

There is a great video by the mathematician Richard Borcherds on this exact objection to current examples of quantum supremacy.

https://www.youtube.com/watch?v=sFhhQRxWTIM

In other words, assuming the computer model has sufficiently accurate data as an input, it can produce significantly more refined output than a human can through trial.

In fields where human trial is exceptionally inefficient- molecular physics, chemical synthesis design, structural material design, etc- a sufficiently fast computer will allow for faster design iteration and perhaps even development of new processes and materials.

More concretely, if you wanted to design a new stick that breaks under exactly the conditions that you intend it to, then you can skip a lot of trial and error if your computer can accurately model the materials you are designing and testing.

Think construction, civil engineering, energetic chemistry, biological processes (medicine design) etc.

What if you broke the stick to study its material properties? Then you would need to spend months carefully taking samples and measuring all the broken spots.

With a perfect simulation? You're done the moment it ends. All the data is there available with a copy paste

> To appreciate the feasibility of computing with no energy and no heat, consider the computation that takes place in an ordinary rock. Although it may appear that nothing much is going on inside a rock, the approximately 1025 (ten trillion trillion) atoms in a kilogram of matter are actually extremely active. Despite the apparent solidity of the object, the atoms are all in motion, sharing electrons back and forth, changing particle spins, and generating rapidly moving electromagnetic fields. All of this activity represents computation, even if not very meaningfully organized. (From The Singularity is Near Chapter 3, The Limits of Computation)

Yes, you can write down a problem inspired by a specific stick. And yes, the written down problem will of course inevitably differ in the details from the real stick. Normally you'd think of these small differences as small errors in the description. But as soon as you try to argue the stick is computing the written-down problem, they become errors in the stick because they affect its ability to implement the problem you wrote down.

That suggests that the implications intentionally provoked by the phrasing "Google’s quantum computer instantly makes calculations that take rivals 47 years" are obviously false, even if the statement itself is true in some extremely specific context. So in other words, when genuine quantum progress has been achieved - I don't think we'll need to debate it, as the results would speak for themselves.

Well... yes. But try building a bridge that doesn't break.

Or to keep with your scenario, try to predict exactly where and how your stick will break before you break it. You can't.

The difficult is ensuring entanglement between qubits, scaling up the qubit count, noise reduction between the qubits and the other physical parts of the quantum computer, error correction, and generating the circuit to represent the optimization problem, formalizing a proof that the total time of quantum computation (computation + preparation) is less than to simulate on high performance computers and what not.

There's several YouTube videos where some company has mapped their problem into a quantum circuit and claim it provided solutions to optimization problems that they couldn't have found classically but dunno, I guess it would really require AB testing between classically computing it on an HPC versus a quantum computer.

I think this makes more sense if you use a bridge instead of a stick.

Building a full sized bridge to test your idea is prohibitively expensive but a simulation is cheaper to build even if the actually simulation is slower to compute.

In real life simulations, small prototypes , and full size prototypes are all useful with various trade-offs of cost and benefits at various stages.

If you mean "useful", then I'd like to point our that breaking rods is a common task in many labs all over the world exactly because it can calculate some things better than any non-rod computer we have.

If you literally meant "fascinating", then you'd have to ask yourself. For a lot of people, it is.

Likewise even contrived quantum experiments like this aren’t interesting to many people. They’re not practical. But they’re profoundly interested to people interested in quantum computing. They’re milestones on a roadmap. There will and are things computer computers won’t do better than classical computers and there are things in reality neither will simulate, and those things are interesting to someone. In fact I think this is a crucial part of basic science- EVERYTHING is interesting. Even the lack of something interesting is certainly interesting to a psychologist :-)

Already, optimization problems have seen classical "ising" chips get great results (as good as the quantum annealing chips), proving that optimization doesn't actually need tunneling or superposition.

Now, the number theorists just need to come up with a classical analog for a QFT or another similar transform, and we will see them obviate QC here. Arguably, RSA being obsolete has already done this.

In simulation, supercomputers are also making huge advances in power.

Yeah, if someone could please do that.

At the end of the day, people writing these papers are also human. The very same sorts of humans who pad resumes with shiny technology and self-serving complexity.

This might be a case of a rabbit you do not want to chase.

It's either Monte Carlo or bullshit.

Unfortunately not. The physicists who are behind quantum computing don't think the same way, and go straight for the abstract math to solve any problem. I am pretty sure they don't understand that most of our progress on computing up to this point is because you don't need to go into Galois fields or discrete math to describe what a computer or algorithm does. I'm also pretty sure that they don't know of another way to think about it.

Quantum circuits are made of quantum logic gates like Hadamard, CNOT, Z, CZ, etc. Instead of bits as inputs and outputs, quantum logic gates have qubits. Unlike boolean logic where bits are 0 and 1, a qubit is a 2D vector [α β] where α and β are complex numbers, corresponding to a superposition of the zero and one bases: α * |0> + β * |1>. You can visualise a qubit as a point on a sphere, the so called Bloch sphere [1]

There are multiple ways to implement a qubit, but you need to start with some quantum phenomenon. An example is the polarisation of a photon, so horizontal could be |0> and vertical polarisation could be |1> and the qubit is represented as complex vector of these two. If you've studied linear algebra you know manipulating a vector often involves linear transformations. Any linear transformation can be represented as a matrix - so applying gates is just doing matrix multiplication. Unary gates are 2x2 matrices and binary gates are 4x4 matrices - for photons they would be implemented with mirrors and optical waveplates. Measuring the polarisation at the end is the output. The output is not deterministic but it always follows the same distribution, so you could design a circuit that has |001> X% of the time, |010> Y%, |111> Z% of the time, etc. such that X + Y + Z + .. = 100%.

I'm not too familiar with the details of random circuit sampling, but the idea is that you start with a big circuit that wasn't intentionally designed and therefore has no known properties we can exploit - instead it's a random mess of transformations to the qubits. A classical computer cannot run big quantum circuits - N gates with the 49 Google qubits requires like 2^49 * N^3 classical gates, so it won't be able to calculate the output distribution. However, what we can do is run the quantum circuit many times (do measurements on the quantum computer) and collect many samples. Given enough samples, a classical computer can verify whether there's consistency between them and whether an actual transformation produced them (and therefore quantum computation happened) or its just pure noise / garbage using cross entropy benchmarks [2].

Note that the purpose of the "random" in the random circuit is to introduce hardness and prevent cheating (assume that the classical computer is the "opponent" of the quantum computer); the circuits don't calculate anything useful / of human value.

What's interesting is that once people with supercomputers saw the benchmark formula and analysed the constant factors, they found a loophole which let them run a classical algorithm which generates measurements/samples that satisfy the benchmark with 40K classical CPUs for a week, or even a single A100 within 140 days. Some of their success was due to the sheer power available and some is due to algorithmic cleverness (see: tensor networks). In my opinion, they are only disproving the Sycamore supremacy in a fussy way.

[1] - https://en.wikipedia.org/wiki/Bloch_sphere

[2] - https://en.wikipedia.org/wiki/Cross-entropy_benchmarking

First, it's important to know that a quantum state (written as |letter>) is not directly observable. We can think of it as some vector, for which we can only apply an operation to to get out a scalar observable.

A quantum circuit is a series of operations on a quantum state to create a different quantum state, which can be modeled as a matrix U, which is unitary (meaning U*U=1).

The goal of "sampling a random quantum circuit" is trying to find the probability of observing some given observable if you keep applying random quantum circuits to a given input state.

I'm not saying they suck, but to proclaim that "quantum computers are superior" you need an actual use-case, IMO.

Even then, I believe the classical simulations to beat google's 53 qubit device were never actually performed -- it was shown that they could be performed quickly with petascale memory but actually doing it would be a huge expense. Add a dozen more qubits and even the hypothetical classical challengers fall off quickly...

1. Breaking crypto. 2. Simulating other quantum systems.

For (1) it's basically all downsides. For (2) unless you're a particle phycisist you'll never need quantum computers.

But that's now. Maybe there will be a killer app for it some day, changing everything. Or indeed, we could get it indirectly. Maybe simulating quantum systems we could invent new battery technologies, which in turn changes our lives.

This is exactly correct. While you can simulate classical computations on a quantum computer, it doesn't make a lot of sense to. However, there exists a class of problems for which there exist solutions that have lower time complexities than anything we can run on a classical computer, if only we had a quantum computer of sufficient size.

Examples of such algorithms are the famous two, Shor's and Grover's algorithms, of which Shor's is more interesting because it factors integers in polynomial time whereas the best known classical algorithm runs in exponential time (this is the one that's scary for cryptography). Grover's algorithm is basically function inversion (find the x given a function f and some desired value y such that f(x)=y) in O(sqrt(N)) over the domain of the function, which on a classical computer requires O(N) operations.

Those were discovered in the 90's, so they're pretty widely understood by now. There's a few newer ones, such as the quantum algorithm for linear systems of equations, which solves for a scalar result of an operation applied to the unknown vector x such that Ax=b in O(log(N)k^2) time versus the classical O(nk), where n is the number of matrix elements and k is a measure of how sensitive to error the problem is.

Basically, there's a handful of useful algorithms, and another dozen or so theoretically interesting ones, that can run faster on a quantum computer. For everything else, there's zero advantage to using one.

In fact, nobody yet really knows what those problems are. There are a few real-world problems that quantum computers could theoretically help with, like factoring large numbers, but nobody is really all that close to implementing them. There are problems that can be implemented, like this one, but they are of no use whatsoever. They just happen to be feasible to implement.

The implementation does suggest that they're building up a toolbox of physical parts that could some day (years, less than decades) be used on real-world problems. The class of such problems appears very small so far, but there is reason to think that we could find other problems that matter. (For example, in the realm of AI, which is very compute-intensive -- though thus far nobody seems to have any specific implementation.)

Think of a quantum computer as a magic box on the side that solves a few problems. If you had it, you might completely reconsider what kinds of problems you want to solve. Solving it via the magic box might require a complete reconsideration of how you frame the question -- like discovering a wormhole that lets you get from Atlanta to Seattle instantly, so how would you redesign a trip from New York to LA?

There are already quantum computer safe encryption algorithms that have been released to the public. I don’t know exactly how they work, but one of them was about reverse engineering a path through multi-dimensional space.

Expect SHA256 to disappear soon and be replaced.

* number pulled out of a hat

To help prove that, people have found contrived problems that don't care about errors but that theoretical quantum computers can solve exponentially faster than classical computers. If these physical devices can solve those problems, that is proof that they are on the right path to one day solving actually interesting problems like Shor's algorithm.

There are of course some caveats. For one, the test problems discovered so far are believed to take exponentially more time on a classical computer, but there is no rigorous proof yet (in fact, it is not yet proven that there doesn't exist a classical algorithm that could run as fast as Shor's). The second is that the current quantum computers are so small compared to classical ones that, even with an exponential advantage, they can't always solve things fast enough to prove without a shadow of a doubt that they have this advantage. So, improvements in this time difference compared to the largest known classical computers is still a worthwhile goal.

As for how actual physical qubits are maintained, that topic is tough to find a good explainer for, since every group has a different approach. Some groups use trapped ions, some use two-dimensional quasiparticles, some use spin states of photons... and no one has a clue which approach will be most practical in the end. It's analogous to not knowing whether clockwork or vacuum tubes will be the better way to implement a Turing machine.