Quantum Computing: Large Chance of Getting Desired Output?

[Dragonfall]

Suppose you were given \sum_{i=0}^{2^n}\left| i\right>\left| f(i)\right>, is there something you can do so that when you measure in the computational basis, you have a large chance of getting a particular desired \left| i\right>\left| f(i)\right>?

 

[Dragonfall]

Is LaTeX not working?

 

[pmb_phy]

That is rather odd. Let me give it a whirl. It works when I do a Preview Post I got the correct result. Let me try posting it

\sum_{i=0}^{2^n}\left| i\right>\left| f(i)\right>

\left| i\right>\left| f(i)\right>

Seems to work for me. Pretty strange indeed!

What do you mean by computational basis? What is |f(i)>? Is it an eigenket? I've never seen that notation before. Usually its written (if you are you referring to what I think you are) as |i>.

Pete

 

[Dragonfall]

I forgot to mention. f is a function from \{0,1\}^n to itself. Suppose I am given the superposition <br /> \sum_{i=0}^{2^n}\left| i\right&gt;\left| f(i)\right&gt;<br />. I want to measure a particular \left| i\right&gt;\left| f(i)\right&gt; with 1 or very high probability. Is it possible to do that by applying some operator to <br /> \sum_{i=0}^{2^n}\left| i\right&gt;\left| f(i)\right&gt;<br />?

 

[pmb_phy]

I forgot to mention. f is a function from \{0,1\}^n to itself.

I'm sorry but I don't understand that notation. Why are you raising a set to the power n??
What does that notation mean? Also you didn't answer my question, i.e. what is |f(i)>? Note that I'm not asking what f(i) is. Does the ket |f(i)> represent an arbitrary quantum state? What do the values f(i) correspond to? Are they eigenvalues of some operator for which the eigenkets are |f(i)>? You do realize that |i> |f(i)> is the tensor product of two state vectors right? The ket |i> I assume is a basis ket for some Hilbert space.

Suppose I am given the superposition

\sum_{i=0}^{2^n}\left| i\right&gt;\left| f(i)\right&gt;

I recommend placing a carrige return before and after the tex label so that the equation doesn't appear inline. Its confusing when it does in that it looks really ugly.

I want to measure a particular \left| i\right&gt;\left| f(i)\right&gt; with 1 or very high probability.

For this to be the case the coeffient must be close to 1. However you don't have any coefficients in that expression. Please check your notation and make sure its what you meant to post. Thanks.

Pete

 

[Dragonfall]

{0,1}^n is the set of all n-length bit-strings. A general state of n qubits is described by \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n}\alpha_i\left| i\right&gt;, in the computational basis. Since f is just a permutation of the strings, \left| f(i)\right&gt; is just one ket of the said basis.

 

[pmb_phy]

{0,1}^n is the set of all n-length bit-strings. A general state of n qubits is described by \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n}\alpha_i\left| i\right&gt;, in the computational basis. Since f is just a permutation of the strings, \left| f(i)\right&gt; is just one ket of the said basis.

Sorry but I can't help you. All this qubits and computational basis stuff is something I know nothing about. Good luck!

Pete

 

[Phrak]

wait, pmb, come back...

Apparently this deals with spin 1/2 particles. The computational basis means,

|0> = |spin up>
|1> = |spin down>

A ket, like this |1101> = |13> (in hexidecimal), is shorthand for |up> |up> |down> |up>.

Dragonfly. I don't get it either. Is f(i) a digit, n bits long?

 

[Dragonfall]

Yes. Say f(3)=4, then somewhere in the superposition is the term \left| 3\right&gt;\left| 4\right&gt;. Basically you'd get a superposition of all the input and values of f from 0 to 2^n.

Now I want to somehow extract a PARTICULAR piece of information from that superposition, say f(3). Is this possible? I mean if I just measure the qubits without doing anything to them first then I'd just get a random term, and hence a random value of f.

Now unfortunately I don't actually know any physical interpretation of all this stuff, so I can't refer to it as a "spin-1/2" particle.

 

[Phrak]

Yes. Say f(3)=4, then somewhere in the superposition is the term \left| 3\right&gt;\left| 4\right&gt;. Basically you'd get a superposition of all the input and values of f from 0 to 2^n.

Yeah, you could do this I think, but I don't know why. It would throw away the parallelism that you'd be gaining in doing it in the first place.

Let me clean up some of your notation first, if I may. Normally you'd have two registers, x and y. The x register (call it 8 bits long) would be prepared as a superposition of all binary values from 0 to 2^8-1=255. All the binary numbers from 0 to 255 would be equally represented in x. Register y is initialized to 8 bits of binary zero, |00000000>. Usually the word length (how many bits) is implied and just written as y=|0>.

\left| x \right&gt; = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\left| i \right&gt;

\left| y \right&gt; = \left| 0 \right&gt;

Note that I fixed the index limit to 2n-1 so that there are 256 numbers respresented, in total.

The idea is to take the register pair \left| x \right&gt;\left| 0 \right&gt; to \left| x \right&gt;\left| f(x) \right&gt; by applying some quantum gate that will mix |x> and |0> together to get y=f(x) and still leave you |x> so that the operation is reversible. (How, or if this manages to conserve information without mixing with the environment, is the question I'd like answered).

After the gate operation is preformed, y = f(x). The register pair become:

\left| x \right&gt; \left| y \right&gt; = \left| x \right&gt; \left| f(x) \right&gt;

Now I want to somehow extract a PARTICULAR piece of information from that superposition, say f(3). Is this possible? I mean if I just measure the qubits without doing anything to them first then I'd just get a random term, and hence a random value of f.

We're both learning this material :: so I had to think a bit to come up with a "method". It would be do-able, just as much as any of this is do-able, given the current technology. Begin with the pair |3> |y> by thowing away the |x> superposition and preparing x = |3> without effecting |y>. Apply a gate operation to obtain |3> |f(3)>. This looks a lot like an inverse gate where |x> has been prepared in a singular state.

Eventually you should need something like this to extract classical information, I think. Maybe that's what you're asking. If so, I've been curious too. If we're lucky someone like Hirkyl will step in and clear up some uncertainty.

Now unfortunately I don't actually know any physical interpretation of all this stuff, so I can't refer to it as a "spin-1/2" particle.

No worries.

 

[pmb_phy]

Yes. Say f(3)=4, then somewhere in the superposition is the term \left| 3\right&gt;\left| 4\right&gt;. Basically you'd get a superposition of all the input and values of f from 0 to 2^n.

Now I want to somehow extract a PARTICULAR piece of information from that superposition, say f(3). Is this possible? I mean if I just measure the qubits without doing anything to them first then I'd just get a random term, and hence a random value of f.

Now unfortunately I don't actually know any physical interpretation of all this stuff, so I can't refer to it as a "spin-1/2" particle.

This can't be done in the form you wrote the equation since it isn't normalized. I.e. since there are no coefficients in front of the kets this doesn't represent a physical state. If you were to rewrite this as you did above when you used \alpha_i and applied the ket <4|<3| then the only surviving term would be \alpha_3. The square of this value is the probability of the system being measured to be in the |3>|4>.

Pete

 

[Dragonfall]

Eventually you should need something like this to extract classical information, I think. Maybe that's what you're asking. If so, I've been curious too. If we're lucky someone like Hirkyl will step in and clear up some uncertainty.

I don't think this is possible. Suppose Alice and Bob shared the entangled EPR pair \frac{\left| 00\right&gt; +\left| 11\right&gt;}{\sqrt{2}}. If Alice were able to CHOOSE which state she can measure, then she'd be able to communicate with Bob faster than light.

 

[pmb_phy]

I don't think this is possible. Suppose Alice and Bob shared the entangled EPR pair \frac{\left| 00\right&gt; +\left| 11\right&gt;}{\sqrt{2}}. If Alice were able to CHOOSE which state she can measure, then she'd be able to communicate with Bob faster than light.

In the physics literature people have presented arguments that faster than light communication is possible with entangled states. Would you like references?

Pete

 

[Dragonfall]

Really? I'd sure love some references. How does that reconcile with relativity?

 

[Dragonfall]

I'm just going over what I'm asking again since I wasn't clear before:

Bob takes n+1 qubits, all initiated at |0> (the first n being input registers and the last is an output register), and sends the first n through an n-fold Hadamard gate. This results in the superposition

\mid\Psi\rangle =\frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\mid i\rangle\mid 0\rangle

Bob then chooses some function f bounded above by 2^n-1, then finds a unitary operator which implements the function:

U_f\mid x\rangle\mid 0\rangle =\mid x\rangle\mid f(x)\rangle

Bob then sends U_f\mid\Psi\rangle to Alice. Alice now has n+1 qubits with loads of information about the function f. Alice would like to learn a PARTICULAR VALUE of f (not a random one). Can she do it?

 

[pmb_phy]

Really? I'd sure love some references.

Here are the ones that I picked up on my journey's to a research library

Can EPR-correlations be used for the transmission of superluminal signals? P. Mittelstaedt, Ann. Phys (Leipzig) 7 (1998), 7-8, 710-715

Abstract. In a compound quantum system with EPR-like correlations a measurement of one subsystem induces instantaneously changes of the subsystem, irrespective of the relative distance of the two subsystems. We consider several arguments which were put forward in recent years in order to show that these nonlocal effects cannot be used for superluminal communication. It turns out that arguments mentioned above are merely plausible but not really stringent and convincing. This means that the question in the title of this paper is still open.

Superluminal signal velocity, G. Nimtz, Ann. Phys (Leipzig) 7 (1988), 7-8, 618-624

Abstract. It recently has been demonstrated that signals conveyed by evanescent modes can travel faster than light. In this report some special features of signals are frequency band limited. Evanescent modes are characterized by extraordinary properties: Their energy is negative, they are not directly measurable, and he evanescent region is not causal since the modes traverse this region instantaneously. The study demonstrates the necessity of quantum mechanics in order to understand the superluminal velocity of classical evanescent modes.

Bell's theorem: Does quantum mechanics contradict relativity?, L.E. Ballentine, Am. J. Phys. 55(8), August 1987

Abstract. Special relativity demands a locality principle (no instantaneous action at a distance); locality implies Bell's theorem; quantum mechanics violates Bell's inequality, therefore, quantum mechanics contradicts relativity! Or so it would seem. It is shown, however, that the locality principle needed for Bell's theorem is stronger than the simple locality that is needed to satisfy the demands of relativity and that quantum mechanics satisfies later. The stronger locality principle id equivalent to the conjugation of simple locality and predictive completeness, and it is the latter principle that fails. The notion of predictive completeness is weaker than, and is implied by, the completeness criterion of Einstein, Podolsky, and Rosen. But the quantum mechanical state description is not only incomplete but incompletable, for any local complete state description would satisfy Bell's inequality and disagree with experiment.

Faster than Light?, Raymond Y. Chiao, Paul G. Kwiat and Aephraim M. Steinberg, Scientific American, August 1993

Experiments in quantum optics show that two distant events can influence each other faster than any signal could have traveled between them.

re - How does that reconcile with relativity? - I can send you any and all of the papers in e-mail to you if you'd like? I haven't found time to study this phenomena yet. Actually I'm reviewing quantum mechanics again and plan on studying this in detail when I get to EPR and Bell's theorem. I'll try to look the articles over in the near future since this is a subject of great interest to me.

Best wishes

Pete

 

[Phrak]

I don't think this is possible. Suppose Alice and Bob shared the entangled EPR pair \frac{\left| 00\right&gt; +\left| 11\right&gt;}{\sqrt{2}}. If Alice were able to CHOOSE which state she can measure, then she'd be able to communicate with Bob faster than light.

So *that's* what this is all about. Too cool. Unfortunately, I'm not in a position to understand it well enough. But to extract y(x) for a given x, Alice needs place x in a definite state--destroy the superposition of x. Bob doesn't know what Alice did to x does he?

There is one other point, though. You do realize that your f(x) is one bit wide as you've stated it. n bits for |x>, leaving one for |y>.

 

[Dragonfall]

Can EPR-correlations be used for the transmission of superluminal signals? P. Mittelstaedt, Ann. Phys (Leipzig) 7 (1998), 7-8, 710-715

Superluminal signal velocity, G. Nimtz, Ann. Phys (Leipzig) 7 (1988), 7-8, 618-624

Bell's theorem: Does quantum mechanics contradict relativity?, L.E. Ballentine, Am. J. Phys. 55(8), August 1987

Faster than Light?, Raymond Y. Chiao, Paul G. Kwiat and Aephraim M. Steinberg, Scientific American, August 1993

Is it possible to find these online?

 

[Cthugha]

Well, the Nimtz paper can be found on Arxiv http://xxx.lanl.gov/abs/physics/9812053".

However none of these papers is really worth your time as they are either papers, which explain small loopholes, which were still left at the time these papers were written, papers, which explixitly say, that the velocity exceeding c is not a signal velocity like the Chiao paper or papers, which are on the brink to crackpottery, because they also discuss a velocity exceeding c, which is no signal speed, but do not explicitly tell that like in the Nimtz paper.

The Nimtz stuff has also been discussed several dozen times in this forum. I am a bit amazed, that it is still quoted as a reference from time to time.

 

[pmb_phy]

Is it possible to find these online?

Not that I know of. I scanned all the papers that I have in my filing cabinet and placed them into PDF files. If you don't want me to e-mail them to you then I could try to upload them onto one of my web sites. I could then post the URL to the papers and you could download them yourself. It'd be easier for me to e-mail them to you though.

Pete

 

[pmb_phy]

I just uploaded the first three of the articles to one of my web sites. I don't have enough web space to upload the last one. The URLs for the first three are

http://www.geocities.com/pmb_phy/Ballentine_1987.pdf
http://www.geocities.com/pmb_phy/Mittelstaedt_1998.pdf
http://www.geocities.com/pmb_phy/Nimtz_1998.pdf

Let me know when you've downloaded them so I can delete then and upload the last one for you.

Best wishes

Pete

 

[Dragonfall]

Got them, thanks.

 

[pmb_phy]

Got them, thanks.

You're welcome. Unfortunately I can't upload the Scientific American article because its too large. Yahoo only allows files of file size less than 5MB and the Scientific American article is 9 MB. Sorry.

Pete

 

[Phrak]

I can't say I'm very impressed by these abstracts, for the most part.

Can EPR-correlations be used for the transmission of superluminal signals? P. Mittelstaedt, Ann. Phys (Leipzig) 7 (1998), 7-8, 710-715

Abstract. In a compound quantum system with EPR-like correlations a measurement of one subsystem induces instantaneously changes of the [other] subsystem, irrespective of the relative distance of the two subsystems.

This is presumtive in at least two ways. The best you can say, without additional interpretation, is that the measurements upon the two subsystems are statistically correlated according to strict rules. The part about one measurement inducing an instantaneous change in the other presumes some additional structure upon quantum mechanics. Secondly, "instantaneous" is relativistically ambiguous. For two space-like separated events, without reference to inertial frame, or an additional theoretical framework, it is meaningless to distinguish one as cause and the other as effect.

 

[Phrak]

I'm just going over what I'm asking again since I wasn't clear before:

Bob takes n+1 qubits, all initiated at |0> (the first n being input registers and the last is an output register), and sends the first n through an n-fold Hadamard gate. This results in the superposition

\mid\Psi\rangle =\frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\mid i\rangle\mid 0\rangle

Bob then chooses some function f bounded above by 2^n-1, then finds a unitary operator which implements the function:

U_f\mid x\rangle\mid 0\rangle =\mid x\rangle\mid f(x)\rangle

Bob then sends U_f\mid\Psi\rangle to Alice. Alice now has n+1 qubits with loads of information about the function f. Alice would like to learn a PARTICULAR VALUE of f (not a random one). Can she do it?

Try as I may, Dragonfly, I can't figure out which part is the classical information that Bob might be sending to Alice.

 

[Dragonfall]

Bob is "sending" Alice 2^n values of f with only n qubits.

 

[Phrak]

Yes, you did already say as much.

Say for a moment that both Alice and Bob have a U_\hat{f}, the inverse gate, and each has \mid\Psi\rangle, where is the superluminal transmission of classical information?

 

[Dragonfall]

The superluminal transmission occurs, for example if we go back to the <br /> \frac{\left| 00\right&gt; +\left| 11\right&gt;}{\sqrt{2}}<br /> state, if Alice measures 0 (or 1), then Bob will also measure 0 (or 1), no matter how far apart they are. So if Alice can choose which one she measures, then she can choose what Bob measures, and this is instantaneous. Normally you wouldn't have this problem since Alice's outcome is random.

 

[Phrak]

You need to present a complete senario--a thought experiment. How the qbits are prepared. Who measures what. What is sent to Alice. What Bob measures. What Alice measures. It's what is measured that counts in transmission of information. It's not enough to have correlation to transmit a message. The measurement process provides classical bit information.