Quantum Algorithms

Sunday, November 30, 2003

**Peter Shor Interview**

I interviewed Dr Peter Shor about the current state of quantum algorithms. When asked about recent quantum algorithm advances, he replied:

*"Grover's algorithm has been generalized to an amplitude amplification algorithm (due to Brassard, Hoyer, Mosca and Tapp), which means that if you have a quantum algorithm which has a small chance of solving a problem (and you can tell when it's solved it), you can amplify this probability more efficiently than is possible classically (by a square root factor)."*

Read the whole interview here.

Friday, November 28, 2003

**Fast Quantum Search Engine for Multiple Matches**

New paper builds on Grover's algorithm and makes it practical in the case of multiple matches.

Thursday, November 20, 2003

**Bose Condensate Advances**

*"[Researchers] started with a gas of fermionic lithium-6 atoms in an optical trap and cooled them in a magnetic field to produce a condensate containing over 100 000 lithium molecules...The condensate lasted for more than 20 seconds."*From a PhysicsWeb story.

**Quantum cnot Gate Created...This Time With Photons**

For the second time in three weeks, Nature has a paper on creation of a cnot gate. From the abstract:

*"We produce all four entangled Bell states as a function of only the input qubits' logical values, for a single operating condition of the gate. The gate is probabilistic (the qubits are destroyed upon failure), but with the addition of linear optical quantum non-demolition measurements, it is equivalent to the CNOT gate required for scalable all-optical quantum computation."*

Wednesday, November 19, 2003

**Electron Spins Can Control Nuclear Spins**

*"nuclear spins have a weaker interaction with the surrounding environment than electron spins. While harder to flip, once oriented, nuclear spins preserve their state longer than do electrons."*From Physical Review Letters, via physics.about.com.

Tuesday, November 18, 2003

**Mysterious Particle Discovered**

*"The discovery either suggests that a new family of molecule-like sub-atomic particles exists, or that theorists must substantially re-think their theory of the masses of sub-atomic particles,"*from New Scientist.

**November Virtual Journal of Quantum Information out**

Two algorithm articles: "Scaling issues in ensemble implementations of the Deutsch-Jozsa algorithm" and "Communication Cost of Simulating Bell Correlations." See it here.

Wednesday, November 12, 2003

**Quantum mp3's**

Story on quantum audio compression:

*"Our approach to quantum audio signals has close similarities with the MP3 compression used for sound treatment in usual classical computers."*The researchers belong to this Center, and here is their paper, which states:

*"A quantum computer with 50 qubits may store an amount of information exceeding all modern supercomputer capacities (1000 years of sound)."*

**Superfast QC Simulator**

5 week old story,

*"Fujishima and his team invented a tool called a "quantum index processor" (QIP) to increase the speed at which classical computers run quantum algorithms, such as Shor's."*

Linked within that article is another that casts serious doubt on QC's every being used for "general-purpose" computing.

**Physics Blogs**

UIUC Physics Blog

Sort of a blog, at about.com

Science blog, not much physics though.

Stupid Movie Physics

**Web Site Up**

There's nothing there yet, but www.qualgorithm.com is up and running. It will hopefully become a resource for quantum algorithm information. I am creating an algorithm directory, and taking suggestions on what else would be useful for the community.

Monday, November 10, 2003

**QM Critics: Put up or Shut up**

There's a new paper in the e-Print archive, which attempts to

*"refine vague ideas about a breakdown of quantum mechanics into specific hypotheses that might be experimentally testable in the near future. "*

**Quantum Chaos**

From the Institute for Quantum Computing: an unpublished pdf tutorial on Quantum Chaos, or technically speaking, the

*lack*of quantum chaos.

**Quantum Cellular Automata**

Only 11 QCA articles in 7 years of the e-Print archive, but here are the two most recent:

July '03:Quantum Cellular Automata from Lattice Field Theories

June '03: Entanglement Dynamics in 1D Quantum Cellular Automata

**Quantum cnot Gate Implemented**

From about a week ago, here is a main stream news story, but the original story appears in Nature, which unfortunately is not free.

Seems like a pretty big milestone, would be nice to know the specifics. From the abstract:

*"In our experiment, two 40Ca+ ions are held in a linear Paul trap and are individually addressed using focused laser beams; the qubits are represented by superpositions of two long-lived electronic states."*

Just how long is "long-lived"?

Sunday, November 09, 2003

**Acceleration Disrupts Quantum Teleportation**

Here is a summary of the discovery.

*"Drawing from the example above, a new analysis has shown that quantum teleportation would malfunction if the receiver of the second particle is accelerating relative to the third particle."*Will this constrain the design of quantum computers at all?

Here's some background info, courtesy of IBM.

**Beal's Conjecture**

Peter Norvig has some classical algorithms to find counter-examples to "Beal's Conjecture." At a first glance it seems to be a well suited problem for a QC, since it is a bit like factoring big integers. When I get a chance, I'll try to come up with a qualgorithm and post it here.

**Unbreakable Quantum Encryption on Sale Now**

Here is the first commercially available quantum encryption system. Seems a bit premature, maybe? I wonder who will buy it.

**Related Blogs**

This seems to be the only blog focused specifically on quantum algorithms, but there's a few others on quantum computing:

Quantum Bits, averages maybe one post a month.

Quantum News, mostly job postings, 5-10 posts per month.

I'll link to them if anything particulary interesting passes through.

**Welcome to qualgorithms (quantum algorithms).**I'm planning on focusing on quantum algorithms, but topics will probably range through many aspects of quantum computing and computer science.

By quantum algorithm, I am referring to algorithms designed to run on quantum computers, assuming they come into existence eventually.

If there's anything you'd like to see discussed on this blog, or have comments of any kind, let me know: jjkleid [ at ] yahoo . com