News for hackers. Stuff that matters.
Re:Quantum supremacy: the gloves are off by naringas on Wednesday October 23, 2019 @01:53PM (#21337071)
I still don't understand what the hell is "quantum computing". I think my problem is my own conception of classical computing.

My best approximation for what a quantum computer actually is. Is that it's some sort of device to set quantum states, then run a "quantum algorithm" (i.e. a graph of "quantum logic gates"), and finally read out the "quantum bits" resulting from the algorithm. That sounds a lot more like a sensor to me. Also all the problems with noise and calibration reinforce my notion that it's more like a sensor than a computer.

But to be fair I barely understand "classical computing". I think my personal notion relies too much on badly defined ideas about "the run-time" of a computer program (some software) that I have constructed from "industry" experience.

To me big huge fundamental part of computing has to do with arbitrarily representing anything with a symbolic alphabet. And then automatically manipulating this symbolic alphabet to get a result with can be "mapped back" through the initial arbitrary representation so we learn something about whatever we initially chose to represent.

Maybe that's not computing? but then what is that? and then what is computing??

Try as I might I cannot reconcile my understanding of classical computing with quantum computing.

Re:Quantum supremacy: the gloves are off by cdumler on Wednesday October 23, 2019 @03:24PM (#21337938)
In classical computing, a bit is a binary state. The implementation isn't important. What is important is there are only two positions: true/false, on/off, electricity flowing/no electricity flowing, a wooden stick pointed to the left/right. If you treat combinations of state as binary numbers (0000=0, 0001=1, 0010=2, 0011=3, etc) and you create functions that manipulate these bits (AND, OR, NOT, etc gates) such that they generate new patterns of bits consistent with doing math. A classical computer relies on classical physics: something exactly is something. You either have a 1 or 0, because the implementation is either one thing or the other thing.

Quantum computing relies on quantum effects, say the spin of an electron. The spin of the electron can be measured and when does it will either be up or down. At first it seems like it's just like a classical computer; however, it's possible to "entangle" multiple qbits together. The orientation becomes fuzzy. In this fuzzy state is possible to create quantum gates that again do math, but these results become "fuzzy."

So I create the function: "Give x such that x has the reminder of 1 after dividing by some huge number?" In classical physics there is no one answer to modulus. There could be an infinite number of possible answers. Solving it with a classical computer does not mean much more than trying values and seeing what works. But, asking that question with a quantum computer does something different.

Being "fuzzy," it exists across all possible states at the same time until you measure it. When you measure it, you will get a random answer but that answer will work for the equation. Say you ask the question, "Give me x where x divided by 5 has a remainder of 1." The quantum computer might first spit out 56 then next time 91 then next time 6.

Re:Quantum supremacy: the gloves are off by Symmetry on Wednesday October 23, 2019 @03:35PM (#21338046)
Your answer is a good one for helping to understand the problem and is true of almost all computers in active use today. But I want to point out that you can have a classical computer that isn't binary. Analog computers have a long history and are still used in some places today. Also ternary computers where bits can be 1, 0, or -1 had a role in Soviet computing and let you used Balanced Ternary[1] which is even nicer than Two's Complement. But these are classical in the sense of having one particular value in the way the rest of your answer lays out nicely.

[1]https://en.wikipedia.org/wiki/Balanced_ternary

Re:Quantum supremacy: the gloves are off by thaumasiotes on Wednesday October 23, 2019 @07:00PM (#21339973)
> however, it's possible to "entangle" multiple qbits together. The orientation becomes fuzzy. In this fuzzy state is possible to create quantum gates that again do math, but these results become "fuzzy."

The fuzzy results, in my understanding, are a property of quantum mechanics and don't require multiple qubits. A single electron has some probability of spinning up and a complementary probability of spinning down, and until you go ahead and measure the spin, the actual spin value hasn't coalesced to either of those states, instead being some fuzzy intermediate probability spectrum.

Entangling multiple particles means (again, as far as I understand) that their measurements cease to be independent -- if I have several pairs of entangled electrons all with spin of 50% up / 50% down, then I might expect the results of measuring the spin of those pairs to look something like this table:

    +/+   25%
    +/-   25%
    -/+   25%
    -/-   25%
when in fact, because these are entangled pairs, I will either get

    +/+   50%
    +/-   0
    -/+   0
    -/-   50%
or

    +/+   0
    +/-   50%
    -/+   50%
    -/-   0
What am I missing here?
Re:Quantum supremacy: the gloves are off by thethirdone on Wednesday October 23, 2019 @08:34PM (#21340527)
> What am I missing here?

I am unsure what you are missing because what you explained is approximately correct.

Minor correction:

Entangled qubits (each of 50% propbaility to be up) can have more possible measurement distributions that the two you mentioned.

Distributions like the following exist.

    +/+ 20%
    +/- 30%
    -/+ 30%
    -/- 20%
   
> if I have several pairs of entangled electrons all with spin of 50% up / 50% down, then I might expect the results of measuring the spin of those pairs to look something like this table:

I think you may misunderstand how to get qubits entangled. You would have to pass two qubits through a two-qubit gate to get them entangled. And doing so would leave you with only one measurement distribution.

For example if you have a qubit in 50% |1>, 50% |0> and pass it through CNOT with a qubit in |1>. You get:

    |11>   0
    |10>   50%
    |01>   50%
    |00>   0
But if the second qubit was in state |0>, you get

    |11>   50%
    |10>   0
    |01>   0
    |00>   50%
> if I have several pairs of entangled electrons all with spin of 50% up / 50% down

Also just in case you don't know qubits have phase so there is more than one way to have a qubit that when measured will be up 50% of the time.

Re:Quantum supremacy: the gloves are off by cdumler on Thursday October 24, 2019 @11:56AM (#21345896)
My goal wasn't to explain a "correct" view quantum physics, only to demonstrate at a cursory level that a binary computer's bits differs from a quantum computer's qbits. Quantum physics is not intuitive and attempting to use a classical understanding of probability will get you in trouble. I highly suggest looking at videos on YouTube, which have a far better explanations on the actual behavior of quantum computation. This is a very good video on Bell's Inequality: https://www.youtube.com/watch?v=zcqZHYo7ONs&t=856s
Re:Quantum supremacy: the gloves are off by DiogenesKynikos on Friday October 25, 2019 @04:02AM (#21352822)
A really important thing to keep in mind is that different possible states have amplitudes, which are complex numbers. These are the real, fundamental description of the system, rather than the probabilities, which are real numbers.

The state of the system could be, for example:

   State  Amplitude  Probability
    +/+      1/2         1/4
    +/-     -1/2         1/4
    -/+     -i/2         1/4
    -/-      i/2         1/4
In the right-hand column, I've included the probability of measuring each state (notice that it's the square of the modulus of the amplitude), but that's not the fundamental quantity that you deal with in quantum mechanics.

All the dynamics of a quantum system are expressed in terms of how the amplitudes change over time. In fact, if this means anything to you, the most succinct way to state how quantum mechanics works is that a quantum system with N possible states is represented by an N-dimensional complex vector, and that in an infinitesimal time step dt, the system goes from v to (1+iHdt)v, where H is a matrix with complex entries (and 1 stands for the identity matrix). If you measure the quantum system, you have to first pick a set of basis vectors in which to measure it. The result you get is one of the basis vectors. The probability of getting any basis vector as result is the square of the coefficient (technically, the square modulus of the coefficient) on that basis vector. The coefficient is what we call the "amplitude."

In a quantum computer, you first prepare the system in a desired state (a complex vector). Then, you get to choose what linear operations you will apply to the state. Then, you observe the state in some basis (in the complex vector space), and get a random basis vector (proportional to the modulus squared of the coefficients in the final state). That's basically it. The trick is whether or not you can actually figure out a way to compute anything useful with such a system with lower complexity than you can with a classical computer. Your fundamental operations are different (linear transformations of a complex vector) than they are in a classical computer, and you have the added wrinkle that you can't read off the final state of the computer - the final result is a random draw from a probability distribution that is based on the state of the computer. Peter Shor figured out that with this setup, you can factor large numbers in a way that uses fewer operations than a classical computer (asymptotically). It also turns out that you can simulate quantum systems really effectively with this sort of system. That's not so surprising. As Feynman said,

> "Nature isn't classical, dammit, and if you want to make a simulation of Nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy."

Re:Quantum supremacy: the gloves are off by btilly on Wednesday October 23, 2019 @02:20PM (#21337313)
Quick explanation.

Flipping a bit in classical computing is an irreversible operation, and so has to release heat. We also have to be in one state at a time.

In quantum computing, we are only allowed reversible operations, but can be in a superposition of states. There is no heat released, no upper limit on how fast the operations can go, and no upper limit on parallelism. But the flip side is that you cannot peek at the operation, and error correction is not exactly easy.

The "only reversible operations" bit is a huge restriction. For example it means that "if" statements are not allowed.

Re:Quantum supremacy: the gloves are off by Strilanc on Wednesday October 23, 2019 @02:01PM (#21337132)
Here's a youtube video that might be at just the right level for you: https://www.youtube.com/watch?v=ZoT82NDpcvQ . Basically it goes over the simplest quantum-vs-classical query advantage (1 instead of 2) that was ever found.
Re:Quantum supremacy: the gloves are off by achenatx on Wednesday October 23, 2019 @04:06PM (#21338404)
In the end a classical computer just "processes" data. It takes data in, processes it (math operations), then outputs it. The foundation is boolean math, which is then used to execute regular math.

At the very most basic level a computer is made of transistors that can solve the problem of basic boolean math. Gates are AND (or NAND), OR, XOR etc.

An XOR gate produces the following output from the following inputs:

A B Output

0 0 0

0 1 1

1 0 1

1 1 0

an AND gate produces the following outputs:

A B Output

0 0 0

0 1 0

1 0 0

1 1 1

with those gates you can make an adder. A single bit adder has the following inputs and outputs

A B Output 1 Output 2

0 0 0 0 (decimal 0)

1 0 0 1 (decimal 1)

0 1 0 1 (decimal 1)

1 1 1 0 (decimal 2)

Notice that Output 2 is an XOR of inputs A and B Output one is an AND of inputs A and B. So a single bit adder is simply the inputs feeding an XOR gate and an AND gate.

This can be scaled up to add any number of bits. Other math operations can also be done.

Transistors can be used to make memory bits that hold its state and can be set and unset. They are essentially binary gate loops that feed outputs back to inputs and rely on the delay of electron flows to reach stable states.

A clock is used to sequentially count (and pull instructions from memory) and set and unset memory bits. Each cycle of the clock allows the computer to execute the next instruction (by incrementing a number that determines which instruction to fetch).

From there you are right, the bits are used to encode meaning. Which could be alphabets, images, audio etc.

Re:Quantum supremacy: the gloves are off by travisoneill1 on Wednesday October 23, 2019 @02:03PM (#21337160)
Is that different than a regular computer? To take your statement and slightly modify it:

some sort of device to set electromagnetic charges, then run an "electromagnetic algorithm" (i.e. a graph of "electromagnetic logic gates"), and finally read out the "sequence of electromagnetic bits" resulting from the algorithm.

That sounds to me like the computer that I am typing on now. Am I missing something here?

Re:Quantum supremacy: the gloves are off by outworlder on Wednesday October 23, 2019 @03:23PM (#21337927)
> Is that different than a regular computer

Not very. Using their definition, logic gates, RAM, Flash or Hard Disks could all be redefined as "sensors".

Re:Quantum supremacy: the gloves are off by fossuser on Wednesday October 23, 2019 @02:07PM (#21337209)
I'd recommend Charles Petzold's Code: http://www.charlespetzold.com/code/

Which does a great job building up computing from bits all the way to a adders, CPUs, and assembly language (with the historical background around it too).

I think the easiest way to get an idea for Quantum Computing and what the difference is comes from watching a specific example, I thought this example of Shor's algorithm was pretty good: https://www.youtube.com/watch?v=wUwZZaI5u0c

Re:Quantum supremacy: the gloves are off by marcosdumay on Wednesday October 23, 2019 @03:15PM (#21337848)
If you can't formally differentiate a computer from a sliding rule, you will have problems differentiating a quantum computer from a sensor too. That's normal.

The difference is more on the flexibility to run different programs than on them transforming encoded data. Both a sliding rule and a sensor do transform encoded data, a computer is something that can apply any mathematical transformation into the data.

Re:Quantum supremacy: the gloves are off by athisntoswhry on Wednesday October 23, 2019 @06:32PM (#21339771)
Nitpick, but there are some transformations that our current computers (or our current mathematics moreso) cannot do, for example, a continuous form of the Fourier Transform. We only possess discrete formulations of it. But in nature, light passing through a prism or diffraction grating performs an equivalent operation (presumably) continuously. So as of right now, nature is still more powerful than our strongest computers.
Re:Quantum supremacy: the gloves are off by nixpulvis on Wednesday October 23, 2019 @08:27PM (#21340499)
Well technically the photons only interact in "quanta" themselves anyway. And suddenly we're back at the level of quantum computing!

I'm not sure what transformations you have in mind that "our current mathematics" cannot do.

Re:Quantum supremacy: the gloves are off by IIAOPSW on Wednesday October 23, 2019 @05:29PM (#21339199)
A quantum computer is "a sensor" in the same sense that every laptop is "an electronics experiment".

A quantum computer still fits your model because you arbitrarily represent anything with an alphabet of quantum states, automatically manipulate it with a quantum algorithm, and map back the result at the end so we learn something about whatever. I do not see the contradiction.

Re:Quantum supremacy: the gloves are off by svat on Wednesday October 23, 2019 @03:09PM (#21337796)
If you really want to know: https://quantum.country/qcvc (previous discussion: https://news.ycombinator.com/item?id=19426573)
Re:Quantum supremacy: the gloves are off by grumpy8 on Wednesday October 23, 2019 @03:23PM (#21337928)
Overly simplified, but in classical computing, a bit is an abstraction representing a 0 or 1. In quantum computing, a bit IS the electron (or some other particle). And electrons are weird and can behave in very surprising ways. Quantum computers are controlling these electrons allowing to do things that classical computers can't. One example of such thing is Shor's algorithm which, taken from wikipedia, "is almost exponentially faster than the most efficient known classical factoring algorithm".
Re:Quantum supremacy: the gloves are off by glandium on Wednesday October 23, 2019 @08:31PM (#21340515)
Minute Physics has a really good explanation of Shor's algorithm, and by proxy, Quantum computing. https://www.youtube.com/watch?v=lvTqbM5Dq4Q

And the followup: https://www.youtube.com/watch?v=FRZQ-efABeQ

Re:Quantum supremacy: the gloves are off by ridewinter on Wednesday October 23, 2019 @03:25PM (#21337941)
As wild as it sounds, parallel universes are IMO the best way to explain a quantum computer. I posted an article about it:

https://news.ycombinator.com/item?id=21337739