Infinite Salesmen problem?

  • Thread starter Mukilab
  • Start date
  • #26
212
30
"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.
 
  • #27
73
0
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.
 
  • #28
35,649
12,214
The state (101) is different from the state (110) if you interpret it as (qubit1,qubit2,qubit3), they can be independent.
 
  • #29
728
168
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.
 
  • #30
73
0
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?
 
  • #31
35,649
12,214
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 ;)).
 

Related Threads on Infinite Salesmen problem?

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
759
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
788
  • Last Post
Replies
3
Views
2K
Top