Quantum Computing and the Infinite Salesmen Problem

[Mukilab]

Hi, I'm looking into quantum computing, and if you could forgive my naivety I was wondering whether the superposition of a qubit could produce a one-step solution to an infinite salesman problem?

The salesman problem is where a computer has to calculate the most efficient route for a man to take between x number of cities. Whilst a classical computer has to go through every single step and then select the most efficient one, I have read that a quantum computer can do every single step simultaneously and then from that find the most efficient one.

Does that mean that the superposition of a qubit allows for it to solve a problem where there are a near infinite number of cities, all in one step? What are the implication of this if it is true? Surely there would be almost no time required to solve any problem.

Furthermore how is this superposition utilised? What is the point of having a superposition if it will collapse when we measure it anyway?

Thank you very much for your time. I understand that some of my knowledge may be wrong, I just hope that you have the patience to deal with me.

 

[mfb]

I think you will need more than one qubit. Then you have to work with those qubits - "calculate" path lengths via special operations on those qubits.
A large number of cities will probably need a large number of qubits, too.

The solving time for problems can go down significantly. But a quantum computer is not a magic box which returns the result of any calculation in an instant.

What is the point of having a superposition if it will collapse when we measure it anyway?

The measured result depends on the superpositions which were manipulated.

 

[DocZaius]

The notion that quantum computers could solve NP-Complete problems (like the traveling salesman) in polynomial time by "trying all possible solutions in parallel" is a misconception. That misconception is really widespread though so it's understandable most people get this "easy" but wrong explanation about how quantum computers work.

 

[Mukilab]

I think you will need more than one qubit. Then you have to work with those qubits - "calculate" path lengths via special operations on those qubits.
A large number of cities will probably need a large number of qubits, too.

The solving time for problems can go down significantly. But a quantum computer is not a magic box which returns the result of any calculation in an instant.The measured result depends on the superpositions which were manipulated.

The notion that quantum computers could solve NP-Complete problems (like the traveling salesman) in polynomial time by "trying all possible solutions in parallel" is a misconception. That misconception is really widespread though so it's understandable most people get this "easy" but wrong explanation about how quantum computers work.

Please could you elaborate on how this superposition works then, in terms of what possible calculations it allows for? For example for one qubit do you now gain three possible states (Spin up/down/superposed)?

I'm struggling to understand how the salesman problem is solved at all. All I've read so far is making incredibly generalisations and not actually explained how qubits calculate things or how the superposition helps to calculate things.

Reading and watching explanations to quantum computing feels similar to being told when I was 6-7 that the Sun goes round the Earth and 'that's all you need to know dear'

 

[Zarqon]

A couple of points:

1) There exists no known quantum algorithm for solving NP-compete problems. The traveling salesman problem is however, NP-complete on in it's decision version. For regular NP-hard problems, the only known algorithm is that of Shore (which can be used e.g. to factor numbers into their prime components, which is an NP-hard problem).

2) Superposition states of qubits are infinitely many, i.e. you can pick any constants a and b and form an arbitrary superposition: a|0> + b|1>. However, when you read the state out, you can only ever get one answer, which will be either 0 or 1. Thus you have to ask your questions in a very special manner, to allow superpositions to be used during calculations, but not in your answer.

3) The superposition property is by itself not enough to allow quantum speed up, but some form of non-local (non-classical) correlations between different qubits are required. Entanglement is a sufficient condition for this correlation (but not necessary, recent results show that something called quantum discord appears to be the minimum correlation needed).

 

[cosmik debris]

The use of superposition in quantum computing is just one of the steps in an algorithm. Superposition is usually used to generate all the possible answers to a particular problem and encode them into a number of qubits. Usually this means that all the answers have the same probability when the register is read. Some technique must then be used to select the "right" answer.

In salesmen type problems, which are searches or inverting functions, you can use Grover type algorithms for enhancing the probability of the correct answer. Grover's algorithm executes in O(sqrt(N)) rathe than the average N/2 for a normal classical search.

 

[Mukilab]

A couple of points:

1) There exists no known quantum algorithm for solving NP-compete problems. The traveling salesman problem is however, NP-complete on in it's decision version. For regular NP-hard problems, the only known algorithm is that of Shore (which can be used e.g. to factor numbers into their prime components, which is an NP-hard problem).

2) Superposition states of qubits are infinitely many, i.e. you can pick any constants a and b and form an arbitrary superposition: a|0> + b|1>. However, when you read the state out, you can only ever get one answer, which will be either 0 or 1. Thus you have to ask your questions in a very special manner, to allow superpositions to be used during calculations, but not in your answer.

3) The superposition property is by itself not enough to allow quantum speed up, but some form of non-local (non-classical) correlations between different qubits are required. Entanglement is a sufficient condition for this correlation (but not necessary, recent results show that something called quantum discord appears to be the minimum correlation needed).

The use of superposition in quantum computing is just one of the steps in an algorithm. Superposition is usually used to generate all the possible answers to a particular problem and encode them into a number of qubits. Usually this means that all the answers have the same probability when the register is read. Some technique must then be used to select the "right" answer.

In salesmen type problems, which are searches or inverting functions, you can use Grover type algorithms for enhancing the probability of the correct answer. Grover's algorithm executes in O(sqrt(N)) rathe than the average N/2 for a normal classical search.

Thank you for your replies. I just watched a lecture by Scott Aaranson on NP/P etc problems so I think I've grasped the limitations of quantum computers and I'm beyond thinking they are a solution to any feasible problem.

He talked about quantum computers using amplitudes of particles (and their subsequent interference) to do calculations. Could you please explain this further? How can one use amplitudes at all since surely you can't choose where they interfere, and if you are choosing where they interfere then surely you know the answer to the problem anyway? (You are just arranging the electrons to come up with that answer)

"Thus you have to ask your questions in a very special manner, to allow superpositions to be used during calculations, but not in your answer." Please could you explain how these superpositions are used? I feel like I will not understand quantum computers until I understand how this occurs.

I thought quantum entanglement was only necessary in order to preserve superposition (once I figure out what that contributes haha)? I will research further on your words, thank you.

"Superposition is usually used to generate all the possible answers to a particular problem and encode them into a number of qubits. Usually this means that all the answers have the same probability when the register is read" Please could you explain this further?


Thank you once again.

 

[martinbn]

Try these http://www.quiprocone.org/Protected/DD_lectures.htm lectures.

 

[Mukilab]

Try these http://www.quiprocone.org/Protected/DD_lectures.htm lectures.

Thank you. I've just read your post so I will get on it today. In the meantime I read an article in the Scientific American which states:

"Put another way, we can store 10^ 300 numbers on our 1,000 particles simultaneously. Then, by performing various operations on the particles and on some auxiliary ones—perhaps hitting them with a sequence of laser pulses or radio waves—we can carry out an algorithm that transforms all 10^ 300 numbers (each one a potential solution) at the same time. If at the end of doing that we could read out the particles’ final quantum state accurately, we really would have a magic computer: it would be able to check 10^ 300 possible solutions to a problem, and at the end we could quickly discern the right one."

But surely if you knew which sequence of laser pulses/radio waves to send, then you would know the answer anyway?

 

[ImaLooser]

I'm no expert, but the impression I get is that the main use of quantum computers is in simulating quantum systems. Problems like finding the shape of a protein given its AA sequence.

 

[Mukilab]

I'm no expert, but the impression I get is that the main use of quantum computers is in simulating quantum systems. Problems like finding the shape of a protein given its AA sequence.

Apparently, that was the original purpose, then they realized that computational power of qubits expanded exponentially rather than polynomially, hence they are trying to apply it to other areas.

Edit: Just watched another lecture, this time by Michael Nielsen. Simulating quantum systems is still one of the main aims of quantum computing it just has not been achieved yet.

 

[ImaLooser]

Apparently, that was the original purpose, then they realized that computational power of qubits expanded exponentially rather than polynomially, hence they are trying to apply it to other areas.

Edit: Just watched another lecture, this time by Michael Nielsen. Simulating quantum systems is still one of the main aims of quantum computing it just has not been achieved yet.

What are the other aims, may I ask? I don't have the patience to watch lectures.

 

[Mukilab]

What are the other aims, may I ask? I don't have the patience to watch lectures.

One of the main aims is to be able to solve the RSA-security which is the predominant encryption on the internet. It multiplies two prime numbers to get a 300 digit number. A supercomputer would take years-decades to solve this kind of thing since computer power expands exponentially, but since quantum computing power expands exponentially, such problems such as RSA encryption will be solved very easily.

However there are many different algorithms quantum computing is being made for, i.e. D-Wave, a quantum computing company in Canada is developing them for visual recognition.That does not mean that quantum computers are just the final goal of everything, they have huge limitations too. Don't assume them to be able to solve absolutely everything, in no time at all. Some problems are only solved quadratically as fast (i.e. instead of ^n, they are ^(n/2)). One of the main downsides is that you need to develop new algorithms for the same operations on quantum computers

 

[Mukilab]

I understand how superposition is used now however I've stumbled on a new thing which I am confused about (and which lectures don't seem to address).

If you are using an algorithm to send waves such that you create constructive and destructive amplitudes among the qubits to get a high chance of you getting the right answer, then surely you know the answer anyway, otherwise how would you know to send that sequence of waves (and which waves to send)?

I understand that these waves are sent by an algorithm, however with an algorithm you need different variables each time to get a different answer, whilst I cannot see new variables with quantum computing, since you are using the same base number of qubits, so surely you would get the same answer every single time with the same algorithm?


Thank you for your replies!

 

[ImaLooser]

If you are using an algorithm to send waves such that you create constructive and destructive amplitudes among the qubits to get a high chance of you getting the right answer, then surely you know the answer anyway, otherwise how would you know to send that sequence of waves (and which waves to send)?

Maybe this can be done by knowing certain properties of the answer.

 

[cosmik debris]

I understand how superposition is used now however I've stumbled on a new thing which I am confused about (and which lectures don't seem to address).

If you are using an algorithm to send waves such that you create constructive and destructive amplitudes among the qubits to get a high chance of you getting the right answer, then surely you know the answer anyway, otherwise how would you know to send that sequence of waves (and which waves to send)?

I understand that these waves are sent by an algorithm, however with an algorithm you need different variables each time to get a different answer, whilst I cannot see new variables with quantum computing, since you are using the same base number of qubits, so surely you would get the same answer every single time with the same algorithm?


Thank you for your replies!

I think the answer here is that you don't know the right answer but the system as a whole does. Don't forget that things like probability amplitudes are not observable but can be manipulated. In Grover's search for example, you use a function that "knows" the answer to first invert the phase of the probability amplitude and secondly invert this amplitude about the mean of all the amplitudes. This has the effect of increasing the amplitude of the right answer and reducing all the rest. If read at the right time you will have a high probablilty of the right answer.

 

[Mukilab]

I think the answer here is that you don't know the right answer but the system as a whole does. Don't forget that things like probability amplitudes are not observable but can be manipulated. In Grover's search for example, you use a function that "knows" the answer to first invert the phase of the probability amplitude and secondly invert this amplitude about the mean of all the amplitudes. This has the effect of increasing the amplitude of the right answer and reducing all the rest. If read at the right time you will have a high probablilty of the right answer.

Thank you.

So how would one convert these amplitudes, which are complex numbers, into integers (such as the test that found that 3*5=15 with a high probability)

 

[cosmik debris]

Thank you.

So how would one convert these amplitudes, which are complex numbers, into integers (such as the test that found that 3*5=15 with a high probability)

You don't. The amplitudes are not observable as I said before. When you read a qubit you get a 0 or a 1 randomly with a probability of the square of the amplitude.

 

[Mukilab]

You don't. The amplitudes are not observable as I said before. When you read a qubit you get a 0 or a 1 randomly with a probability of the square of the amplitude.

Sorry could you explain this?

I believed that you get results through interference, i.e. constructive interference will heighten the probability of a certain amplitude being found. I thought that 'amplitude' denotes on of the possible states of the entire qubit system, and is a complex number.

So if you have two qubits, one amplitude would be 1,0. I also thought this was a complex number, so how is it converted into an integer?

 

[cosmik debris]

Sorry could you explain this?

I believed that you get results through interference, i.e. constructive interference will heighten the probability of a certain amplitude being found. I thought that 'amplitude' denotes on of the possible states of the entire qubit system, and is a complex number.

So if you have two qubits, one amplitude would be 1,0. I also thought this was a complex number, so how is it converted into an integer?

The 0 and 1 are interpretations of two distinct states, just as they are in a classical computer. A classical logic circuit may have 3.5 volts as a 1 and 0 volts as a 0, or it could be -27.5 volts for a 1 and 56.3 volts as a 0, it doesn't matter.

In quantum mechanics the amplitudes (what you are calling complex numbers) are not observable, they only affect the probability of you getting a one state or another. These two states are labelled 0 and 1. I suggest you read up on measurement in quantum mechanics.

 

[Mukilab]

The 0 and 1 are interpretations of two distinct states, just as they are in a classical computer. A classical logic circuit may have 3.5 volts as a 1 and 0 volts as a 0, or it could be -27.5 volts for a 1 and 56.3 volts as a 0, it doesn't matter.

In quantum mechanics the amplitudes (what you are calling complex numbers) are not observable, they only affect the probability of you getting a one state or another. These two states are labelled 0 and 1. I suggest you read up on measurement in quantum mechanics.

I'm sorry, I don't understand.

In a classical system you have two possible results i.e. as you said it may be (+) volts for 1, and (-) volts for 0. However these are the final results.

For qubits, although yes there are 1s and 0s, the answers are the amplitudes, which are 2^n many, rather than just one of two answers in the classical system (1 or 0). In classical computing these 1s and 0s have to be strung together to form an integer, however in quantum computing the amplitudes themselves are already integers.

My question is how can amplitudes be converted to integers, in the same way classically 1s and 0s are strung together to be converted to readable integers.


I thought that an amplitude was a certain state, that is, a collection of the states of several qubits, hence what is the difference between getting an amplitude and getting a state?


Thank you for your time.

 

[cosmik debris]

I think I have said three times now: amplitudes are not observable. When you read a quantum register it is read as a binary number just as it is in a classical computer. The bits of this register only have values of 0 or 1 just as they do in a classical computer. The difference between a quantum register and a classical one is that the value of each bit (0 or 1) and therefore the value of the register as a whole is probabilistic. If you have three bits and the top bit has a probability of one-half of being 0 or 1, and the other two bits have a probability of 1 of being 1, then the value of the three bits has a one-half probability of being 3 or 7.

 

[Mukilab]

I think I have said three times now: amplitudes are not observable. When you read a quantum register it is read as a binary number just as it is in a classical computer. The bits of this register only have values of 0 or 1 just as they do in a classical computer. The difference between a quantum register and a classical one is that the value of each bit (0 or 1) and therefore the value of the register as a whole is probabilistic. If you have three bits and the top bit has a probability of one-half of being 0 or 1, and the other two bits have a probability of 1 of being 1, then the value of the three bits has a one-half probability of being 3 or 7.

I am very sorry. Please could you explain how a quantum register converts whatever there is to convert into a binary number? Disregard amplitudes, how do you get from a series of particles to a binary number?

Do you literally have to measure every single one and see whether it has spin up or down (although this will surely affect the whole system!)

 

[cosmik debris]

You can use any quantum system to represent the qubits as long as it has at least two distinguishable states. Spin states, polarisation, energy states of an atom etc can be used. Yes, you have to be able to change the state and measure the state of each entity that you use for a qubit. This is an active area of research, if you do a search you will find ion traps, NMR systems, and an obscure method called adiabatic quantum computing.

 

[Zarqon]

In order for you to get to an arbitrary number from the measurements of 0 and 1, you have to either repeat the experiment many times, or have a series of parallel qubits that do the same thing. If you repeat the experiment a hundred times and you get 0 half of the time and 1 half of the time, then your probabilities are close to 0.5 each. Though note that to also determine the phase of the state you in addition also have to perform measurements in a rotated basis.

The more experiments you perform, the closer you get to the "real" state value, where the statistical error for determining the "real" value typically go down as \sqrt(n).

 

[Zarqon]

"Thus you have to ask your questions in a very special manner, to allow superpositions to be used during calculations, but not in your answer." Please could you explain how these superpositions are used? I feel like I will not understand quantum computers until I understand how this occurs.

A simple algorithm to start with to get a feeling for what's going on, is the Deutsch-Jozsa algorithm. Explained in a handwaving (and wrong, but just to get a feeling for things) manner, consider a function f, that can be either even or odd, meaning given f(x) the function can either return +0.5 for both positive and negative values, or +0.5 for positive and -0.5 for negative, and your task is to determine which it is.

Classically, you would have no choice but to compute the function twice, for both positive and negative inputs, and then check whether they are the same or not. There is no other way. Using quantum superposition states however, we can simple compute the function for a superposition of a positive and negative value, and let the answer of our algorithm correspond to , say, the sum of the outputs (i.e. either +0.5 +0.5=1 for even, or +0.5-0.5=0 for odd function). We now see that even though the answer is only one single bit (1 or 0) we gain information about a global property of the whole function by only one single evaluation.

This is what I meant with "you have to ask the questions in s special manner". By using a quantum algorithm, we don't perform the two computations faster, but rather we rephrase the question to take advantage of the superpositions (and entanglement) in order to obtain the answer to the originial question in the different, more efficient way.

 

[Mukilab]

Sorry for my late reply, I've been very busy recently.

So since a probability amplitude is a collection of quantum states, then surely the probability amplitude denoting the state (101) is the same as the one denoting (110) since both states have two electrons with spin up and one electron with spin down? Or does probability amplitude also vary with the order of qubits?

Furthermore when we read out, as you have said, the 1s and 0s on our quantum register, how do we know what our 1s and 0s denote? For example if we measure our system to measure the system and find that the system is in the state (001), how do we know that this denotes to the number 7 for example?

Also, are there different interpretations for what a state may mean? For example in one experiment could 001=7 and in another experiment could 001 again equal a number such as 3?

Thank you very much.

 

[mfb]

The state (101) is different from the state (110) if you interpret it as (qubit1,qubit2,qubit3), they can be independent.

 

[cosmik debris]

Sorry for my late reply, I've been very busy recently.

So since a probability amplitude is a collection of quantum states, then surely the probability amplitude denoting the state (101) is the same as the one denoting (110) since both states have two electrons with spin up and one electron with spin down? Or does probability amplitude also vary with the order of qubits?

No, the probability amplitude is the coefficient of the vector which describes the quantum state. When you put a register into a superposition of states the probability amplitude of each state can be anything as long as they all sum to 1. The probability of a collection of qubits is a combination of the probabilities of the individual qubits. You have completely the wrong idea here.

Furthermore when we read out, as you have said, the 1s and 0s on our quantum register, how do we know what our 1s and 0s denote? For example if we measure our system to measure the system and find that the system is in the state (001), how do we know that this denotes to the number 7 for example?

This is a form of coding they can mean whatever you want them to mean, but in this context they are binary numbers.

Also, are there different interpretations for what a state may mean? For example in one experiment could 001=7 and in another experiment could 001 again equal a number such as 3?

Thank you very much.

See above, they are usually interpreted as binary numbers.

 

[Mukilab]

No, the probability amplitude is the coefficient of the vector which describes the quantum state. When you put a register into a superposition of states the probability amplitude of each state can be anything as long as they all sum to 1. The probability of a collection of qubits is a combination of the probabilities of the individual qubits. You have completely the wrong idea here.

This is a form of coding they can mean whatever you want them to mean, but in this context they are binary numbers.

See above, they are usually interpreted as binary numbers.

If it is coding - then surely different coding may be used in different situations, creating an event where one research group codes the state 010 as the binary digits representing 7 whilst another group codes the same state but represents it as a 4.

Since coding is arbitrary, how can we know what state actually represents which number?

 

[mfb]

You can define "0", "1" and its interpretation in any way you like, you just have to do it consistently in the preparation of the states and the interpretation of the results.

In a similar way, you can compute 2+4 on every conventional computer, and get 6 independent of the details of the implementation in hardware (or maybe 5.9999 with some bugged CPUs ;)).