Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite Salesmen problem?

  1. Oct 24, 2012 #1
    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.
  2. jcsd
  3. Oct 24, 2012 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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.
  4. Oct 24, 2012 #3
    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.
  5. Oct 24, 2012 #4
    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'
  6. Oct 25, 2012 #5
    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).
  7. Oct 25, 2012 #6
    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.
  8. Oct 26, 2012 #7
    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. Oct 26, 2012 #8


    User Avatar
    Science Advisor

  10. Oct 26, 2012 #9
    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?
  11. Oct 26, 2012 #10
    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.
  12. Oct 26, 2012 #11
    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: Oct 26, 2012
  13. Oct 26, 2012 #12
    What are the other aims, may I ask? I don't have the patience to watch lectures.
  14. Oct 27, 2012 #13
    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
  15. Oct 27, 2012 #14
    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!
  16. Oct 28, 2012 #15

    Maybe this can be done by knowing certain properties of the answer.
  17. Oct 29, 2012 #16
    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.
  18. Oct 30, 2012 #17
    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)
  19. Oct 30, 2012 #18
    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.
  20. Oct 31, 2012 #19
    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?
  21. Oct 31, 2012 #20
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook