Simple circuit "factors" arbitrarily large numbers

Last Thursday, at the QIP rump session in Beijing, John Smolin described recent work with Graeme Smith and Alex Vargo [SSV] showing that arbitrarily large numbers N can be factored by using this constant-sized quantum circuit

to implement a compiled version of Shor’s algorithm.  The key to SSV’s breathtaking improvement is to choose a base for exponentiation, a, such that the function a^x bmod N is periodic with period 2.  (This kind of  simplification—using a base with a short period such as 2, 3, or 4—has in fact been used in all experimental demonstrations of Shor’s algorithm that we know of).  SSV  go on to show that an a with period 2 exists for every product of distinct primes N=pq, and therefore that the circuit above can be used to factor any such number, however large.  The problem, of course, is that in order to find a 2-periodic base a, one needs to know the factorization of N. After pointing this out, and pedantically complaining that any process requiring the answer to be known in advance ought not to be called compilation, the authors forge boldly on and note that their circuit can be simplified even further to a classical fair coin toss, giving a successful factorization whenever it is iterated sufficiently many times to obtain both a Head and a Tail among the outcomes (like having enough kids to have both a girl and a boy).   Using a penny and two different US quarters, they successfully factor 15, RSA-768, and a 20,000-bit number of their own invention by this method, and announce plans for implementing the full circuit above on state-of-the art superconducting hardware.  When I asked the authors of SSV what led them into this line of research, they said they noticed that the number of qubits used to do Shor demonstrations has been decreasing over time, even as the number being factored increased from 15 to 21, and they wanted to understand why.  Alas news travels faster than understanding—there have already been inquiries as to whether SSV might provide a practical way of factoring without the difficulty and expense of building a large-scale quantum computer.

John Stewart Bell Prize 2011 Nominations

John Bell Prize nominations:
Dear friends and colleagues:
We are pleased to announce John Stewart Bell Prize 2011, and ask for your assistance in identifying candidates for the award.
The John Stewart Bell Prize for Research on Fundamental Issues in Quantum Mechanics and their Applications (short form: “Bell Prize”) will be awarded every other year, in particular again in 2011, for significant contributions first published in the 6 years preceding January 1st of the award year.  The award is meant to recognize major advances relating to the foundations of quantum mechanics and to the applications of these principles – this covers, but is not limited to, quantum information theory, quantum computation, quantum foundations, quantum cryptography, and quantum control.  The award is not intended as a “lifetime achievement” award, but rather to highlight the continuing rapid pace of research in these areas.  It is intended to cover even-handedly theoretical and experimental research, both fundamental and applied.
The award is funded and managed by the University of Toronto, Centre for Quantum Information and Quantum Control (CQIQC), but the award selection will be handled by an arms-length selection committee.  The membership of the 2011 committee is
Alain Aspect
Nicolas Gisin (winner of the inaugural Bell Prize 2009)
Aephraim Steinberg, ex officio vice-chair
John Preskill
Peter Zoller chair
The award will be presented as part of the biennial CQIQC conference, during which the awardee will be invited to deliver a prize lecture.
To nominate a candidate for this award, please email your nomination to Anna Ho, CQIQC administrative assistant, at aho [atatat]  The nomination should include the name and affiliation of the nominee, a 1-2 paragraph statement of the importance of the contribution on the basis of which you are making the nomination and the principal literature citations to this work (which must have been published between January 2005 and December 2010). Self-nomination is prohibited.
All nominations received prior to December 25, 2010 will be considered (although the committee will not be bound to restrict itself to these nominations).
Thank you in advance for your assistance,
Peter Zoller
on behalf of the Bell Prize selection committee

QIP 2011 Call for Submissions Lah

QIP on the equator:

QIP 2011
Call for submissions
14th workshop on Quantum Information Processing
Tutorials January 8-9, NUS, Singapore
Workshop January 10-14, The Capella, Sentosa Singapore
Conference Website:
Paper Submission:
Quantum Information Processing (QIP) is a rapidly developing field of research spanning both physics and computer science. As the name implies, the field extends information processing (including computing and cryptography) to physical regimes where quantum effects become significant.
QIP 2011 is the fourteenth workshop on theoretical aspects of quantum computing, quantum cryptography, and quantum information theory in a series that started in Aarhus in 1998 and was held last year in Zurich. QIP 2011 will feature plenary talks (called invited talks at previous QIP workshops), featured papers (previously called long contributed talks), contributed papers, and a poster session.
Submissions of abstracts for contributed papers are sought in research areas related to quantum information science and quantum information processing. A small number of contributed paper submissions will be selected as featured papers. The submission to QIP should consist of 2-3 pages, containing a non-technical, clear and insightful description of the results and main ideas, their impact, and their importance to quantum information and computation.  In addition, the submission should direct the reader to a technical version of the work (this should preferably be online but otherwise can be provided as an
attachment). The submission should not consist of a compressed version of the technical exposition of the paper, but instead should facilitate the reading of the technical version and help the program committee assess its importance. In exceptional cases, submissions
without technical versions may be accepted.
The 2-3 page abstracts of the accepted contributed papers and featured papers will be posted on the QIP 2011 website.  More details will be provided in the acceptance notices.
Submission deadlines
Contributed papers: October 14
Posters: December 1
Notifications of acceptance
Contributed talks: November 17
Posters submitted by November 10: November 17
Posters submitted after November 10: December 8
Programme Committee:
Andris AMBAINIS (University of Latvia)
Steve BARTLETT (University of Sydney)
Wim van DAM (UC Santa Barbara)
Daniel GOTTESMAN (Perimeter Institute) (chair)
Pawel HORODECKI (Gdansk University of Technology)
Iordanis KERENIDIS (Universite Paris-Sud)
Hirotada KOBAYASHI (National Institute of Informatics)
Robert KOENIG (Caltech)
Barbara KRAUS (University of Innsbruck)
Mio MURAO (University of Tokyo)
Peter SHOR (MIT)
Graeme SMITH (IBM)
Frank VERSTRAETE (University of Vienna)
Michael WOLF (Niels Bohr Institute)
Steering Committee:
Dorit AHARONOV (Hebrew University of Jerusalem)
Ignacio CIRAC (MPQ, Garching)
Renato RENNER (ETH Zurich)
Louis SALVAIL (Universite de Montreal)
Barbara M. TERHAL (IBM T J Watson)
John WATROUS (University of Waterloo)
Andreas WINTER (University of Bristol / CQT, NUS) (chair)
Andrew Chi-Chih YAO (Tsinghua University)
Local Organisers:
Cedric BENY (Poster Session)
Rahul JAIN (Local Arrangement and Social Events)
Hartmut KLAUCK (Tutorials)
KWEK Leong Chuan (Sponsorship)
Darwin GOSAL (Webmaster)
Markus GRASSL (Outreach and Publicity)
Ethan LIM (Webmaster)
Tomasz PATEREK (Rump Session)
Stephanie WEHNER
Andreas WINTER (Coordinator)
Miklos SANTHA (Advisor)

Where Quantum Computing Theory Is Done

Update 4/5/09: The wandering Australian does an analysis by institution.
Today, because I have way to many deadlines fast approaching, I needed to waste some time (procrastineerering), I decide to take a look at the last years worth of scited papers on the quant-ph section of The question I wanted to investigate is where quantum computing theory is occurring worldwide. So I took the top scited papers scoring over 10 scitations (42 papers in all) and looked at the affiliations of the authors: each co-author contributed a fractional score to their particular region (authors with multiple affiliations had their votes split.) And yes, I decided to lump all of Europe together and combined Japan and China (sorry). The results are as follows:

  • US: 40.07%
  • Europe: 30.68%
  • Canada: 18.75%
  • Singapore: 5.54%
  • China/Japan: 3.77%
  • Australia: 1.19%

Of course these results are subject to a plethora of problems: I mean the idea that one can extrapolate from a half rate voting website is silly! But that’s what blogs are for, no? So let’s plunge in 🙂
To me it was interesting to see that the U.S. is doing as well as it is, considering that fact that there have been considerably less hires of junior faculty in the U.S. in quantum computing that elsewhere. In looking at this it seems pretty clear to me at lot of this has to do with two institutions: Caltech (the IQI) and MIT. Another interesting fact for me was that Canada did not score as high as I would have expected, considering the vast resources that exist at the University of Waterloo and the Perimeter Institute. Finally it was quite impressive to look at the number of European contributions from the U.K.: far higher than I had appreciated.
So what conclusion should you draw from this? Probably none at all, considering the suspect methodology, but if you want something to write home about it’s probably: the U.S. is behind the combined juggernaut of Canada and Europe 🙂

Quantum Police, Arrest This Woman

Okay this one from ScienceDaily made my day. No it made my week. The title is “Police Woman Fights Quantum Hacking And Cracking.” Intriguing, no? Who is this mysterious police woman in quantum computing? I don’t know many police offers involved in quantum computing, but yeah, maybe there is one who is doing cool quantum computing research (“cracking?” and “hacking?” btw.)
I open up the article and who is the police woman? It’s Julia Kempe! Julia was a graduate student at Berkeley during the time I was there, a close collaborator of mine, and well, last time I checked, Julia described her job as “a senior lecturer (assistant professor) at the School of Computer Science at Tel-Aviv University” not as “policewoman working on quantum hacking and cracking.” And here I was hoping that we’d have someone to arrest anyone making false claims about quantum mechanics!

Fudzilla Plays Telephone and Loses

Here is an article at about a result in quantum computing (see here for my own article on this result.) And here is an article on the website fudzilla describing this physorg result. How in the world do you get from the physorg article to fudzillas: “Top boffins who have been looking under the bonnet of Quantum computers are starting to think that they may not be the future of computing”?
Is the internet version of the game telephone more or less noisy than the spoken game?

A What Bit?

A correspondent writes to me about a recent article in the APS News describingThe Top Ten Physics Stories of 2008 and notes a very troubling sentence:

Diamond Detectors
Work on the molecular structure of carbon continues to show great promise for quantum computing. This year scientists were able to construct a nano-scale light source that emits a single photon at a time. The team first removed a solitary atom from the carbon’s otherwise regular matrix and then introduced a nitrogen atom nearby. When they excited this crystal with a laser, single polarized photons were emitted from the empty space. These photons could be used to detect very small magnetic forces. Additionally the photons emitted contained two spin states and were able to exist in that state for nearly a millisecond before their wave function collapsed. The emitted photon is essentially a long-lasting qbit which could, with further development, be entangled with other adjacent qbits for uses in quantum computing. Another team at the University of Delft in the Netherlands, working in conjunction with UCSB, was able to detect the spin of a single electron in a diamond environment. At the same time, a group at Harvard was able to locate within a nanometer a single Carbon-11 impurity using its nuclear spin interactions.

Qbit? What’s a qbit? Doh.

A Race for Quantum Computing People

Okay, quick, who can be the first to tell me what is drastically wrong with arXiv:0804.3076? (via rdv.) Winner gets a beer next time I see them. This is almost as fun as the game of trying to spot the error in papers claiming thethe discovery of a quantum algorithm for efficiently solving NP-complete problems.