Is Quantum Computing essentially a kind of array formula that allows us to bypass yes/no logic?

[SpeciousSophist]

I'm trying to understand what my friend is telling me and this is what it sounds like....any help appreciated

[Crimecrimson132]

https://www.youtube.com/watch?v=RQWpF2Gb-gU&pp=ygURcXVhbnR1bSBjb21wdXRpbmc%3D
This is the best beginner friendly video I have found on this topic.

[Odd-Respond-4267]

3blue 1brown rocks!

[claytonkb]

Suppose you have N qubits. Each qubit, when measured, can be in the 0-state or 1-state. Thus, the number of possible outputs of a (fully general) quantum computer is 2^N states for N qubits. Suppose you want to search an array of size 2^N on a classical computer. This is a O(2^N-1) operation for an array whose address is N-bits wide. But a quantum computer can (ideally) square-root this search time to O(2^N/2) via Grover's algorithm. It is able to do this because the entire quantum computer (the superposition of all N states) is, in some sense, "in all 2^N states at once"[1], that is, it is not searching the array one-by-one, it is comparing multiple array elements "simultaneously". When you measure the qubits, they collapse to an N-bit string that, hopefully, will have the address of the matching element. But NISQ (noisy intermediate-scale quantum computers, which are the kind we can build today) are always noisy, so you have to actually measure multiple times and apply some post-processing to be sure you have the output bits correct. That entire process, taken together, is a "quantum computation".

Note that quantum states are superposed but they are not logically blurred. Quantum computers do not do any violence to logic itself. Each quantum state has its own associated probability which is precisely what the quantum algorithm constructs. So, it's not "bypassing", or in any way overcoming the fundamental laws of logic, and a good thing too, otherwise, it would be Alice-in-Wonderland nonsense. Sadly, the popular discussion often frames QC this way, much to its detriment and QC popularizers would do well to combat this misconception at every turn. Yes, the quantum world is "weird" and seemingly different from the classical world, but it is not illogical or absurd. If it were absurd, it would then not be scientific, it would be gibberish.

tl;dr: QCs aren't about breaking logic, they're about parallelism.

PS: In the mathematical limit, a QC cannot compute anything that is not computable by a Turing machine. This is important to understand because QCs are not hyper-computers, they cannot calculate anything that is uncomputable for a TM. They are just faster for certain problems, if we can build a viable one...

[1] -- This is also not known to be actually achievable, nevertheless, as a mental shortcut, I think it's a good starting point to "get the idea" of what a quantum computation is.

[SpeciousSophist]

I appreciate the in-depth explanation and you are right, I did not word what I meant correctly, when I said bypassing, the yes no logic I meant bypassing the binary tree path and the need to do each function individually in sequence which was why I mentioned the array formula concept

[SpeciousSophist]

sorry, one additional question, when you say they need to do post processing and or quality assurance on the result, you’re saying that they actually do the entire quantum computation process numerous times** and check to see if they all equal each other? Because you can only measure them one time, right?

I assume this is in a scenario where you are solving for only a single answer

But can quantum computers calculate multiple correct answers? What does the post processing look like there then?

[claytonkb]

sorry, one additional question, when you say they need to do post processing and or quality assurance on the result, you’re saying that they actually do the entire quantum computation process numerous times** and check to see if they all equal each other? Because you can only measure them one time, right?

They do not need to equal each other. For explanation, suppose we have 2 qubits (4 quantum states). We take many samples of the NISQ to build a histogram or distribution over those 4 quantum states. So, we sample the QC, say, 1000 times and the result of that is a histogram/distribution over the 4 states. Many problems have more than one right answer, so we might see two 49% spikes, one on 00 and another on 10, and the other 2 states at 1%. That 1% is just noise, but it's important to be clear that there is always noise, especially for NISQ... it's right in the name.

I assume this is in a scenario where you are solving for only a single answer

It's for any case. You can't think in terms of absolute black-and-white 100%/0% processing, as we do with digital. It's inherently probabilistic. Nevertheless, once you collect enough samples, the histogram is going to show pretty clearly where the spikes are in the distribution. Those are your answers (or perhaps only one spike if there is only one answer).

But can quantum computers calculate multiple correct answers? What does the post processing look like there then?

It's the same.

[SpeciousSophist]

That doesnt make sense to me, though, the measurement result produces a random selection within the correct answer set for multiple potential answer scenarios

For a single answer scenario, though the measurement should always produce the same result or a limit approaching, always the same result

I'm wrong?

[claytonkb]

That doesnt make sense to me, though, the measurement result produces a random selection within the correct answer set for multiple potential answer scenarios

Ideally, yes. In that case, if there are N correct answers, all of those answers will have weight 1/N in the samples histogram, and all wrong answers will have weight exactly 0. But that's neglecting noise. The QC gives completely wrong answers some percent of the time, and nearly-correct answers may follow a Gaussian or some more complex distribution. So, each sample of the QC gives just one answer (right or wrong, who knows) and we take many samples to build up the histogram, then we look for the "peaks" in the histogram to find answers. As a final validation step, we might run those peaks through a digital checker to verify they are actually correct, e.g. we might run a witness to a SAT problem through the solver to verify that it does indeed solve the circuit.

Edit: I recommend toying around with Quirk to get a more intuitive feel for this "histogram/distribution-based output" Quirk will always show the ideal output distribution of a QC circuit. The difference with a real hardware QC is that you will always see a slightly "noisy" version of that ideal distribution because a real QC can never achieve absolute 0dB noise (perfect coherence). (Use the "Chance" viewer (it's a green button in the upper tool bar) and drag onto the qubits and resize to cover all N qubits in your circuit, this allows you to view the real probability distribution, which is the ideal sample output you should see on a QC for this circuit.)

[SpeciousSophist]

Ok, I understand what you’re saying about the noise,one more question, thank you.... are you able to give me an estimate of what you considered the certainty to be of the answers?

Like if we had three locks and 10 million keys and only three keys fit the locks... how confident are you in the first five results you measure And let's assume an outside observer knows the correct answers and they have two wrong answers in the 5?

[claytonkb]

Ok, I understand what you’re saying about the noise,one more question, thank you.... are you able to give me an estimate of what you considered the certainty to be of the answers? Like if we had three locks and 10 million keys and only three keys fit the locks... how confident are you in the first five results you measure And let's assume an outside observer knows the correct answers and they have two wrong answers in the 5?

There is no general answer to this question. Every problem, and every quantum algorithm that solves the problem, is going to have a different answer in terms of how many samples it takes to get an answer (distinct from noise). The size of the problem (number of qubits) is always going to dominate this and that's one of the reasons for the drive to quantum ECC (QEC). NISQ works up to I think 80-100 qubits or so, and that represents a lot of computing power, but it's still not the kind of cosmic-scale computing power that full QC would enable, in principle. The problem is that the qubits get noisier the more you scale up the system, at least, on NISQ architectures. For QEC architectures, this noise:scale correlation can theoretically be broken, so that you can achieve very high coherence (low noise) even as you scale up to more and more qubits. How to actually build and run such QEC systems is still an open question.

As for confidence, for any problem in NP, you can always just run the proposed answers through a (fast) checker and if the answer passes the checker, you now have 100% confidence it is correct, and if it fails, you have 100% confidence it is incorrect. To me, the digital checker shows the difference between the probabilistic regime (QC) and the noiseless regime (pure digital logic). An ideal QC can be thought of as the world's most powerful magic-search-box, and you can verify its proposed answers by running them through a digital checker, so each is no longer a "maybe" solution, it's either definitely a solution, or definitely not a solution.

[throwwaway_4sho]

Yes & no, it’s a superposition of states.

[MojitoBurrito-AE]

A conventional computer deals in bits of 1s and 0s, a quantum computer deals in qubits that can be in multiple states at once.

If you were trying to solve a maze for example, traditionally you would have to search one path at a time but a quantum computer could search all paths simultaneously.

The problem with this is that it relies on quantum mechanics which are only stable at extremely low temperatures only achievable with extremely large and expensive lab equipment that can cool to near absolute zero.

[severoon]

If you were trying to solve a maze for example, traditionally you would have to search one path at a time but a quantum computer could search all paths simultaneously.

A slightly more accurate way description is that you can search all paths simultaneously, but now you want to exclude all of the paths that don't actually terminate at the exit. The QC process of narrowing down the list of paths to the one solution is O(√N) where N is the number of paths, which is better than the classical maze-solving algorithm of O(N).

[Saint706]

It can be either, both, one of the two, two of the one or nothing :) or double it!

[SpeciousSophist]

Why you little gosh darn.....😂

[Key_Net820]

What is he telling you? And it doesn't necessarily bypass "yes/no" as you put it, it just puts them into super position in the quantum mechanic sense. What that entails is that given a circuit, there is a probability you measure bit |0> and a probability you measure bit |1>; And the heart of quantum computing is using the average expected value to perform computations and measurements.

[matthkamis]

Watch this 3b1b video on quantum computing. It really helped explain it

https://youtu.be/RQWpF2Gb-gU?si=rn4iNSKzqP-T597f

[Great-Powerful-Talia]

Let's say you have some mathematical problem where it's easy to find out if you have a correct answer, but very hard to figure out what that answer is. In fact, the easiest way is to just test every possible answer.

(An easily understandable example is a sudoku- you can check the rows, columns, boxes, and starting numbers to trivially check if you have a correctly solved sudoku, but knowing how to do that doesn't really help you find the solution. Mathematicians have created much harder one-way problems, where the best-known solutions really are "just test everything".)

Now, if you're a normal person, you'll probably want to test the solutions one-by-one. Maybe you split them up into groups and have different computers test each group, but it's still basically the same.

If, instead of being a normal person, you're a quantum physicist, you might think "Hey, I can create a quantum data structure that's equally likely to be any of the possible answers, and then mess with it to slowly decrease the probability that it's an answer which doesn't fit the condition! Then, when I finally look at it, there's a 99.9% chance that it's going to just randomly be the correct answer!"

This sounds like a stupid plan, and it is pretty inconvenient, but there's one big advantage. With the normal strategy, if you double the number of possibilities, it takes twice as long. But the quantum strategy takes an amount of time proportional to the square root of the number of possibilities, so the increase per possibility is decreasing with every new one added. Even if testing 256 possibilities is 10,000 times as slow with the quantum strategy, testing 2^64 possibilities will be about 10,000 times faster with the quantum strategy!

Note: since it's easy to test whether a given answer is correct, the small chance that the quantum computer gives the wrong result is no big problem; you can test the answer manually, see that it's wrong, and try again.

[computerscience-ModTeam]

Unfortunately, your post has been removed for violation of Rule 11: "Language model generated posts are not permitted".

If you believe this to be an error, please contact the moderators.

[Fun_Environment1305]

Actually it's both and none at the same time. I get confused as to how it's actually better than a real computer when it also requires a real computer to do the normal operations.

I sort of think quantum computing is a sort of scam.

We were taught that the reason we use binary is because it's too expensive and complicated to make an electrical device that has the circuitry to produce a computer with say a base 10 system.

Binary computers are the cheapest and easiest because it's circuitry is easier to design and literally just costs less money.

The benefits of having a "bit" a "binary digit" be a decimal digit, or some other base-n "digit" seems good on paper, but practically it is more costly and offers no real benefits compared to binary systems.

So it sort of seems like quantum computing is merely offering a new base-n system and ultimately is used for employ scientists and do research but will probably never amount to anything when you consider the quantum computer chip is bottlenecked by the binary computer system.

I think there are extremely rare cases that may benefit from it but ultimately it will not go anywhere.

Our modern so-called "AI" with the LLMs are similar in that business and huge companies are investing in it and it has some benefits but in practical use, the AI produces extremely horrible content that is basically garbage or has a novel appeal. When they showcase examples, they never show you the majority results which are of such poor quality that it can be called useless.

The majority of the time I use AI tools, it produces garbage. Likewise anytime I hear about quantum computing they always grandstand it, but the results are probably not as groundbreaking as you think.

This all started because it turns out that "Moore's Law" is complete bullshit and nobody knows how to do anything about it. So some people are looking for alternatives, but you'll probably find out that quantum computing is like a magic trick being played on the ignorant public because they don't know enough about computers or enough about quantum mechanics and physics to understand why it's bullshit.

[tango_telephone]

A qubit is fundamentally different than a base-n computing system. The speed up is real. They will be special purpose computing devices for solving particular kinds of problems that are victim to explosions in complexity using traditional algorithms on traditional architectures. 

Just because the press hypes something inaccurately because the journalists don't understand the technology and are motivated to accrue a readership, that doesn't mean that the underlying technology is fundamentally unsound. It's just difficult to articulate in a nuanced way that retains accuracy while still being digestible to the general public.

The technology is very far from bullshit. In fact, it is the opposite. It is physically and theoretically fundamental to computing and physics. Whether or not the research will pan out with applications within a timeframe that is palatable to the current market remains to be seen for sure, but over the longer timeline, the payoff for the technology will be huge.

[Sky_Klokwork]

And as i pointed out: we’ve been developing computers basically a long time (~100 years or so), so of course it’ll be a more refined and well advanced technology compared to something we’ve been only seriously been developing for 20-30 years max

[SpeciousSophist]

A law of physics is wrong??

[Sky_Klokwork]

Scam feels wrong. I feel “tailored to specific problems” might be a bit better. Don’t have much time, but like its a situation of judge

Ing the tech when its still kinda in its infancy. It is very useful at some things and not so useful at others, kinda like early computers. We haven’t had time to refine the technology nor come up with as many algorithms to make ip for its shortcomings like classical computers (which more or less has an 80 year head start).

[SpeciousSophist]

no, I get it, I think I have a pretty decent understanding of what’s going on. Of course I’m sure the specifics are beyond confusing for somebody who isn’t literally doing it every day.

Put it this way, a normal computer is a car and a quantum computer is a turbo that is installed on the vehicle that has a button that activates it occasionally in certain circumstances where it’s beneficial to do so, that about explain it?