Yep, it’s that time again. Paper dance time!
arXiv:1006.4388
Making Classical Ground State Spin Computing Fault-Tolerant
Isaac J. Crosson, Dave Bacon, Kenneth R. Brown
We examine a model of classical deterministic computing in which the ground state of the classical system is a spatial history of the computation. This model is relevant to quantum dot cellular automata as well as to recent universal adiabatic quantum computing constructions. In its most primitive form, systems constructed in this model cannot compute in an error free manner when working at non-zero temperature. However, by exploiting a mapping between the partition function for this model and probabilistic classical circuits we are able to show that it is possible to make this model effectively error free. We achieve this by using techniques in fault-tolerant classical computing and the result is that the system can compute effectively error free if the temperature is below a critical temperature. We further link this model to computational complexity and show that a certain problem concerning finite temperature classical spin systems is complete for the complexity class Merlin-Arthur. This provides an interesting connection between the physical behavior of certain many-body spin systems and computational complexity.
Dave, that’s a really interesting preprint … full of good ideas IMHO.
I to reach the topic that most interests me, I had to read all the way to the final sentence: “Another interesting question is the rate at which the ground state spin model thermalizes; a proof that the system reaches thermal equilibrium in a time polynomial in the size of the circuit being implement would be another step towards making this model more physically relevant.”
Here several interlocking considerations arise. Let’s imagine that we investigate this question by a direct numerical computation, more specifically, by numerically computing the trajectory as an integral curve of a Hamiltonian flow. If we integrate dynamical trajectories on a tensor network state-space (for reasons of numerical efficiency, perhaps) then for rank 1 the dynamical flow is, unsurprisingly, the (classically symplectic) Hamiltonian flow of the Bloch equations.
Similarly, in the large-dimension limit the state-space curvature is “dimensionally drowned” (specifically, for rank >= 2^{O(n_spin)}), and the resulting simplified dynamical flow is the (quantum-symplectic) Schroedinger equations on a linear Hilbert state-space; thus both the low-rank and high-rank state-space limits are geometrically simple.
From a simulationist point of view, the geometric simplifications and numerical efficiencies attendant to this large-rank “dimensional drowning” are the pragmatic reasons that Hilbert space is such a popular venue for quantum dynamical calculations; in essence, Hilbert space is a (hugely convenient) large-rank approximation.
Lastly, for intermediate rank we have a hybrid simulation that is *also* symplectic.
Now we appreciate that because the dynamical flow is symplectic for all state-space ranks, by adjusting the rank we vary the dynamics to be “as quantum as we want”; this provides a well-posed (and numerically tractable) model for studying the classical-quantum transition.
Of course, we still have to couple the dynamics to an external reservoir, and here many subtleties arise, both formally and numerically, in both the fully classical and fully quantum limits (and for every state-space rank in-between).
Unsurprisingly, any obstruction to a physical system’s approach to thermal equilibrium, also obstructs the efficient numerical simulation of that system’s approach to equilibrium. When it comes to working through the details, I highly recommend two 1988 articles by Ford, Lewis and O’Connell, titled “Independent oscillator model of a heat bath: exact diagonalization of the Hamiltonian” and “Quantum Langevin equation”.
AFAICT, it would be possible to adapt the Ford-Lewis-O’Connel thermalization models to intermediate-rank state-spaces in general, and to your ground-state computational dynamics in particular, but to the best of my knowledge, no-one has yet done so.
In summary, your (outstanding IMHO) preprint establishes that both low-rank and high-rank symplectic ground-state dynamics exhibits a rich computational structure … which is to say, the Hamiltonian potentials on these manifolds exhibits a rich computational structure … and now so we have the natural challenge of describing the computational structure of the middle-rank state-spaces too.
That’s *one* way to read your article, anyway … the reason it’s an outstanding article (IMHO), is that there are so *many* interesting ways to read it.
Hi alla;
“In summary, your (outstanding IMHO) preprint establishes that both low-rank and high-rank symplectic ground-state dynamics exhibits a rich computational structure … which is to say, the Hamiltonian potentials on these manifolds exhibits a rich computational structure … and now so we have the natural challenge of describing the computational structure of the middle-rank state-spaces too.
That’s *one* way to read your article, anyway … the reason it’s an outstanding article (IMHO), is that there are so *many* interesting ways to read it.”
mary lou…
I provided some historical context for the above discussion over on Ian Durham’s Quantum Moxie, in the context of an evolving narrative in which:
(1) 19th century Parallel Postulate ‚áà 21st century “Quantum Linearity”
(2) 19th century Riemannian dynamics ⇈ 21st century Kählerian dynamics
(3) 19th century navigational science ‚áà 21st century quantum systems engineering
(4) 19th century texts like Bowditch ‚áà … texts that haven’t been written yet!
Even the scientific factions map cleanly: Gauss’ 19th century concerns regarding the “outcry of the Bœotians”, that is, 19th century mathematicians who embraced Euclidean geometric axioms, maps onto the early 21st century outcry of the “quantum Bœotians”, that is, those physicists who axiomatically embrace Euclidean quantum dynamics.
JVP, I take it you wouldn’t agree with Roger Cooke’s “I think that the work of the mathematician is precisely to remove the mystery from the universe, even though a universe without mystery would be dull … Reducing the need for genius is (in my view) the central aim of mathematics.”
Here Cooke is expressing a theme that has been prominent ever since Bowditch’s 1802 mariner’s text … and is well-exemplified in modern times by (for example) Petkovsek/Wilf/Zeilberger’s A=B … and it is a theme that no doubt will continue in our 21st century.
So an interesting question is, which 21st century math-and-science disciplines are destined to prominently diminish in mystery, and thereby, reduce their need for genius?
It is only mildly contrarian (IMHO) to foresee that quantum information science may perhaps be one of those disciplines … especially since articles like the Crosson/Bacon/Brown preprint can be read as significant advances in that direction.
Of course, clearing away old mysteries always makes room for newer, deeper mysteries. Good! We engineers are eager for this cycle to progress as rapidly as feasible!
As Steve Martin memorably says in The Jerk: “Waiter! Take away this old wine and bring us some new wine!” 🙂
What a great paper! Now I’ll have to quote you in the remaining 7 chapters of my Quantum Computing/First Contact novel (working title “Fermi’s Facebook) which, in the first 37 chapters, already quoted Prof. Scott Aaronson (with permission) on Merlin-Arthur complexity. The ETs use Anyons, and the DOD wants to break their error-detection/error detection, thermally if necessary (chemical laser onboard an Aurora). Oh, and I posted your abstract and arXiv link on my facebook page…
From my Facebook page in the past couple of minutes:
Nicholas Post
Why did they let Jim Lee redesigned her? Alex Ross is better, even Adam Hughes!
Jonathan Vos Post
Nicholas: I assume that you mean Nelson Alexander “Alex” Ross (born 22 January 1970) : American comic book painter, illustrator, and plotter, acclaimed for the photorealism of his work; as opposed to Alex Ross (born 1968): American music critic. He has been on the staff of The New Yorker magazine since 1996 and published a critically acclaimed book on 20th-century classical music in 2007, The Rest Is Noise: Listening to the Twentieth Century. I suppose that Dave Bacon (double B.S. in Physics and English from Caltech) might someday write a book called “The Rest Is Quantum Noise: Listening to the Twentyfirst Century.”
For that subset of Quantum Pontiff readers who enjoy studying the early history of math and science, on Ian Durham’s Quantum Moxie blog I have posted some key bibliographic references relating to the central role that ideas of state-space structure played in the development of math, science, and engineering during the 19th century.
This I take to be a key issue too for modern-day quantum information science, and for the Crosson/Bacon/Brown line of research in particular.
As I have said before, it is not necessary that everyone regard quantum information science (QIS) in the same way—this would not even be desirable.
The supplied references provide an (exceedingly optimistic) 19th century perspective on 21st century QIS—a perspective that no-one is obligated to share.
The 19th century perspective on QIS does turn out to be mighty fun, though! 🙂
Indeed, I did continue to continue the topic:
I have heard Scott Aaronson’s comparison of a proof p = np to finding out God is either right or left handed. To me this seems a little silly.
I openly welcome your advice and a rigorous reproof:
Of the text posted here: http://scottaaronson.com/blog/?p=446#comment-43384
Sincerely,
Professor X
root@bt:~# help prove p = np true
pushd: pushd [ dir | +N | -N ] [-n]
Adds a directory to the top of the directory stack, or rotates the stack, making the new top of the stack the current working directory. With no arguments, exchanges the top two directories.
+N Rotates the stack so the Nth directory (counting from the left of the list shown by ‘dirs’, starting with zero) is at the top.
-N Rotates the stack so the Nth directory (counting from the right of the list shown by ‘dirs’, starting with zero) is at the top.
-n suppress the normal change of directory when adding directories to the stack, so only the stack is manipulated.
dir adds DIR to the directory stack at the top, making it the new current working directory.
You can see the directory stack with the ‘dirs’ command.
pwd: pwd [-LP]
Print the current working directory. With the -P option, pwd prints the physical directory, without any symbolic links; the -L option makes pwd follow symbolic links.
true: true
Returns a successful result
The portion below is from a student:
Rodriguez-Ariz, Xochitl
Period 4
The math behind Game Theory
Game Theory is a wide assortment of topics and themes having to do with daily life, business or the mechanics behind games like poker and checkers. Besides the game there is a mathematical side, such as with Miserere play rules and P-position and n-position both stand for turn of players. P-position stands for previous player position and N-position with next player position. Both are not difficult to understand but become difficult to use and explain for certain games. Certain games like Nim Sum use difficult to understand rules. A certain rule goes hand in hand with this game is Fibonacci Nim. Similar to regular Nim the only change is the maximum can be taken is double the amount the first player took. For example for 1 token taken in the game at your turn, you can take either 1 or 2, however if your opponent decides to take 5, you in turn my take 1 to 10. The sequence of numbers can be taken is defined as F1=1, F2=2, and Fn +1= Fn + Fn-1 for n ‚â•. So it can then be written as 1,2,3,5,8,13,21,34,55 and so on and so on. Although there is a limited side of mathematics to Game Theory, it takes place as the foundation and explanation for many of the aspects of each game played.
A, Xochitl please keep up the good work.
Sincerely, M. M. M. h t t p : / / m e a m i . o r g
I just added to my BibTeX database the following quotation from Michael Neufeld’s Von Braun: Dreamer of Space, Engineer of War:
“Most touching for von Braun was the enthusiasm of children and teenagers, who wrote in large numbers, many asking how they could get an education suitable for a space program.”
It is sobering that in quantum information science, there is nowadays not much evidence of comparable enthusiasm, anywhere in the Blogo-sphere.
The intellectual vigor and cheerful optimism of blogs like Quantum Pontiff, Shtetl Optimized, and Quantum Moxie serves a vital social purpose … and conversely, when blogs fall silent, it’s mighty discouraging to prospective young mathematicians, scientists, and engineers.
There was much conversation about von Braun, with whom my father worked, and one of my brothers met, at Westercon 63. There were several panels on human space travel, and a space historian corrected me as we were Giving Panel. I’d said that von Braun was smuggled into Alabama via Operation Paper Clip, and he said (rightly): no, El Paso. Again, there was conversation with Karen Anderson (widow of Poul Anderson) and others in the Green Room about the A-9/A-10, 2-stage V-2 successor designed for transatlantic strikes against New York and Washington D.C., a universe in the multiverse which appears in a nearly completed novel manuscript of mine.
But back to Quantum Computing: any thoughts on Wan-li Yang et al. One-step implementation of multi-qubit conditional phase gating with nitrogen-vacancy centers coupled to a high-Q silica microsphere cavity. Applied Physics Letters, 2010?
http://www.sciencedaily.com/releases/2010/06/100629170945.htm
Now a team of researchers from the Wuhan Institute of Physics and Mathematics, the Chinese Academy of Sciences and the Hefei National Laboratory for Physical Sciences at the Microscale at the University of Science and Technology of China has made a step toward a warmer solution. As reported in the journal Applied Physics Letters, published by the American Institute of Physics (AIP), the team is exploring the capabilities of diamond nitrogen vacancy (NV) materials. In this material, a “molecule” at the heart of an artificially created diamond film consists of a nitrogen atom (present as in impurity amid all those carbon atoms) and a nearby vacancy, a place in the crystal containing no atom at all. These diamond structures offer the possibility of carrying out data storage and quantum computing at room temperature.
JVP, we’ve updated our MRFM home page to provide links to some of the issues that you raise, under the aegis of a debate between quantum “skeptics” and quantum “Boeotians”.