Category: Quantum Computing

Posted on

Original McEliece Cracked

Shor’s algorithm is an algorithm for quantum computers which allows for efficiently factoring of numbers. This in turn allows Shor’s algorithm to break the RSA public key cryptosystem. Further variations on Shor’s algorithm break a plethora of other public key cryptosystems, including those based on elliptic curves. The McEliece cryptosystem is one of the few public key cryptosystems where variations on Shor’s algorithm do not break the cryptosystem. Thus it has been suggested that the McEliece cryptosystem might be a suitable cryptosystem in the “post quantum world”, i.e. for a world where a quantum computer is built (and if your a commenter who wishes to simply post the quantum computers are like string theory, please…save your keystrokes.)
Continue reading “Original McEliece Cracked”

Posted on

Shorter Bruce Schneier: "Trust My Blind Faith in Cryptography"

Bruce Schneier has a commentary up at Wired about quantum cryptography. There are a lot of good points about the article, but it left me kind of scratching my head. As far as I can tell Bruce Schneier believes that you should not worry about any cryptographic system currently in use ever being broken. I didn’t think cryptographers were allowed to have so little paranoia.
Continue reading “Shorter Bruce Schneier: "Trust My Blind Faith in Cryptography"”

Posted on

Quantum Algorithms Zoo

Stephen Jordan, now a postdoc at Caltech, has produced a useful little guide to quantum algorithms: a zoo of quantum algorithms. Help squash the myth that all there is to quantum algorithms are the algorithms of Shor and Grover!

Posted on

War I Tell You

Self promotion for those around the University of Washington campus: I’m giving a talk in the physics department at UW. Mondays, October 20 at 4:00 P.M. Ronald Geballe Auditorium, Rm. A102 (cookies at 3:45):

Title: “Who Will Build a Quantum Computer: the Physicists or the Computer
Engineers?”
Abstract: Building a quantum computer large enough to perform a task beyond the capability of today’s classical computers (breaking a cryptographic code or simulating a complex quantum system) is a daunting task. On the fundamental side, this difficulty arises from the fact that quantum systems like to decohere, and that we cannot control a quantum system with perfect accuracy. On the technical side, the obstacles toward build a quantum computer arise from the severe engineering constraints imposed by manipulating individual quantum systems. The theoretical solution to the problems of decoherence and lack of control was worked out in the nineties and is known as the threshold theorem for fault-tolerant quantum computing. The great debate in quantum computing today is how the technical difficulties of building a quantum computer will be overcome. In this talk I will outline two very distinct camps on how this will be achieved: one centered very squarely on engineering and the other with roots in condensed matter physics. This is a battle for the soul of future quantum computers and will determine whether quantum computers are years, decades, or centuries away from being built.

Posted on

Dickian Physics Abstract

An entry into the “best abstract ever” subcompetition of the “best title ever” competition, arXiv:0809.3979:

Counterfactual Quantum Cryptography
Authors: Tae-Gon Noh
Abstract: The ‘quantum counterfactuality’ is one of the most striking counterintuitive effects predicted by quantum mechanics. This manuscript shows that the counterfactual effect is not merely an interesting academic theme, but that it can also provide practical benefits in everyday life. Based on the quantum counterfactual effect, the task of a secret key distribution between two remote parties can be accomplished even when no particle carrying secret information is in fact transmitted. The secret key obtained in this way may be used for secure communications such as internet banking and military communications. This manuscript also shows that, in some cases, the mere possibility that an eavesdropper can commit a crime is sufficient to detect the eavesdropper, even though the crime is not in fact carried out. In a sense, part of the story of the SF film Minority Report seems plausible.

Emphasis mine. Horselover Fat would be proud.

Posted on

Holevo Additivity Falls? The Quantum Universe Gets Even Stranger

Major news from the quantum information front. Today I see posted on the arXiv a paper by M.B. Hastings: arXiv:0809.3972 “A Counterexample to Additivity of Minimum Output Entropy.” If correct this resolves one of the most famous open problems in quantum information theory, and, even more interestingly says that in a quantum world, transmitting classical information down quantum channel defies your classical intuition. Blessed be our quantum world, which just continues and continues to amaze.
Continue reading “Holevo Additivity Falls? The Quantum Universe Gets Even Stranger”

Posted on

Kitaev Wins MacArthur!

I just saw the news that Alexei Kitaev, a pioneer in quantum computing and an incredible physicst/computer scientist, has won a MacArthur “genius” award. Awesome!
Kitaev was my next door neighbor while I was a postdoc at Caltech, and among the many highlights of my short life I count listening to Kitaev’s amazing, confounding, brilliant and way over my head ideas. One event in particular I will always remember involved Alexei talking to theoretical computer scientists and, halfway through the talk, pointing out how Majorana fermions were essential to understanding what was going on in that particular computer science problem. Sure in retrospect I understood what he was saying, but how the hell did he make that connection?!?! Truly a genius and completely deserving of the MacArthur award. Congrats Alexei!
Update 8pm PST: Seems that news article has been taken down. Hmm.
Update 12:30am PST List of fellows now posted here. In a local note, David Montgomery who studies geomorphology has also been named a MacArthur fellow.