Infinite Salesmen problem?

  • Thread starter Mukilab
  • Start date
  • #1
73
0
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.
 

Answers and Replies

  • #2
35,646
12,213
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.
 
  • #3
365
11
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.
 
  • #4
73
0
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'
 
  • #5
212
30
A couple of points:

1) There exists no known quantum algorithm for solving NP-compete problems. The travelling 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).
 
  • #6
728
168
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.
 
  • #7
73
0
A couple of points:

1) There exists no known quantum algorithm for solving NP-compete problems. The travelling 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.
 
  • #9
73
0

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?
 
  • #10
487
3
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.
 
  • #11
73
0
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 realised 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.
 
Last edited:
  • #12
487
3
Apparently, that was the original purpose, then they realised 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.
 
  • #13
73
0
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
 
  • #14
73
0
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!
 
  • #15
487
3
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.
 
  • #16
728
168
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.
 
  • #17
73
0
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)
 
  • #18
728
168
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.
 
  • #19
73
0
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?
 
  • #20
728
168
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.
 
  • #21
73
0
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.
 
  • #22
728
168
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.
 
  • #23
73
0
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!)
 
  • #24
728
168
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.
 
  • #25
212
30
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).
 

Related Threads on Infinite Salesmen problem?

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
758
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
471
Top