How would observation of the state of qubits affect them?

[ant0n]

Firstly, I apologise for any lack of understanding, incorrect assumptions or misinterpretations of the very little I know about physics, quantum mechanics & quantum computing. I am not an academic, scientist or mathematician, but a software engineer with an interest in quantum computing and cryptography. With that in mind, my question may be stupid, but I was always told there's "no such thing as a stupid question" so I'll ask it anyway.

My very little understanding of quantum mechanics and superposition (and please correct me if I've got any of this wrong) is that the state of a quantum particle is not determined until it is observed, as proven by the double slit experiment, so in terms of quantum computing, a qubit can be both a zero and a one at the same time.
Does this mean that, for example, a 4 character string represented by qubytes with its qubits in an undetermined state would effectively be every combination that a 4 character string could be, at the same time?
Would that mean that theoretically a quantum computer with enough qubytes could guess a password in a single attempt by using a qubyte string with its qubits in an undetermined state?

If the above were true , how would observation of the qubit states work?
If my understanding is correct, then observation of the qubyte string BEFORE attempting to guess the password would cause the qubits to get determined values therefore creating a string e.g. "abcd".
But if the qubits were not observed and therefore in an undetermined state, and that string was used to guess the password (let's assume the password is "four"), if I observed the qubit states AFTER the password was guessed, would they reflect the value of the password i.e "four"?

 

[FactChecker]

Does this mean that, for example, a 4 character string represented by qubytes with its qubits in an undetermined state would effectively be every combination that a 4 character string could be, at the same time?

Yes.

Would that mean that theoretically a quantum computer with enough qubytes could guess a password in a single attempt by using a qubyte string with its qubits in an undetermined state?

Yes.

If my understanding is correct, then observation of the qubyte string BEFORE attempting to guess the password would cause the qubits to get determined values therefore creating a string e.g. "abcd".

Right. Observing the qubits prematurely would force them to a wrong solution. There must be an algorithm used to allow the qubits to solve the problem first. Then the qubits can be observed and the answer read. It can be difficult to design a solution algorithm even for very simple problems. A quantum algorithm is not a series of steps that are performed. It is an arrangement of the qubits and their connections that give the solution in one step. Shore's Algorithm is a famous algorithm to factor integers.

 

[Strilanc]

Does this mean that, for example, a 4 character string represented by qubytes with its qubits in an undetermined state would effectively be every combination that a 4 character string could be, at the same time?

That's one way to think about it, but there are caveats.

Would that mean that theoretically a quantum computer with enough qubytes could guess a password in a single attempt by using a qubyte string with its qubits in an undetermined state?

("FactChecker"'s reply is wrong about this.)

This is one of the caveats: when you measure, you only get one of the results. If you wrote a "put quantum computer into superposition of all passwords, check if correct" program, and then measured the result, you'd almost always get junk output like "I tried the password 'blargebla' and it was wrong".

To make the correct answer rise to the surface, you need to do fancy things such as Grover's algorithm, that cancel out the wrong answers. If there are $N$ possible passwords, you need to do ~$\sqrt{N}$ work to cancel out all the bad ones. That's better than classical, but very far from "one attempt".

If the above were true , how would observation of the qubit states work?

It's not true.

In a quantum logic circuit, observation/measurement is identical to performing a controlled-not onto an otherwise-unused qubit that was initialized to be zero.

If my understanding is correct, then observation of the qubyte string BEFORE attempting to guess the password would cause the qubits to get determined values therefore creating a string e.g. "abcd".
But if the qubits were not observed and therefore in an undetermined state, and that string was used to guess the password (let's assume the password is "four"), if I observed the qubit states AFTER the password was guessed, would they reflect the value of the password i.e "four"?

Only if you did operations that canceled out the wrong guesses first.

 

[bhobba]

My very little understanding of quantum mechanics and superposition (and please correct me if I've got any of this wrong) is that the state of a quantum particle is not determined until it is observed, as proven by the double slit experiment, so in terms of quantum computing, a qubit can be both a zero and a one at the same time.

The state is known at all times. However what the state does is help us calculate the probabilities of the outcomes of observations. The twist in QM is the theory is silent about properties like position, momentum etc until its observed to have those properties.

In the double slit what happens is this. First consider a single slit and for definiteness we will use electrons. The slit is a position measurement because just behind the slit it has a definite position. From the Heisenberg uncertainly principle if we then measure its momentum its totally unknown. The kinetic energy is unaffected so the square of its velocity is the same. This means the absolute value of the momentum doesn't change, but the direction is now unknown so when its detected at the screen behind the slit it is scattered. If we have two slits then a quantum principle, called the principle of superposition, comes into play. When we apply that and chug through the math you get an interference pattern.

Here is the full detail:
http://arxiv.org/ftp/quant-ph/papers/0703/0703126.pdf

It is not zero and one at the same time - the theory is silent about those properties until you observe it to have them. Popularisations will often say loose things like that to get the flavour of QM across to a lay audience, but here we generally try to be exact. It makes more demands in understanding terms, but the pay-off is you don't get yourself in knots trying to understand subtle phenomena.

Thanks
Bill

 

[ant0n]

Thanks for all of the replies.

Shore's Algorithm

I checked out Shor's Algorithm and this wiki article actually talks about it in terms of using it to crack public key encryption - it's an interesting read.

This is one of the caveats: when you measure, you only get one of the results. If you wrote a "put quantum computer into superposition of all passwords, check if correct" program, and then measured the result, you'd almost always get junk output like "I tried the password 'blargebla' and it was wrong".

I think this pretty much answers my question. I guess my real question was "would the act of cracking a password using qubits in superposition cause their values / states to become determined, without direct observation?" So if the password was cracked successfully, would that mean that observing the qubit states at the point of successfully guessing the password would reveal the actual password? I gather from your answers that this is not the case, and that observation would corrupt the result showing only a random possibility of the password and not the actual password itself, even though at some point, the qubits must have been in a state to reflect the correct password in order to crack it.

 

[FactChecker]

To make the correct answer rise to the surface, you need to do fancy things such as Grover's algorithm, that cancel out the wrong answers. If there are $N$ possible passwords, you need to do ~$\sqrt{N}$ work to cancel out all the bad ones. That's better than classical, but very far from "one attempt".
Only if you did operations that canceled out the wrong guesses first.

There are processes and algorithms that can solve problems in one step if the process is controlled well enough to remain in its lowest energy state. Any disturbance will upset the process and give a wrong answer at a higher energy state, but that is a problem with the implementation, not an essential part of the theory. With those processes, the number of incorrect answers is related to the probability of energy disturbances and the number of qubit values required for the solution.

 

[Strilanc]

There are processes and algorithms that can solve problems in one step if the process is controlled well enough to remain in its lowest energy state. Any disturbance will upset the process and give a wrong answer at a higher energy state, but that is a problem with the implementation, not an essential part of the theory. With those processes, the number of incorrect answers is related to the probability of energy disturbances and the number of qubit values required for the solution.

You're talking about adiabatic quantum annealing, right?

You can't just move the system from the trivial state to the problem state. You have to do it slowly. For larger or more complicated problems, you have to go slower and slower. Unstructured search is known to have a lower bound of $\Omega(\sqrt{N})$ time in BQP, and that applies even if you conceptualize the process as a single step.

You can call it "one step" if you like, but that "step" is going to take more and more time to guess passwords as they get larger. When you tell someone it can be done in one step, there's a real danger that they'll wrongly assume you mean it can be done in constant time (instead of taking at least twice as long for passwords four times as large), so be wary of that.

 

[Strilanc]

Thanks for all of the replies.


I checked out Shor's Algorithm and this wiki article actually talks about it in terms of using it to crack public key encryption - it's an interesting read.


I think this pretty much answers my question. I guess my real question was "would the act of cracking a password using qubits in superposition cause their values / states to become determined, without direct observation?" So if the password was cracked successfully, would that mean that observing the qubit states at the point of successfully guessing the password would reveal the actual password? I gather from your answers that this is not the case, and that observation would corrupt the result showing only a random possibility of the password and not the actual password itself, even though at some point, the qubits must have been in a state to reflect the correct password in order to crack it.

It sounds like you're on the right track.

I will caution that the way you're phrasing things makes me think you're not familiar with programming. You're talking like the computer will notice what you're trying to do and help you out, but really all it does is run the operations you give to it without understanding or purpose. If you want a computer to do something, you have to find a sequence of operations that does that thing. Finding and understanding an algorithm for putting qubits into a state where the correct password gets almost all the amplitude is the conceptually hard part, and the computer is not going to do it for you.

 

[FactChecker]

You're talking about adiabatic quantum annealing, right?

Yes.

You can't just move the system from the trivial state to the problem state. You have to do it slowly. For larger or more complicated problems, you have to go slower and slower. Unstructured search is known to have a lower bound of $\Omega(\sqrt{N})$ time in BQP, and that applies even if you conceptualize the process as a single step.

You can call it "one step" if you like, but that "step" is going to take more and more time to guess passwords as they get larger.

Yes, but it is one step. I think that is important to understanding the process.

When you tell someone it can be done in one step, there's a real danger that they'll wrongly assume you mean it can be done in constant time (instead of taking at least twice as long for passwords four times as large), so be wary of that.

Agree. But the concepts of quantum entanglement and the potential of quantum computers is clearer if a person understands that it can solve large problems in one step. There are still great problems to solve before they are practical, but the potential is also great.

 

[Strilanc]

the concepts of quantum entanglement and the potential of quantum computers is clearer if a person understands that it can solve large problems in one step. There are still great problems to solve before they are practical, but the potential is also great.

I seriously disagree with this. If you're letting steps take arbitrarily large amounts of time, doing things in one step is no longer impressive and is not indicative of potential. It's *interesting* that the process is so straightforward, but the *potential* is all about how long it takes.

As a counter-example, consider the Quantum Fourier Transform. It does not finish in one step. It takes $O(n^2)$ operations in the gate model, where n is the number of qubits. More, if you have to build the finely tuned phase gates out of a restricted gate set. But when people worry about cryptosystems being broken they're *not* thinking about adiabatic quantum computing (well... http://www.am.qub.ac.uk/ctamop/phd/ProjectMcCann.pdf [Broken], anyways): they're worried about the QFT. The known potential of the gate model is much higher, despite it being broken into multiple "steps".

 

[FactChecker]

I seriously disagree with this. If you're letting steps take arbitrarily large amounts of time, doing things in one step is no longer impressive and is not indicative of potential. It's *interesting* that the process is so straightforward, but the *potential* is all about how long it takes.

"Arbitrarily long" would indeed be a problem. But the question of how long a single step takes can be completely different from the question of how much total time an O(n³) process of n steps takes. Understanding the potential of the two processes is only clear if that difference is understood. So it is important for anyone studying quantum computers to know that they can do more in one step than traditional computers can.