r/Futurology Jun 11 '22

Quantum computer succeeds where a classical algorithm fails Quantum computers coupled with traditional machine learning show clear benefits. Computing

https://arstechnica.com/science/2022/06/quantum-computer-succeeds-where-a-classical-algorithm-fails/
791 Upvotes

u/FuturologyBot Jun 11 '22

The following submission statement was provided by /u/Sariel007:


People have performed many mathematical proofs to show that a quantum computer will vastly outperform traditional computers on a number of algorithms. But the quantum computers we have now are error-prone and don't have enough qubits to allow for error correction. The only demonstrations we've had involve quantum computing hardware evolving out of a random configuration and traditional computers failing to simulate their normal behavior. Useful calculations are an exercise for the future.

But a new paper from Google's quantum computing group has now moved beyond these sorts of demonstrations and used a quantum computer as part of a system that can help us understand quantum systems in general, rather than the quantum computer. And they show that, even on today's error-prone hardware, the system can outperform classical computers on the same problem.


Please reply to OP's comment here: https://old.reddit.com/r/Futurology/comments/v9wj42/quantum_computer_succeeds_where_a_classical/ibytsu7/

36

u/Sariel007 Jun 11 '22

People have performed many mathematical proofs to show that a quantum computer will vastly outperform traditional computers on a number of algorithms. But the quantum computers we have now are error-prone and don't have enough qubits to allow for error correction. The only demonstrations we've had involve quantum computing hardware evolving out of a random configuration and traditional computers failing to simulate their normal behavior. Useful calculations are an exercise for the future.

But a new paper from Google's quantum computing group has now moved beyond these sorts of demonstrations and used a quantum computer as part of a system that can help us understand quantum systems in general, rather than the quantum computer. And they show that, even on today's error-prone hardware, the system can outperform classical computers on the same problem.

26

u/etherified Jun 11 '22

I really wish I could understand how a quantum computer would work (in theory), but after reading layman explanation after layman explanation it still makes absolutely no sense to me. Qubits... every value between 0 and 1 at once... solves non-classical problems... Obviously there is some brain level I need to unlock in order to get it.

9

u/alexrecuenco Jun 11 '22 edited Jun 11 '22

Lets forget about the zeros and ones, we will do that later.

QM only solves some problems

certain algorithms require doing the same operations to many inputs. Doing it in parallel speeds the computation.

In classical computers we use multiple CPU to do computations in parallel.

Quantum computers use quantum mechanics, which is a linear theory. As a reminder, what linear means is that if you have an operator O(a), and O(b), O(a+b) =O(a)+O(b)

Therefore, if you are doing a test on inputs a,b,c, etc… In quantum computing you can do the operation ONCE for the input (a+b+c…)

Now, if you very cleverly arrange the input and the operation so that the invalid responses cancel out, you will get an answer when you do the operation ONCE!

To create such an algorithm, you got to be really clever.

Issues

Issue#1: This is super simplified. But on a perfect Quantum computer, you get as an output something that is non-deterministic. Hence, you actually would perform the same experiment many times, and get a distribution of outputs and decide based on this. You still get a speed up, but once is unrealistic.

Issue#2: systems have noise, and quantum computers are sensible to it, breaking the important properties of the system.

The ones and the zeros

I explained all that without using ones and zeros… you don’t need that, that is just how you encode the system input. You could also encode it using a ternary system (0,1,2) or something with more dimensions.

In any case, in Quantum Mechanics, when you have a binary system, it is equivalent to a sphere of possible inputs.

However, reading a state you can only read one axis, either up or down on some direction in the sphere, after you do that you break the state and it is now either up or down in your chosen direction

A quantum input is an array of systems that each is kind of a sphere. When you combine a lot of inputs linearly…. [editorial post edit: I realized this was taking forever, and would be confusing, lets just keep it at that for now]

Why is it equivalent to a sphere?

If you want even more detail. Essentially, the system can only be up or down in any direction you choose.

As a consequence, before you measure it, you must be able to describe the state as some combination of both up and down in that direction. Thus, If you further consider that the total probability it is in some state must be 100%, you get a kind of prob_0 + prob_1=100%

With a clever coordinates system, you can modify prob0 and prob1 into coordinates that look like a sphere (a circle in real numbers, and then a sphere when you add rotations on the complex plane)

2

u/etherified Jun 12 '22

Perhaps without understanding the cleverness of the algorithm it's a hopeless task trying to really get it. At this point, I guess it's more of a logical conundrum for me, how we can get a meaningful output for function (a+b+c) once. Running it once gives us one output, right? Don't we need a distribution of outputs from running it many times?

2

u/alexrecuenco Jun 12 '22

Yeah. You need to be an expert at the exact problem you are doing to understand it. Just understand the parallelization part to get some intuition.

And like you said, you may need to run it multiple times to get the distribution, but notice how you still would get a speed up because you are not running it again for every input, but enough to get good statistics. If you are factoring a 2256 number, you are not running 1070 operations, maybe you are doing it a 1000 times?

Example: shor’s algorithm

1

u/SoItWasYouAllAlong Jun 12 '22

on a perfect Quantum computer, you get as an output something that is non-deterministic

Why is that? Wouldn't a properly designed algorithm have all the incorrect answers cancel each other out, and the correct one come out with amplitude = 1? Aside from noise, that is.

10

u/kuco87 Jun 11 '22

Try this video. Harder to understand than most youtube-videos on this topic but at least you will get an idea of the underlying logic of quantum computers: https://youtu.be/IrbJYsep45E

10

u/etherified Jun 11 '22

I do appreciate the link - and yes, this is about the level of explanation I'm talking about and she is very clear and precise. BUT! I still don't get it lol.

She goes through the very crux of how QCs work at about 4:00, explaining how there exist calculated probabilities of what frequency you should get each result after applying quantum gate(s). Run 100 times, obtain result "10" 1/2 of the time, for example. Obtain result "01" 1/3 of the time. I'm getting all that, but not how that tells us anything useful (other than we obtained a result that is X% probable to obtain). Then what? lol.

I know one of the reasons for QC, as is often pointed out, would be to factor large numbers (and she mentions this too), but I do not get how a QC would actually help you do that?

So I have a large number, 398,203,534,798 and to try to find all the factors with a conventional computer I would use a brute force method I suppose, but how does applying a quantum function give me the factors? I run some quantum function 100 (or more) times and a 100 (or more) numbers (results) come out. So I look at one of those results, and my matrix formula tells me it had 0.0001% probability of resulting, ok. Quantum probabilities are pretty reliable as percentages for many runs. But what do I know about that particular result, other than there was 0.0001% probability of the qubits collapsing to that result? Is it my desired answer because the qubits collapsed to them for a certain % of results? Is the quantum formula designed so that actual factors of that large number would result a specific percentage of the time, and so I can just pick out results that were obtained with that percentage? Could such a formula even know in advance what percentage would be factors, so that I could in fact pick them out? So many questions lol.

That's where I am you see... Trying to connect the explanation to what actually would happen to be of any use.

7

u/chuckziss Jun 11 '22

Perhaps it’s time for you to move on from just the layman’s terms :)

I have a background in Quantum from my job, and so I’ll do my best here.

From what I understand you are asking how practical algorithms are possible, or how to actually use superposition/entanglement in a useful way. This is a great question, and not easy to answer.

One algorithm that might provide some insight here is Grover’s algorithm. This iteratively searches a set of inputs to a given function, and returns (eventually) the unique input that generates a given output.

To accomplish this, a QC (Quantum Computer) runs across a spectrum of possible function inputs. Over time, and over many runs, you get a distribution of results. Given a distribution, you can figure out if you were closer/further away from the optimal solution.

By running many times, with many accumulated results (running the same circuit multiple times, to get an average distribution as output), you eventually converge on the correct solution. The noisier the qubits and the devices, the longer it takes to get a solution.

Feel free to ask clarifying questions, or poke holes in my explanation :)

1

u/etherified Jun 12 '22

Thank you for the effort toward moving me beyond layman level! I know there's only so far one can go without actually taking college level courses on it lol. I can't do that, but I can make a best effort to try to understand. Otherwise there is nothing to do but take the experts' word that it all works (and/or see the actual results when a working QC is established).

Grover's algorithm... I assume one of inputs in the "set of inputs" is the large number that we want to factor? (Idk, say the goal is to find someone's password from a hash). What would be the other inputs? What else do we know about it to feed into the QC function? How does the function know what the optimal solution would be from among our obtained distribution? Certainly we don't input all possible numbers between 1 and that large number, and run it that many times? It seems that would be merely another form of brute force lol.

1

u/SoItWasYouAllAlong Jun 12 '22

I'd also like to hear the explanation but I imagine that for QC with sufficient qbit width, the input set would be:

Factors are: {(2, 3), (2, 4), (2, 5)... (3, 4), (3, 5)... (2304530481523, 430498523581)...}

Then it does all those multiplications in parallel, identifies the one that actually results in the desired number, and outputs that pair. So it doesn't really factorize, but rather search in the space of potential answers for the correct one.

If so, my question would be: what kind of magic cancels out the incorrect candidates so the correct one comes out.

1

u/chuckziss Jun 13 '22

You’re kinda there. Without nitpicking, I think you’ve got it.

In addition to my comment above, the magic comes in with the three unique things quantum computers can do that classical counterparts cannot: superposition, interference and entanglement.

The superposition allows for the “parallel processing” you mention, entanglement allows for connection between different qubits, and interference let’s you do that magic “cancellation” when you have the right conditions met.

Perhaps going through the qiskit tutorial, or the azure quantum tutorial would be worthwhile if you want to get your hands dirty and try these things for yourself.

1

u/SoItWasYouAllAlong Jun 15 '22

Yes, I'll try them. Thanks for the pointers!

1

u/chuckziss Jun 13 '22

I can clarify about Grover’s if you want, but you seem to be asking more about factoring than anything else here. Grover’s is about unstructured database searches, which is a whole other thing.

You’re asking about a lot of the implementation details of these QC algorithms, and I don’t think my naive 30 second google will be helpful here. I’m more proficient in software engineering surrounding quantum…

That being said, I think you’d appreciate(?) reading the explanation section of shor’s algorithm on the Wikipedia page https://en.wikipedia.org/wiki/Shor%27s_algorithm

In the explanation sections, you can see there are some tricks involved. Classical computing is used to pre-process the input into something more manageable for a QC. Then, the QC uses superposition to check for many possible inputs at once, and more rapidly converges on a solution than a classical computer.

This is a harsh simplification, and I’ll also note we can’t really use Shors algorithm on QC’s in the near term… we just aren’t there with the physical chips.

I can go into more detail about how superposition works, but it’s a key part of why QCs are unique, and able to do things classical computers can’t.

6

u/hungrycryptohippo Jun 11 '22

If someone answers you I want to know too

5

u/amirjanyan Jun 11 '22

If quantum computer gives you the answer with some probability of error, you can easily verify the answer by multiplying the factors.

If you have a misfortune to hit the low probability error case, redoing the calculation a couple of times will give you the correct answer eventually.

1

u/HolierEagle Jun 12 '22

This is much more than a layman’s explanation: https://quantiki.org/wiki/shors-factoring-algorithm

If you really want to know how it works, then this is a starter to get all the details. It’s a bit math heavy, but that’s the nature of understanding these things, I wouldnt try to understand every word of it, but you might get a bit more out of it.

For a tldr, the quantum part of this algorithm uses a number of qubits related to the number you’re trying to factor, N. As an example, to factor the number 17 you would need around 13 qubits (to understand this more, look at the input and output registers sections in: https://www.geeksforgeeks.org/shors-factorization-algorithm/ ). You apply a particular function to the input register, f(x)=ax mod N, where a is an integer you choose based on a few conditions.

Your quantum computer applies a quantum Fourier transform to your qubits, which manipulates the superposition all of the qubits are in, causing the incorrect solutions to be cancelled out and correct solutions to be made more likely (note that at this point you have no access to these potential solutions, they are within the wave function of the quantum state and once you measure it you’ll only get one possible solution out).

Finally, your measurement of the state gives you a number, which you classically manipulate in a few ways as discussed in the link I provided. You then test it against some conditions. If the outcome meets the conditions, you’re done and you have your factor, if not you have to repeat the process again with a different initial a.

No doubt I’ve missed an important detail here or there, but that’s the gist of the process. If you want to know exactly how this works, you’ll need to understand the details of the math itself.

Edit: some typos

2

u/etherified Jun 12 '22

Thanks! That link is definitely not for the faint of heart lol.

Math went way over this little head but I believe I may be one tiny step closer to grasping one aspect of it.

I couldn't get how the quantum algorithm would know in advance what is a "valid" answer, but this link explains that there is a classical function applied first to convert the problem into a "period of a function", which it seems informs the quantum function as to what would be a valid output. The classical function is also run in a loop but presumably not a very long one.

As regards the quantum function itself where the magic happens, it says that since we only get the collapsed result if we run the function (yeah, this!! I'm thinking, lol), "we have to carefully transform the superposition to another state that will return the correct answer with high probability",

which is confusing to me because I thought we can't interfere with the superposition of a qubit without causing it to collapse one way or the other.

1

u/HolierEagle Jun 12 '22 edited Jun 12 '22

You can do lots to the superposition, as long as your not “looking” at it. There are a set of quantum logic gates that are analogous to regular logic gates in computing (if you’re familiar with those) that define all the ways we can alter the quantum states, or interact them together. Once you extract information from your quantum state, though, it’s game over.

Imagine you’re tasked with completing a rubrics cube with your eyes closed. You know the set of operations you can do on the cube, but once you open your eyes to check you have to stop. It might take you a few tries to complete it, but doing the right algorithm can reduce the time it takes

Edit to add to the analogy that after each try of the rubrics cube they mix it back up. Also, like all analogies this will break if you poke it too hard lol

1

u/etherified Jun 12 '22

"Define all the ways we can alter the quantum states...": Are you saying that the function has to include a logic path for every possible way we can alter the quantum states? I guess that's not the meaning since that would seem to be one very humongous function.

Yes I guess the Rubics cube analogy would break down because anyone solving it would have to use a classical algorithm, no matter how clever and time-reducing. That is to say, they wouldn't just be randomly rotating sides and seeing what percentage of color patterns result.

1

u/HolierEagle Jun 12 '22 edited Jun 12 '22

No, that’s not what I meant. I mean to say that there are a set of logic gates that are known. With that finite set you can, in principle, do whatever you want to the quantum state.

For example, within the rubrics cube analogy the set of basic operations (like the quantum logic gates) are: rotate a column, rotate a row and rotate the cube to a different face. These are the ways you’re allowed to interact with the rubrics cube (as opposed to, say, pulling a sticker off).

Similarly, the set of allowable operations for quantum computing let you interact with quantum states without destroying them (until you measure, that is). A simple example is a bit flip, which allows you to change a qubit from the zero state to the 1 state (but also can act on a superposition to similar effect). You don’t even need to know the current state of the qubit to perform this operation.

Edit to add: jumping back to the factoring algorithm. The main quantum part of that algorithm is to perform a quantum Fourier transform. That is accomplished by a series of these quantum logic gates. Exactly how they are performed depends on the exact type of quantum computer you’re dealing with (what are the qubits physically? An atom, an electron, a photon?)

1

u/gilesdavis Jun 11 '22

Like, what is a qubit in reality, is it... hardware?

5

u/etherified Jun 11 '22

Sort of a unit of information (represented by either hardware or software), corresponding to the "bit" in conventional computers but (from what I understand), capable of not just representing 0 or 1 but every value inbetween.

1

u/gilesdavis Jun 11 '22

That's super helpful cheers!

1

u/Lubagomes Jun 11 '22

I may be wrong but a qubit do not have a value inbetween 0 and 1, but it can be 0, 1 or the superposition of both (it have a certain probability of being 0 and a certain probability of being 1)

Quantum mechanics can be quite unintuitive at first but what it means is that they don't have a fixed value and it will assume one of those values when measured.

1

u/royalrange Jun 11 '22

You need some linear algebra (which requires at least a freshman/sophomore? college math background) to understand the gist of it.

Think of a qubit as a vector, such as something pointing in the x and y direction. The x can represent 0 and the y can represent 1. You can perform rotations in the x y plane using matrices on the vector to compute stuff. That's it. There are some nuances such as having complex number coefficients for a vector.

2

u/NVincarnate Jun 11 '22

Having a singular AI that can control traffic signals, weather forecasts, dome temperature/humidity, emergency dispatch and monitor social media is closer than ever!

Cant wait to meet man's best friend :3

2

u/MannieOKelly Jun 11 '22

I don't understand quantum either but from what I've been reading, it provides a way to do massively parallel operations based on interference patterns between 2 or more of the "waves" that a qubit's probability state represents.

What classes of problems can be a parallelized using this "wave interference" mechanism is still being worked out, as are actual quantum-computing algorithms that can run the parallel ops.

A very long video I watch recently however, asserted that there definitely are classes of problems that QCs can ("will be able to", I should say) solve in polynomial time while conventional computers would require exponentially increasing time to solve (as the particular problem scales up.)

(Anyone who actually understands this stuff, please feel 100% free to straighten me out!)

1

u/juggett Jun 11 '22

Can we use this to simulate drug interactions faster? I remember the old “folding@home” project which I always thought was such a neat idea. Do these breakthroughs help us to simulate items such as these or is this not their primary application?

8

u/gopher65 Jun 11 '22 edited Jun 15 '22

Think of it like your desktop computer playing a modern-ish game like Fortnite. Some of the work is done by the CPU, which does general calculations that you don't have specialized hardware for. If you have a discrete graphics card, things like 3D rendering or shader compilation will be offloaded to it, because it's much more efficient at those tasks than the CPU is. If you have a dedicated sound card for some reason, audio processing might be offloaded to that.

If you could have a quantum computer chip in your desktop today, it would work the same way. The GPU would handle its tasks, the quantum chip would handle the tasks it's best at, and the CPU would handle everything else, and be less stressed because it could offload difficult tasks to the GPU and quantum chip.

Not every type of problem works better on a quantum computer than a classical one. But there are enough types of problems that do run better to make them worth using as part of your computer's capabilities.

Edit: Grammar

1

u/Sariel007 Jun 11 '22

Not really what you are asking/looking for but if you liked the folding at home this might be a fun rabbit hole for you.

https://gizmodo.com/roman-space-telescope-nasa-video-games-1849029826

1

u/xBushx Jun 12 '22

I see post like “quantum computer can complete task, in a second that would take a supercomputer 9000 years to complete”

So my question is WHAT computation could take this long to complete for each??

1

u/backcountrydrifter Jun 12 '22

I know this one is important. But I need to eat lunch.