# Notes on “The Limits of Knowledge…”

Published on: Fri Nov 19 2010

I went to a talk at The Simons Center for Geometry at Stonybrook today, given by Michael H. Freedman from Station Q, Microsoft Research.
The talk was titled: The Limits of Knowledge: The Philosophical & Practical aspects of Building a Quantum Computer". It was quite an ambitious topic, and right away it took off in an unexpected direction, with the speaker announcing he intended to interweave Philosophy and Math/Physics using an unexpected analogy between Catholicism & Math/Physics. Everyone raised an eyebrow at this, but the analogy made sense: both are long term institutions and deal with difficult idea's on the long timescale. He focused on the difficult ideas aspect and narrowed the analogy down to four ideas:
Omniscience >> P/NP
Original Sin >> Universality
Redemption >> Quantum Mechanics
Unicity >> Free Will
From those four ideas he moved on to idea's about scaling. Like universality, things viewed from 10 feet away and 10 nanometers away, often look like the same thing. His slide photos showed the Mandlebrot set, which reminded me of Mandlebrot's book, where the coast of England and the contours of a pebble from the coast of England are compared with each other. (They look the same)
Quantum Computing is between Physics, Computer Science and Math. and there are some problems we are trying to solve, and some problems we can solve. They go in order of difficulty: **Pspace >>>> Q >> NP >> P** ,right now we can solve **P** and in a short amount of time. **NP** we can solve but it takes quite a lot of time (work?). **Q** we hope to be able to solve using Quantum Computing technology, which obeys different scaling laws.
Now, for a brief bit on the history of computers. Classical computers are all Turing machines, they can handle P and sometimes NP. At the most, all we will ever know (compute) is in the **Q** region of problems. (unless possibly in a different universe where NP-complete could be solved efficiently...)
So, what is the special thing about QC which lets us move into the **Q** region of problems? Here the speaker was quite dramatic, and said he could tell us why in one word. "Superposition". But he then went on to note, that this doesn't really mean much unless you understand the idea of superposition.
Nature likes square roots of probabilities (Like the double slit experiment)
We observe **| a + b** | but we expected to see **|a|^2 + |b|^2** Why is this? Shor's algorithm is like the double slit experiment, where useless paths cancel out. There is a classical aspect and quantum aspect to Shor's algorithm. The quantum mechanical aspect allows for a Fourier Transformation to k space, making it much easier to find the period. (Which is used in factoring)
Some of the things a Quantum Computer could do: Physics! Things like: Strongly correlated electron systems, High temperature superconductors, 2 dimension electron gasses (2 DEG), Exotic magnets (condensed matter), Sample google large linear equation sets, Drug design and AI.
How are we going to get these computers? (An excellent question was asked after the talk too, If we do get them and have no classical means of solving the problem, how will we know the QM computer is actually solving it?) One of the ways to get it is by using Topology, which has to do with the math of strings and braids (ironic, that the only math class I've taken on this was at FIT, because supposedly art students love topology...) The topological approach avoids using the physically provided degrees of freedom, and instead works to touch all the degrees at once, (Need 2DEG for this) the eventual goal is to get some Majorana Fermions (MJ's?) localized in "vortices". I'm not too sure what MJ's are exactly, or if that is the actual goal..
MJ's allow for huge, but still finite blackboards of Hilbert space. I think the Fractional Quantum Hall Effect has something to do here too... Maybe MJ's are Quantum Hall States?
Fractional Quantum Hall Effect is topological, meaning distance plays a limited role in them.
There was a picture of four dots, and how when you connect two at a time over time, it forms a braid like pattern. I drew it in my notebook.
And near the end was a slide of man's toolbox it went:
Fire > Number > Machine > Decimal > Computer > Nuclear > Biology > Quantum Computer