## Quantum Computing Uses

**Moderators:** gmalivuk, Moderators General, Prelates

### Quantum Computing Uses

I've been somewhat exposed to it via classes and presentations, but I just don't think I have a grasp on what all this really means. They all seem to go too much into theory and mathiness into "qubits can be zeros and ones at the same time" or "looking at a result affects the system." This just makes it seem not very useful to me. What useful info is in a piece of data if it's both 0 and 1 with a 50% chance of each? If looking at it affects the data, how can you be sure the data is correct?

### Re: Quantum Mechanics Uses

Entanglement is a pretty useful aspect too, so you can end up with a system of qubits with a particular configuration of 1's and 0's with a certain probability and a variety of different configurations with different probabilities (and they're not simply the products of a whole bunch of probabilities of individual qubits).

You might start with a bunch of independent qubits with 50:50 chance of being 1's or 0's, and that's not super useful at that stage, but the idea is to then evolve that system (perhaps by introducing particular magnetic fields for example) into something with different probabilities.

There's a few different methods of quantum computing, but in at least one way you could theoretically set things up so that your system has say, a 90% chance of being in a configuration that represents the solution to your problem, and simply repeat that process a number of times until you're sufficiently confident that the answer you got most often is indeed the correct answer. (Or in a number of problems, it's possible to quickly check if a solution is indeed a solution e.g. factoring).

You might start with a bunch of independent qubits with 50:50 chance of being 1's or 0's, and that's not super useful at that stage, but the idea is to then evolve that system (perhaps by introducing particular magnetic fields for example) into something with different probabilities.

There's a few different methods of quantum computing, but in at least one way you could theoretically set things up so that your system has say, a 90% chance of being in a configuration that represents the solution to your problem, and simply repeat that process a number of times until you're sufficiently confident that the answer you got most often is indeed the correct answer. (Or in a number of problems, it's possible to quickly check if a solution is indeed a solution e.g. factoring).

### Re: Quantum Mechanics Uses

So the idea here is that we are sacrificing accuracy for speed? Quantum computing would be faster but less accurate, and by repeating this faster algorithm multiple times, we can be more sure of its results, hoping it has a faster O-bound in the long run?

### Re: Quantum Mechanics Uses

I should say I am not an expert on the subject. It was the subject of my undergrad honours project so I know a fair bit, but still, undergrad level. I'm primarily familiar with adiabatic quantum computing, so other flavours of quantum computing might work differently.

Quantum is probabilistic in nature, so it makes sense that many quantum algorithms would give correct results with a probability of less than 100%. I don't know that quantum computing is necessarily faster than classical (it could be, but I don't think that's been shown), and there are plenty of probabilistic classical algorithms out there so I'm hesitant to say you're sacrificing accuracy. Again, there's many problems where it's easy to check if an answer is correct, and so in those instances you can repeat the process until you get a correct answer with certainty. Even for other sorts of problems, you can keep repeating it until you're 99.999...9% (arbitrary but finite number of 9's) certain of the result, which with enough 9's is probably comparable to a classical algorithm which gives a 'certain' result.

It might be that the best (not necessarily known) quantum algorithms scale better than the best (not necessarily known) classical for certain kinds of problems, but classical is better than quantum for others, but I don't know, and I don't know if anyone does yet. There's lots of potential there though since intuitively one would expect a (qu)bit which can be in some sense simultaneously 1 AND 0 to be more powerful than something constrained to be 1 xor 0, not to mention entanglement allowing all sorts of interesting states that one couldn't get classically. Of course intuition only goes so far so there's a lot more research to be done, but it's one possible avenue to the future of computing (particularly as classical chips get so small that quantum mechanical effects begin to take over anyway).

Quantum is probabilistic in nature, so it makes sense that many quantum algorithms would give correct results with a probability of less than 100%. I don't know that quantum computing is necessarily faster than classical (it could be, but I don't think that's been shown), and there are plenty of probabilistic classical algorithms out there so I'm hesitant to say you're sacrificing accuracy. Again, there's many problems where it's easy to check if an answer is correct, and so in those instances you can repeat the process until you get a correct answer with certainty. Even for other sorts of problems, you can keep repeating it until you're 99.999...9% (arbitrary but finite number of 9's) certain of the result, which with enough 9's is probably comparable to a classical algorithm which gives a 'certain' result.

It might be that the best (not necessarily known) quantum algorithms scale better than the best (not necessarily known) classical for certain kinds of problems, but classical is better than quantum for others, but I don't know, and I don't know if anyone does yet. There's lots of potential there though since intuitively one would expect a (qu)bit which can be in some sense simultaneously 1 AND 0 to be more powerful than something constrained to be 1 xor 0, not to mention entanglement allowing all sorts of interesting states that one couldn't get classically. Of course intuition only goes so far so there's a lot more research to be done, but it's one possible avenue to the future of computing (particularly as classical chips get so small that quantum mechanical effects begin to take over anyway).

- gmalivuk
- GNU Terry Pratchett
**Posts:**26739**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Quantum Computing Uses

I changed the title from "mechanics" to "computing", because that's what the OP is actually asking about. (QM itself, of course, is how we have things like lasers and transistors, and I'm pretty sure no one is questioning how those things can be useful.)

- doogly
- Dr. The Juggernaut of Touching Himself
**Posts:**5530**Joined:**Mon Oct 23, 2006 2:31 am UTC**Location:**Lexington, MA-
**Contact:**

### Re: Quantum Computing Uses

No practical problems have been solved with a quantum computer yet. Very hard to build.

In order for a quantum computer to be useful at solving a problem, it has to have an algorithm for that problem that takes advantage of quantum mechanics. We have search and integer factoring algorithms, and I believe some for certain quantum chemistry problems. There aren't many algorithms for quantum computers.

The ones that do exist represent a speedup to an entirely different complexity class, however. So, boom!

But, without a quantum computer that can run these algorithms (engineers are so disappointing...) so far the biggest uses of quantum computing have been theoretical - we understand quantum mechanics significantly better, and we understand complexity classes significantly better. It is a theoretical lens which provides great clarity.

In order for a quantum computer to be useful at solving a problem, it has to have an algorithm for that problem that takes advantage of quantum mechanics. We have search and integer factoring algorithms, and I believe some for certain quantum chemistry problems. There aren't many algorithms for quantum computers.

The ones that do exist represent a speedup to an entirely different complexity class, however. So, boom!

But, without a quantum computer that can run these algorithms (engineers are so disappointing...) so far the biggest uses of quantum computing have been theoretical - we understand quantum mechanics significantly better, and we understand complexity classes significantly better. It is a theoretical lens which provides great clarity.

LE4dGOLEM: What's a Doug?

Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.

Or; Is that your eye butthairs?

Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.

Or; Is that your eye butthairs?

- eternauta3k
**Posts:**519**Joined:**Thu May 10, 2007 12:19 am UTC**Location:**Buenos Aires, Argentina

### Re: Quantum Computing Uses

I think they factored the number 15 at some point. Somewhat handy?doogly wrote:No practical problems have been solved with a quantum computer yet

And frustration. "We could solve this very efficiently if only this computer existed".doogly wrote:It is a theoretical lens which provides great clarity

### Re: Quantum Computing Uses

doogly wrote:No practical problems have been solved with a quantum computer yet. Very hard to build.

That's not quite true. The D-Wave machine appears to solve a subclass of Ising spin glass problem which are hard to write good classical solvers for. This class of problem is practical and useful, which is one of the reasons why Google and NASA are buying them for testing purposes.

Moreover, the machine appears to outperform generic classical solvers. Someone has (after the D-Wave machine was built) implemented a less generic classical solver for that particular problem which outperforms D-Wave. Nonetheless, that particular quantum computer apparently has solved practical problems.

- doogly
- Dr. The Juggernaut of Touching Himself
**Posts:**5530**Joined:**Mon Oct 23, 2006 2:31 am UTC**Location:**Lexington, MA-
**Contact:**

### Re: Quantum Computing Uses

d wave's successes are in marketing, not computing.

LE4dGOLEM: What's a Doug?

Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.

Or; Is that your eye butthairs?

Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.

Or; Is that your eye butthairs?

### Re: Quantum Computing Uses

doogly wrote:d wave's successes are in marketing, not computing.

I'd put it differently: The success that D-Wave has had in engineering is grossly overshadowed by over-hype and the fact that Geordie Rose is an irritating and condescending arsehole.

### Re: Quantum Computing Uses

From http://www.scottaaronson.com/blog/?p=1400

Scott Aaronson wrote:D-Wave: Truth finally starts to emerge

D-Wave founder Geordie Rose claims that D-Wave has now accomplished its goal of building a quantum computer that, in his words, is “better at something than any other option available.” This claim has been widely and uncritically repeated in the press, so that much of the nerd world now accepts it as fact. However, the claim is not supported by the evidence currently available. It appears that, while the D-Wave machine does outperform certain off-the-shelf solvers, simulated annealing codes have been written that outperform the D-Wave machine on its own native problem when run on a standard laptop. More research is needed to clarify the issue, but in the meantime, it seems worth knowing that this is where things currently stand.

### Re: Quantum Mechanics Uses

Dopefish wrote:Even for other sorts of problems, you can keep repeating it until you're 99.999...9% (arbitrary but finite number of 9's) certain of the result, which with enough 9's is probably comparable to a classical algorithm which gives a 'certain' result.

I recall reading somewhere [citation needed] that Shor's algorithm for example has a maximum efficiency of 50%, so if I've done my back-of-envelope sums properly you should only need to run it around 21 times to get the equivalent of 5 sigma? (Bad example as Shor's is for factorizing, so it's one of the easy ones to check)

### Who is online

Users browsing this forum: No registered users and 10 guests