Efficient markets and P vs. NP

According to Phillip Maymin of the NYU Poly Department of Finance and Risk Engineering:

Markets are Efficient if and Only if P = NP

I prove that if markets are efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can “program” the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient. Specifically, markets become increasingly inefficient as the time series lengthens or becomes more frequent. An illustration by way of partitioning the excess returns to momentum strategies based on data availability confirms this prediction.

I guess this means that libertarians will be petitioning the Clay institute to collect their million dollars then?

Habemus Papam(s)!

fumata bianca
The conclave has reached an agreement. The new quantum papal dynasty will be a triumvirate consisting of:

  • Charlie Bennett
  • Aram Harrow
  • Steve Flammia

For those of you concerned about having three pontiffs at the same time, fear not: there is historical precedence. Urbi et Orbi.


For every talk in computer science and physics there is now at least one relevant xkcd comic (is it coincidence that this occurred near the same time of IPv4 exhaustion?  I think not.)

Doing My Part

Ryan Williams ACC. Which reminds me the other day a student of mine accidentally called coNP, coCP. Yep, turns out CP is a class. So the question is: will P versus NP be resolved before or after all two alphabetic symbol complexity labels are used up?

Shor on Shore

The important thing is to never, ever, ever pass up an opportunity for a bad pun. Especially a bad pun that might by some strange coincidence be stumbled upon by Wim van Dam or Michael Freedman while out taking a walk pondering the secrets to the quantum computing universe 🙂 Though I will say that this circuit is not resistant to the correlated errors that are waves that will soon wash it away.
Shor on Shore

Quantum Communications at CLEO 2011

Richard Hughes send along a call for contributed papers for the Quantum Communications Symposium at CLEO2011:

Call for contributed papers: Quantum Communications Symposium, CLEO2011

1-6 May, 2011, Baltimore, MD


Deadline for submissions: December 2, 2010 at 1700GMT

Dear Colleagues,

Tom Chapuran (Telcordia), Norbert Lutkenhaus (Waterloo), Iain McKinnie (Kapteyn Murnane Labs) and I are organizing a Quantum Communications Symposium at CLEO2011: http://www.cleoconference.org/conference_program/symposia.aspx

We are close to finalizing an outstanding line-up of invited talks from internationally-leading quantum communications researchers. At this time we are issuing a call for contributed papers to the symposium: please consider submitting your latest quantum communications research results at: http://www.cleoconference.org/submissions/Electronic_Submissions.aspx

To have your contribution considered for the symposium, please submit it to one of the following subcommittees:

CLEO:QELS – Fundamental Science 2: Quantum Science, Engineering and Technology;

CLEO: Science & Innovations 12: Lightwave Communications and Optical Networks;

CLEO: Applications & Technology 3: Government & National Science, Security & Standards Applications

no later than 1700GMT December 2, 2010.


Richard Hughes

Physics Division, LANL


Quantum Communications Symposium description:

Quantum communications is a rich interdisciplinary field encompassing fundamental science, innovative technologies, and a broad range of potential applications to computing, cryptography, and networking. Since the first experiments two decades ago, the transmission of quantum states has been extended to ranges of hundreds of kilometers, in optical fiber and in free space. Novel optical networking techniques have been developed to enable scalable communications among large numbers of users. Investigations of entanglement, teleportation, and other uniquely quantum phenomena have provided fundamental insights into the quantum world, while also laying critical groundwork for the development of quantum repeaters. Theoretical research has led to the emergence of wholly new cryptographic paradigms and applications, such as quantum key distribution, quantum secure identification and quantum secret sharing, whose security assurances are rooted in the laws of physics. Large-scale quantum communications testbeds have been demonstrated in recent years in several countries, and commercial standards activities are underway. The symposium will highlight the latest research results across the broad spectrum of quantum communications topics from fundamental science to practical applications. It will provide an overview of quantum communications in optical fiber networks and free-space, including the underlying science, components and technology impacting systems, networks, and field trials, with invited presentations from leading research groups around the world.


Thomas Chapuran, Telcordia

Richard Hughes, Los Alamos National Lab

Norbert Lütkenhaus, Univ. of Waterloo

Iain McKinnie, Kapteyn Murnane Labs

CLEO2011 blog:


QI Positions, Postdocs, Oh My

Well, someday this blog will turn back into a blog where I complain about the awful state of quantum computing (haha), cus you know I’m all about the negative stuff, but in the mean time here are new job postings. First up is a school that was crazy enough to admit me as an undergrad (legacy admit), Caltech:

Postdoctoral Research Positions
The Institute for Quantum Information at the California Institute of
Technology will have postdoctoral scholar positions available beginning
in September 2011. Researchers interested in all aspects of quantum
information science are invited to apply. The appointment is contingent
upon completion of a Ph.D.
Please apply on-line at http://www.iqi.caltech.edu/postdoc_opening.html.
Electronic copies of your curriculum vitae, publication list, statement
of research interests, and three letters of recommendation are required.
The deadline for receipt of all application materials is December 1,
The California Institute of Technology is an Equal
Opportunity/Affirmative Action employer. Women, Minorities, Veterans and
Disabled Persons are encouraged to apply.

Great postdocs if you get them, I mean you can even use them to work on crazy things like time travel. Okay, maybe I blew the limit on that topic, but maybe you could do a postdoc at the IQI and figure out how to use the black hole information paradox to solve problems in PSPACE.
Next up is a job in beautiful Malibu, California. Need I say more?! The job was sent to me by Jim Harrington, who can be reached for information at the job at his email address jim.harrington[this-is-an-at-sign]gmail.com The posting is at this link:

RESEARCH STAFF – Quantum Information Science
Job Type: Full-Time
Location: Malibu, CA
Post Date: 10/12/2010
Job Description:
Ph.D. in Physics, Computer Science, Applied Mathematics, or Electrical Engineering
Analyze and design algorithms, protocols, architectures, and fault tolerance techniques for quantum information science applications. Present ideas and results in effective technical presentations, write technical papers, reports and proposals. Work effectively in a collaborative environment.
Demonstrated research experience in quantum information science, the development and analysis of fault-tolerant quantum and classical error correction codes, and design and analysis of classical and quantum algorithms.
In depth understanding of multiple areas of quantum information science. Coursework or experience in theoretical computer science. Analysis and/or development of efficient approximation algorithms. Knowledge of discrete mathematics, numerical analysis and scientific computing techniques.
Excellent written and verbal communications skills, excellent problem solving skills, ability to work in team environment and to sit for long periods of time at a computer monitor, Ability to travel.
SPECIAL REQUIREMENTS (e.g. driver’s license, special tools or restrictions): U.S. citizenship. Ability to obtain Interim and/or Final Clearances (Post Start); Active DoD Security Clearance is a plus.
We are proud to be an EEO/AA employer M/F/D/V. We maintain a drug-free workplace and perform pre-employment substance abuse testing.

Also postdocs at the IQC in Waterloo that I don’t think I’ve posted:

We are pleased to announce that a number of openings for Postdoctoral Fellowships are available at the Institute for Quantum Computing (www.iqc.ca), a leading-edge research centre at the University of Waterloo, Canada.
Please share the information below with students or postdocs interested in pursuing theoretical or experimental research in quantum information.
Positions Available
IQC Postdoctoral Fellowships:
Successful applicants will join a world-leading team of 17 faculty members and approximately 100 students and postdocs pursuing all aspects of quantum information research, from fundamental theory to implementations. We seek exceptional candidates to help advance understanding of the foundations of quantum information, to develop new quantum applications and algorithms, to implement these ideas in laboratory experiments and engineered systems, and to transfer this knowledge to industry. IQC faculty and students span academic disciplines including Applied Mathematics, Chemistry, Combinatorics and Optimization, Computer Science, Electrical and Computer Engineering, and Physics and Astronomy.
Candidates must have a PhD and proven research abilities, or strong potential for excellence in research. Interested researchers can learn more about these positions and apply online here: http://new.iqc.ca/welcome/positions.
New — Banting Postdoctoral Fellowships:
In addition to IQC’s regular Postdoctoral Fellow positions, we are also seeking applicants for the prestigious Banting Postdoctoral Fellowships Program, recently created by the Canadian government, which provides $70,000 per year for two years. To indicate an interest in pursuing a Banting Postdoctoral Fellowship at IQC, please contact us no later than Oct. 15, 2010 by submitting an online pre-application here: https://service.iqc.ca/applications/positions/postdoctoral-fellowships/
Applications received by November 15, 2010, will be given priority.
Note: Applicants interested in the Banting Postdoctoral Fellowship should contact IQC immediately, given its earlier deadline.
For more information, please contact Wendy Reibel at wendy.reibel [here is an at sign] uwaterloo.ca