Algorithms! I need algorithms!

Often, I am asked something along the lines of: “Why Quantum Computing? What does it offer that is better than regular computers?” To be perfectly honest, I don’t know. For me, I just think that it is really cool to be able to control and engineer the quantum states of individual ions. And working with lasers. But as an engineer, I feel like I need to offer some sort of practical and useful application of Quantum Computing (or Quantum State Engineering).

Are there certain problems that are nearly impossible on a regular computer, but are a snap on a quantum computer? This implies some sort of complexity of the problem. But since I’m no computer scientist, I don’t know anything about P vs. NP & complexity classes. But I do know this: a quantum computer won’t be any faster than a regular computer, unless it is running a quantum algorithm (an algorithm that exploits some aspect of quantum mechanics). Because, otherwise, it could be done on a regular classical computer. And to be honest, with all the infrastructure we need (electronics, lasers, vacuum chambers, etc.), it’d be faster to just use a regular computer.

So, what quantum algorithms are there? Again, I’m no computer scientist, and only know of three: the Deutsch-Jozsa algorithm, Grover’s search algorithm, and Shor’s factoring algorithm. Wikipedia gives a good description of the Deutsch-Jozsa algorithm:

In the Deutsch-Jozsa problem, we are given a black box quantum computer that implements a single function f(x1, x2, …, xn) that takes n binary bits x1, x2, …, xn and returns the binary value f(x1, x2, …, xn). We know that the function is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half); the task then is to determine which it is (constant or balanced) by applying inputs to the black box and observing its output.

Grover’s search Algorithm searches an unsorted database. Suppose you find just a phone number in your pocket, and you can’t remember if it is the number of the hot girl you met last night, or the the ugly one. To save face, you decide not to call to find out. Rather, you want to look them up in the phone book. Unfortunately, the phone book is ordered by name, not number. So how would you search? If you had a quantum computer, Grover’s algorithm could help you.

Shor’s factoring algorithm is just that. It factors a number into its primes. Why is this interesting? The difficulty of factoring has it’s uses in encryption. An example of the use of this is in RSA Encryption. Of course, this has spy stuff written all over it—breaking codes, secret messages. It also offers the best speed-up, and uses the Quantum Fourier Transform. And I’m quite partial to any sort of Fourier Transform.

So, obviously, I’ll mention Shor’s algorithm.

Perhaps it is time that I learn some Computer Science & some other quantum algorithms. If you’re interested in how Shor’s factoring algorithms works, I highly recommend this post by Scott Aaronson. Incedentally, he’s got another post about the recent breakthrough in quantum algorithms: the NAND tree.

I see the light at the end of the tunnel

And there’s a needle there:

Under the radar

D-Wave supposedly has unveiled it’s 16-qubit Quantum Computer today, according to their blog. What does this all mean? Well, if it truly is a Quantum Computer, then good for them. I’m quite skeptical, mainly because this thing would have gone completely under our radar. Their method is using superconducting Quantum Interference Devices (aka “SQUIDs”), which are large solid-state devices. One reason ions hold so much promis in this field is that their qubits can have long coherence times (i.e. it keeps a |0> or |1> longer), because we choose atomic states that do not interact strongly with the environment. Solid-state implementations of Quantum Computing generally have short coherence times. So, given that I’ve not seen many papers demonstrating rapid progress in solid-state quantum computation, I think I’m right in being rather skeptical about this announcement. My advisor Chris is skeptical too.

I don’t know anything about adiabatic quantum computing, which is what this system supposedly is. From what I can gather, it looks like they’re just simulating (solving?) a 2-D ising model in a magnetic field. Correct me if I’m wrong, but isn’t there an analytic solution?

I have this sneaky suspicion that what we have is a 2-D array of qubits—a qubit consisting of a large domain of a single state—interacting via tunneling from one domain to another. I don’t think that we have actual entanglement, nor coherence. This tunneling interaction can be written as a 2-D Ising model. Hence, all I can see this ‘quantum computer’ doing is simulating the 2-D ising model.

Note: The Quantum Pontiff, Dave Bacon, had a roundup of this. We’ll see what goes on with this. If this is bunk, hopefully it won’t be like Cold Fusion, which discredits the whole field.

It’s official: I’m an EE

A month ago, I inherited a stereo receiver/amplifier from Karyna. She got it from Craigslist, and it was starting to ‘go bad’—some crackling, and other non-niceties in the sound. She got a new amplifier from her parents, and decided to give me this one. As for what I’d do with it, I’m not too sure.

So I ordered a service manual from stereomanuals.com. Despite their horrendous website and slightly cryptic e-mails, I managed to get the right service manual. And it is beautiful. They do a bang-up job on reproducing the manual, and they are rather prompt in shipping. So, I highly recommend them—in spite of their horrible website.

Now, I’m looking at the circuit layout, the block diagram, and everything; thinking to myself: damn, that’s complicated, but I could make that! It’s obvious now that I’m ‘in love’ with circuits. I have a specific task that’s interesting to me, and I am thinking about how to build it.

Anyways, I need to spend some time with my receiver/amplifier and figure out what’s wrong. By looking at the block diagram, I’ve realized that I can cut out 90% of the circuit, as it is obvious it has nothing to do with what’s wrong.

Photonic qubits: Schrödinger six-pack

I took a look today at Nature Physics, a relatively new physics journal from the makers of Nature. The latest issue has an article about the entanglement of six photons in both a ‘GHZ’ state and a ‘cluster’ state.

The Greenberger–Horne–Zeilinger (GHZ) state is an entangled state in which (for this experiment) all six photons are in a superposition of all being horizontally polarized and all vertically polarized. In computer lingo, that is all zero (000000) and all one (111111) at the same time. This state is entangled, as the state of each individual photon is correllated with the others. The six-qubit ‘Cluster state’ is quite a different beast. Basically, it is another entangled state of the six photon system. The entanglement properties of these states are quite different, and can be represented as points on a graph. Each qubit is a point/node, and the entanglement is like a line connecting the points.

Six-Qubit GHZ state:

Six Qubit Cluster State:

Of course, when I think of a Schrödinger six-pack, I think of Bob the Angry Flower.