The Square Root of Not | Hacker News Reader

The Square Root of Not

americanscientist.org

108 pointsColinWright25 comments

If you enjoyed this article, you may enjoy my series of short videos on "Quantum Computing for the Determined", which go deeper into the subject than this article, while remaining accessible to anyone with some basic background in linear algebra. The videos provide an intro to quantum mechanics, and cover the basic quantum computing model, as well as quantum teleportation and superdense coding:

http://michaelnielsen.org/blog/quantum-computing-for-the-det...

(Apologies for the self-plug, but this particular article seems like a good prelude to my course.)

Thanks!

It would be pretty cool if you could make the links drop down and display the video on your site so it could be easier to go back and forth between videos at one time.

ex: http://imgur.com/0CyckZQ

A quick note: in the first or second lecture when you multiply a state vector by a constant and use number 2 as an example, it's a bit confusing: it does not preserve the unitarity. A better example would be a complex number exp(i\phi).

Here's a much simpler and more intuitive (IMHO) way of understanding this: imagine you're encoding bits as polarization. Vertically polarized is 1 and horizontally polarized is 0. Rotating the polarization by 90 degrees is then a logical NOT operator. Rotating by 45 degree is then the "square root of not" because if you do it twice you get a NOT operator. (This exactly analogous to how you can define the square root of -1 by thinking of multiplying by -1 as a rotation through 180 degrees on a number line. The square root of -1 then becomes a rotation by 90 degrees.)

BTW, you can actually do this experiment yourself at home using very inexpensive materials: a laser pointer, polarized sunglasses, and a few dollars worth of "quarter wave plate" material that is easily found on the internet.

I do hope your example is correct, I now think I understand the concept!!!

Is it correct to say that the x-axis in your example is the imaginary number line and the y-axis is the real number line? What about other degrees of rotation?

Your question is a little ambiguous, but I think you'll find the answer here:

http://betterexplained.com/articles/a-visual-intuitive-guide...

Note that the two examples (polarization versus imaginary numbers) differ in one important respect: in the polarization example, negation is rotation by 90 degrees, e.g. from vertical to horizontal. In the imaginary numbers example, negation is rotation by 180 degrees (e.g. from positive X to negative X -- see the link above).

Usually we say x-axis is real number and y-axis is imaginary. But you get the idea. http://en.wikipedia.org/wiki/Complex_plane

This is a fascinating article but the formatting is atrocious, mostly with the closing >-like character in the |0> notation, which seems to be rendered as an image and then repositioned in an inappropriate way so that it leaves its context.

People with Chrome developer tools or Firebug will find it marginally improved by disabling the stylesheet rules for the .imageRight class (and maybe setting the p.font-size to 16 or so to boot, so the > isn't grossly oversized relative to the text)

Much better: http://bit-player.org/wp-content/extras/bph-publications/AmS...

Non-print friendly version, possibly with better formatting, but in five pages:

http://www.americanscientist.org/issues/pub/the-square-root-...

"In all known classical factoring algorithms, the amount of time needed to find the prime factors of a number grows as an exponential function of the size of the number, making the algorithms impractical for very large numbers."

General number field sieve is sub-exponential. Factoring is interesting because it is not NP-complete, but not known to be in P either. It is my understanding that NP-complete problems remain so in the quantum world.

Saying "NP-complete problems remain so in the quantum world" is a bit imprecise because NP-complete is simply defined as a set of problems which can be solved by classical nondeterministic computers. Of course it "remains so" in the quantum world; it's a mathematical definition, it remains so in any world.

What's very interesting is that Scott Aaronson proved that normal quantum computers could have solved NP problems (in fact, something stronger: BQP = PP) if quantum mechanics allowed nonunitary linear operations or was based on the norm

    norm = lambda vec: sum(abs(component) ** p for component in vec)

for p > 2 (quantum mechanics is based on p = 2, classical probability is based on p = 1). So if it were any larger, the quantum computer could do brute force with ease.

Right now it's not known whether BQP contains NP-complete or not; it might very well contain both problems in NP and problems not in NP while deftly evading NP-complete.

It is known that PostBQP = PP and therefore contains NP-complete. PostBQP is the set of quantum algorithms which are allowed to destroy the universe when they fail, under the anthropic principle reasoning that "humans will only live on in universes where the computation succeeds."

>>Since quantum mechanics appears to be a true theory of nature, it governs all physical systems...

That's quite naïve. I'd say quantum mechanics seems to be the best description we currently have for the laws of physics on a micro level.

All macro systems are consistent with blown up versions of quantum systems. Chemistry, then biology. Whats left?

When you're studying the philosophy of science, it's more accurate to say that our theories and equations describe reality rather than to say that they govern reality.

That's not necessarily arguing that a more fundamental theory might exists that could overturn socially unpopular theories higher up the chain. Sure, that happens in certain kind of debates rather often, but I'm not sure that's what's happening here.

Yes you correct of course. I thought the point nsns was making that quantum was holding on the micro scale, and not-above that. I didn't get that he was commenting on the difference between _govern_ and _describe_.

What, exactly, do you think they meant by the word 'appears t be'?

It's not naivety -- it's just not interesting to get sidetracked by philosophy every time you talk about a particular scientific theory. For the sake of brevity, all that stuff can be shoved to the side in this context.

Also note that the probabilities in each column and each row sum to 1, indicating that every possible combination of input and output has been accounted for.

Perhaps a quantum probabilistic NOT gate requires the columns to add up to 1, but it's certainly not a general requirement of any physical device that imperfectly implements a NOT gate.

Consider the following probability matrix:

      0    1
 0  0.1  0.9
 1  0.8  0.2

For any input (say, 0, in the top row), the output will be interpreted as either a 0 or 1, so the row sum must be 1.

However, there's nothing forcing the probability of 0 as an output in one row to depend on its probability in another row. One could implement the gate above in software, with no problems, and a hardware equivalent could certainly be produced.

[Edit-- fixed row probabilities in second row.]

I don't think you logic works. Your table says that if a 0 is in-putted then there is a .1 chance of getting a 0 and a .8 chance of getting a 1. That leaves a probability of .1 or something else happening, but it you add a third state it is no longer a not gate.

In other words, a not gate, regardless of the implementation must have it's columns sum to 1. This is a fundamental principle of probability and the definition of a not gate.

Your comment supposes that the column headers are the inputs. However, I used the definition from the article-- "Here the numbers along the left edge, labeling the rows of the matrix, are the inputs to the gate..."

So, taking the columns as the outputs, my point is that adding down the columns corresponds to no particular causal relationship in the physics of the gate.

Your comment did, however, make me realize that I hadn't modified the row probabilities for the second row to sum to one (11-month old under foot). So thanks for that.

In order to satisfy the basic matrix transformation properties

    dot = lambda M, v: vector(sum(M[i][j] * v[j] for j in range(len(v))
                                                 for i in range(len(M)))

as well as the basic left-to-right, top-to-bottom ordering "M00 M01\nM10 M11", the columns, not the rows, would add up to one. Such a matrix is called a "stochastic matrix" or "Markov matrix".

You are correct that the rows do not have to add up to one, just the columns do, for stochastic matrices.

Quantum gates do demand one special restriction; they must be unitary. A unitary matrix satisfies:

    transpose(U) = inverse(U)

This is not as simple as "rows sum to 1" or anything of the sort; as the article says, you can create several examples of 2x2 matrices which have sqrt(1/2) factors in all components.

No, a matrix is unitary if

  hermitian(U) = inverse(U)

Ugh. Promotes (or, at least, inadequately rebukes) the bad and common misunderstanding that quantum computing provides a _general_ exponential speedup. It does not. QC is only even theorized to provide a exponential speedup for a few things, for other things QC cannot provide a better than sqrt() speedup (and this is tightly bounded for general non-linear search).

I strongly recommend Scott Aaronson's thesis http://www.scottaaronson.com/thesis.pdf for anyone who doesn't want to be made QC-stupid by articles like this. The beginning is interesting and generally accessible as it goes into the details you need to be comfortable with linear algebra to follow along.

Did you read the penultimate paragraph? I suspect you didn't.

Reply on news.ycombinator.com