Quantum Computing: How are quantum properties exploited?

[expos4ever]

TL;DR Summary

While I believe I understand the quantum concepts of superposition, entanglement, and (wave) interference, I do not understand how these are directed / harnessed to solve a problem

To elaborate a little on what I think I do understand / accept:

1. I don't think I have a problem accepting the "weirdness" of quantum concepts. So, for example, I am willing to accept the concept that a quantum system can "exist" in a large number of different states simultaneously.

2. I believe I understand how n qubits can represent "2 to the n" information states at the same time.

3. I believe I understand how information can be encoded in correlations between entangled qubits.

4. I understand the concept of constructive and destructive interference between different waves.

5. I believe I understand the concept of decoherence.

In brief, I believe I understand the basics of superposition, entanglement, interference, and decoherence - I just don't understand how these are harnessed / directed to solve a problem. I am not so much concerned with the "mechanics" of how you would actually build such a computer; I am more interested in an "information-theory" kind of abstract explanation of how these various quantum concepts can be "directed".

If you can offer any assistance, perhaps in the form of a reference to a good explanation, that would be greatly appreciated. If this is too "large" a question to be tackled in this forum (i.e. if I am too much of a noob, don't be shy in saying so). Thanks.

 

[FactChecker]

I may be interpreting your question in too simple a way, but here are my two cents:
First of all, the advantage of a quantum computer is in finding the solution of problems, A, where finding the solution requires a great number of combinations. Many problems are not like that and the QC has no advantage. Suppose we have a combinatorial problem with n binary options to consider.
Traditional computer:
step 1: check if (0,0,0,0,0,...,0) solves A
step 2: check if (1,0,0,0,0,...,0) solves A
step 3: check if (0,1,0,0,0,...,0) solves A
step 4: check if (1,1,0,0,0,...,0) solves A
...
step 2^n: check if (1,1,1,1,1,...,1) solves A
On average, this will require 2^(n-1) steps to solve, but it might require all 2^n steps if the solution is (1,1,...,1).
For n up around 60, this could require millions of years even on the fastest supercomputers.

Quantum Computer:
Formulate the problem "find the qubits, (q1,q2,q3,...,qn), that solve problem A". THIS CAN BE VERY DIFFICULT!
Set up the QC to solve that formulation.
Run the QC.
BOOM! Through the magic of superposition and entanglement, q1=1, q2=0, q3=0, q4=1, q5=1, ... , qn=1.
Interpret the QC result to get that (1,0,0,1,1,0,...,1) solves A
Even if this process takes some time (days?), compare it with the millions of years that a traditional supercomputer would require.

 

[expos4ever]

I may be interpreting your question in too simple a way, but here are my two cents:
First of all, the advantage of a quantum computer is in finding the solution of problems, A, where finding the solution requires a great number of combinations. Many problems are not like that and the QC has no advantage. Suppose we have a combinatorial problem with n binary options to consider.
Traditional computer:
step 1: check if (0,0,0,0,0,...,0) solves A
step 2: check if (1,0,0,0,0,...,0) solves A
step 3: check if (0,1,0,0,0,...,0) solves A
step 4: check if (1,1,0,0,0,...,0) solves A
...
step 2^n: check if (1,1,1,1,1,...,1) solves A
On average, this will require 2^(n-1) steps to solve, but it might require all 2^n steps if the solution is (1,1,...,1).
For n up around 60, this could require millions of years even on the fastest supercomputers.

Quantum Computer:
Formulate the problem "find the qubits, (q1,q2,q3,...,qn), that solve problem A". THIS CAN BE VERY DIFFICULT!
Set up the QC to solve that formulation.
Run the QC.
BOOM! Through the magic of superposition and entanglement, q1=1, q2=0, q3=0, q4=1, q5=1, ... , qn=1.
Interpret the QC result to get that (1,0,0,1,1,0,...,1) solves A
Even if this process takes some time (days?), compare it with the millions of years that a traditional supercomputer would require.

I appreciate the reply. However, I do not understand how this addresses my question. I think I am 100% with you on every detail of your analysis of the traditional computer. However - and please forgive me if I do not understand what you are getting at - when you write this:

BOOM! Through the magic of superposition and entanglement, q1=1, q2=0, q3=0, q4=1, q5=1, ... , qn=1.
Interpret the QC result to get that (1,0,0,1,1,0,...,1) solves A

...it seems to me that you are effectively just reformulating my question. It is precisely this "magic" and this "interpretation" that I am trying to understand: I accept and understand (I think) superposition and entanglement - I just don't see how we "engineer" these properties to solve a problem.

Again, thanks for the reply and I hope you do not take offence that I do not, at least at the moment, see how this addresses my question.

 

[FactChecker]

Again, thanks for the reply and I hope you do not take offence that I do not, at least at the moment, see how this addresses my question.

No offense at all. That is exactly what I was wondering. I just thought that it was best to start at the beginning. So you are asking about how the QC is set up to solve that problem. There are a couple of very different approaches.
One company, D-Wave Systems, makes a QC with a large network of qubits (thousands) and "weight" parameters on the connections that allow it to solve a problem through annealing. It starts at a low energy state and slowly rises to a solution, guided by the parameters. Setting the parameters for a particular problem is a puzzle in itself. There is debate about whether this work has so far shown a quantum speed.
There are other companies, like IBM, that are building smaller quantum chips (a few dozen qubits) that allow more traditional logic.
I am afraid that I would soon get over my head on either of these and will leave any further discussion to those who know more about it.

 

[f95toli]

...it seems to me that you are effectively just reformulating my question. It is precisely this "magic" and this "interpretation" that I am trying to understand: I accept and understand (I think) superposition and entanglement - I just don't see how we "engineer" these properties to solve a problem.

I don't believe there is a simple universal answer to this question; it varies depending on the algorithm. A QC has extra "resources" that classical computers do not have and the challenge is to find algorithm that can utilise these in a way that will give you a speedup. This is very, very hard and if you look around you will notice that there aren't actually that many algorithms around; and even fewer that are practical. Fortunately, it turns out that some of the algorithms we do have are very useful.

Note also that algorithms for NISQ processors -which is what we will have for the next 10 years or so- are inherently very different from more well known algorithm's such as Shor's; in algorithms for NISQ machines (see e.g. VQE solver) the quantum processor is used as an auxiliary processor and is only doing one or two steps of the algorithm. Most steps as well as the overall flow control is handled by a classical computer.

 

[phinds]

A QC has extra "resources" that classical computers do not have and the challenge is to find algorithm that can utilise these in a way that will give you a speedup.

For me, and I suspect for the OP, this is just more hand waving that does nothing, really, but reformulate the OPs question. Like him, I am completely puzzled by how a QC actually DOES what it apparently does.

Possibly, like some other issues in physics, the answer lies deep in the math and talking about it in English just isn't going to work.

 

[f95toli]

For me, and I suspect for the OP, this is just more hand waving that does nothing, really, but reformulate the OPs question. Like him, I am completely puzzled by how a QC actually DOES what it apparently does.

My point is that there isn't a single answer; you have to look into the details for each specific algorithm. You can give hand-wavy answers such as "whereas a classical bit only has an amplitude, a qubit has both amplitude and phase. We can create algorithms by applying a series of gate operations to qubits or pairs of qubits"
This is all correct but it doesn't really tell you how to solve a problem.

That said, a statement such as "a classical computer consists of bits can be in one of two states, we solve problems by applying a series of gate operations to bits or pairs of bits" is also correct; but again I don't think it tells you much.

 

[phinds]

That said, a statement such as "a classical computer consists of bits can be in one of two states, we solve problems by applying a series of gate operations to bits or pairs of bits" is also correct; but again I don't think it tells you much.

That's a good point.

 

[Dali]

I think this in an excellent question, and agree it is kind of hard to answer without going into the full details of a specific quantum algorithm. I will try however to formulate my understanding of what I guess is the key question here - more precisely how does a quantum computer utilize quantum weirdness to actually do useful computations?

First - as pointed out above - a quantum computer ("QC") is only effective on certain very specific problems. There is no general way to utilize superpositions, entanglement etc to solve "simple" problems like adding numbers, performing a matrix multiplication or similar. So far, all smart quantum algorithms that have been found so far only works for very specific problems that are hard to solve, but easy to check once you have a solution candidate (NP-problems). Like for example Peter Shor's famous quantum algorithm for factorizing a large number C, where the difficulty of finding the factors A*B = C grows exponentially with the number of digits in C, but checking the correctness by multiplying A*B is just one single operation.

The key in all known quantum algorithms is to utilize superpositions and coupling between qubits in a smart way.

A quantum register x is a set of N qubits that can represent any number between 0 and 2^N-1 (just like an ordinary byte or variable in a classical computer). But because all individual qubits can be in superpositions of both states 0 and 1 simultaneously, such a quantum register x can be in a state that represents all 2^N (-1) states simultaneously. If we now also can apply quantum gates (such as a AND, OR, or NOT) between qubits without measuring them (without too much decoherence), we can apply a transform on x to take it to any f(x). Actually one can show that with enough C-NOT gates, it is possible to implement any such function f(x) in a quantum computer.

But, just putting x in a superposition and calculating f(x) does not give us anything new. Even if x starts in a superposition of all possible input values, and we can apply quantum gates to transform it into a superposition of all possible f(x), a final measurement of just gives one of f(x)'s possible values at complete random.

What one has to do is to find specific transformations that tells us something useful even when we just can read out one specific value at the end. For example, let's say we want to find the unknown periodicity of the function f(x). (This is in fact mathematically equivalent to finding a prime factor of another number C...). Then we start with our register in state x as a superposition of all possible inputs, apply our function f(x), but then we don't measure or read out f(x), but instead applies further quantum gates representing a Fourier transform on f(x). Then in the end our register will be in a superposition of all possible values of the Fourier transform of f(x). When we finally read out the state of our register, the superposition collapses and we still get only one value out of the measurement. But this value is now with high probability close to one of the fundamental frequencies of f(x). We can then easily check that solution with a classical computer.

So the quantum computer used superpositions and quantum transformations to make one very good guess of the original hard problem. That guess is easy to check if it is correct or not. If it is wrong, we just runt the quantum algorithm again until we find a correct answer. It might take a few trials to find the solution. But the quantum computer has helped us finding very likely candidates instead of having to try out every possibility for ourselves like a classical computer would have to do. And thus reduced the problem from something that grew exponentially with the size of the input to something that only needs a polynomial number of steps.