Wednesday, July 21, 2010
Quantum Chemistry Comes of Age
Quantum computers are now capable of simulating the behaviour of atoms and molecules.
There's no shortage of scientists waiting to get their hands on quantum computers. Cryptographers, in particular, are licking their lips in anticipation.
But there's another group who are already beginning to benefit from the first few iterations of quantum computing devices: chemists.
Various scientists have pointed out that it is possible to study the properties of a particular quantum system using another controllable quantum system.
This kind of quantum simulation has huge implications for chemistry. No longer would it be necessary to mess around with real atoms, ions and molecules in messy experiments with test tubes and bunsen burners.
Instead it ought to be possible to perfectly simulate what goes on using a quantum computer set up in the right way. That's the theory anyway. The practice is inevitably more tricky.
But quite remarkable progress has already been made, say Ivan Kassal, James Whitfield and few buddies at Harvard University in Cambridge who review the field.
Quantum computers are still primitive devices (relative to what they are expected to achieve). "In analogy to classical electronics, as of 2010, the implementation of quantum information processors is in the vacuum-tube era," they say.
But that hasn't stopped some steady progress. They point to experiments published earlier this in which researchers used quantum optics and nuclear magnetic resonance to simulate various properties of hydrogen molecules. More impressive still is the work of a group using superconducting qubits to simulate the aspects of the way a chaperone protein assists a four-amino-acid peptide that is still in press.
Make no mistake: simulating quantum chemistry on a quantum computer is hard. But it looks as if the field is poised for an explosion of new results. An exciting time to be a quantum chemist.
Ref: arxiv.org/abs/1007.2648 : Simulating Chemistry Using Quantum Computers
Massachusetts Institute of Technology
Comments
EPA terrorism, feminist spew re potentially pregnant females, and professional management have all but ended organic labs. Microscale preps are all the rage - make enough to appear as a TLC spot. One amusing result is a BS/Chem that cannot make 100 mg of anything, much less a kilogram.
One of Uncle Al's employers spent a fat four figures outsourced spinning band distilling a liter of monomer that would not cooperate. Uncle Al durped it pot to pot under vacuum into a cooled receiver in 40 minutes, then broke to argon. A polymerization-off followed. Only one worked.
The lethal impurity was... oxygen, from air. Strain out the lumps and store under argon. Go compute prior knowledge.
UncleAl
07/21/2010
Posts:90
I do not understand why we have to go into the esoteric world of quantum mechanics to resolve this difficult open problem of computer science.
I have several colleagues who went into quantum computing from computational comoplexity background. All of they just gace up. They said physicists do not understand logic. What is new.
Never mind quantum mechanics, it is already known that analogue computing is more powerful than digital algorithmic computing. El Por in the 1980's showed that there is a differential equation whose solution cannot be computed by algorithmic computation.
This leaves an open question if we can beat Church's thesis using hybrid computing.
Best regards,
AKT
AKT
07/22/2010
Posts:382
However, if you have an 8 bit quantum processor, when you wish to test all the possible values for a variable, you nudge the computer into the appropriate state of coherence and all 8 bits take on both a 1 value and a 0 value at the same time, which means that the 8-bit variable takes on all values between 0 and 255 at once. This accelerates things 256 times compared to an 8 bit conventional processor.
The real fun stuff is that, not only are we not limited to 8 bits (we will get 64 bit quantum processors) but when variables interact and each variable takes on all 256 values at once, you speed things by 2^16 instead of 2^8.
while theoretically speaking an NP problem is still an NP problem, the reason that you get NP problems is because of the interaction of variables rapidly increasing the number of "tests" required.
But even if you have 100 variables, when each takes on all values at once the increase in tests is only arithmetic, not geometric. Thus you don't have runaway numbers of possibilities - which is what makes a problem NP.
Essentially you've not redefined the NP problem as P, you actually have a new problem. The computational process is entirely different and so you are using, as it were, a new operation neither multiplication nor exponentiation, but something different that increases difficulty in a way similar to addition, but is not really addition either.
But if it helps - and I'm going to get this wrong myself, so I'll have to ask a math PhD friend of mine - you can think of the problem changing from 2^X into a form more like 2*X in terms of the number of tests/iterations are required for solving the problem. it is still true, of course, that the possibilities being considered are 2^X, but so many are considered at once that - and this is *very key*
the number of tests is not only no longer = the number of possibilities
The number of tests is no longer even *proportional* to the number of possibilities.
This makes things seem pretty amazingly fast in terms of computing answers to problems with large # of possibilities the way that NP problems have.
Now it's time for a real mathematician and quantum engineer to show up here, collaborate, and give you a truly good and accurate explanation!
here's hoping, 'cuz I can't have been so lucky to have gotten everything right and I'm as curious as you as to how all this works, exactly, to change computing times and exactly how/by what factor computing times are changed.
cripdyke
07/23/2010
Posts:39
So, there is nothing interesting in quantum computing from mathematics point of view. Quantum computing is just trying to implement an efficient nondeterministic computing machines. By definition if you have it you can compute NP problems in polynomial time. It is not a mathematical research. It is purely an engineering research.
Making Quantum Computers will not make any contribution to complexity theory.
It is already known that NP problems can be executed in exponential time if done deterministically. It is my prediction that likely NP problems are high order polynomial. So far, the only way to create high order polynomial problems is to use Cantorian diagonalisation. This is a very artificial method and we will not grasp nature of higher order polynomial problems. This is why we cannot show that P = NP. Even though each NP problem has equivalent P problem at higher order polynomial, we cannot find such program. As you know it was shown in 1980's that we cannot use diagonalisation to show that P = NP fails.
Anyhow it is an enginnering problem and when it comes to engineering problem, we already had a good example. UK government recently declassified their WWII time top secret information. It is about the world first electronic computer built before the ENIAC. It was a multiple tape parallel processing stored program machine designed specifically to break German ENIGMA code. This nondeterminsitc computer for the assigned tasks performed better than contemporary sequential deterministc computing machines, aka computer.
Best regards,
AKT
AKT
07/23/2010
Posts:382
But it turns out that you knew all that (and that thing about the UK - it seems you know a lot more about the history of practical attempts at solving NP problems than me). You're perfectly fluent in the concepts of polynomial time, etc.
And so now I'm confused as to why you would have posed the problem as not being able to see how this reduces NP to P - as we both said, it doesn't, but as is also just as clear, it doesn't matter.
So what was your question, anyway? Frankly, it seems like I could learn from you on this topic, but I'm not really sure how we ended up going down the road we're on. You did say that you didn't see how this reduces NP to P, I didn't imagine that. Can you tell me how the failure to reduce NP to P is relevant here if you can just load your code/data onto a non-deterministic machine (once quantum computing is a bit more advanced)?
Why exactly is the reduction of NP to P so important when it appears to me that QC makes it irrelevant? No sarcasm here, you genuinely seem to have an appreciation for this that I really don't.
As for me saying that I hoped both a mathematician and quantum engineer stopped by, yes, the machine is a non-mathematical exercise entirely. The mathematician was to tell us more specifically than I was able why, exactly, non-deterministic machines are necessary: perhaps explaining polynomial time and what it means to be "not solvable" in polynomial time.
It actually seems that you might be able to tell us. Of course, I have another friend who could do that & maybe I'll invite him over, but it seems like you might be able to provide a simple explanation and you're already here & commenting, so...
cripdyke
07/23/2010
Posts:39
I have been in the scene longer than you. I am a retired recursive function theorist and set theorist who also did some work in theoretical computer science. There as a generalised recursion theorist, I mostly worked on semantic theory of programming languages. In set theory, I worked on recursion theoretic set theory.
As a pure mathematician, I personally am not fully satisfied by the computational complexity theory. It is a theory on programs not of computable functions. For example, the theory fails at very basic level. One can represent numbers using Godel's representation. Then addition becomes more difficult than multiplication. For this they say as an excuse that their results depend upon "reasonable" representation. Godel's representation unreasonable? It gave us the realisation that most of consistent theories are incomplete.
NP hard problems are the problems for which we do not know how to compute deterministically in polynomial time. But we know how to do it in polynomial time using nondeterministic computation. NP complete problems are some NP hard problems which are complete in the sense that if one of them can be computed in polynomial time deterministically then all NP hard problems can be computer in polynomial time deterministically. So, mathematically reducing NP problems to P problem mean showing NP complete problems can be computed in polynomial time deterministically.
This is a very difficult open problem which was discovered by a research student in Moscow State University in the early 60's. His research supervisor did not think this was an important result and did not bother to publish it. Later, Steve Cook at Berkley discovered the same open problem and published it making a fortune out of it. Despite this result, Berkley did not understand the importance of this problem and denied tenure. Cook moved to Canada, and continued his research at the University of Toronto.
This problem is nothing outstanding in recursive function theory. This field of mathematical logic has tons of next to impossible open problems especially in subrecursive hierarchy theory involving syntactic complexity. (P =NP problem is a problem in dynamic complexity.) They are so difficult that virtually nobody can afford to work on them in this rat race of publish 30 papers a year or perish.
A top American recursion theorist Solvey once said that he quit working on the P=NP problem as it became difficult to separate between working on this problem and not doing anything.
Any way I have explained rather coherently how this problem has little to do with quantum computing. Quantum computing does not offer any solution to this problem of finding polynomial time deterministic computation for NP complete problems or showing that this is impossible.
Majority of researchers believe that P is not NP but cannot show it. I suspect that in fact the reason why so could be because they could be equal at the high order deterministic polynomials. In such case we have virtually no hope of showing how to reduce NP problem to P problems mathematically.
Making a practically effective enough nondeterministic computing machines such as quantum computers is an entirely different problem. By definition, if you use such machines you can compute NP problems with ease in polynomial time.
Best regards,
AKT
AKT
07/23/2010
Posts:382
The interest is purely mathematical. We know exponential problems are strictly more difficult than polynomial problems. Super exponential problems were considered and hierarchy of such problems were developed. But later it was shown that this whole hierarchy of super exponential problems collapse.
This Soviet maths student at Moscow State University showed that in between deterministic polynomial problems and exponential problems there appear to be yet another class of problems called NP problems. He presented NP complete problems which is complete in a sense that if one of them can be computed in deterministic polynomial time then all NP problems can be computed in Polynomial deterministic time. But he could not show of this is possible, he could not show if this is impossible either.
This kind of problems bother us mathematicians a lot. We have our own foundation problem which is the consistency of an axiomatic set theory ZF. This was proposed as an alternative to ill fated Cantorian set theory which Cantor himself proved to be inconsistent. You see, this is the difference between mathematicians and physicist. We have nothing but mathematics at stake. So, we are quick to admit failure when we failed. We do not need to have huge research grant to continue our research and so admitting error does not hurt us.
Returning to the issue, we cannot prove the consistency of this theory. We cannot prove the inconsistency of this theory either. I and my coauthor tried twice to prove this inconsistent and we fell short. Prof. Fefferman after reading our failed work wrote to us saying that he also hates ZF but he suspects that this theory might be consistent.
The problem here is that ZF is a first order set theory and so it cannot adequately express the concept of well-foundedness which is a second order concept. ZF has an axiom of regularity which is a first order (thus weaker version) of the well-foundedness. because of this weakness it barely escapes proving Richard paradox. We thought we showed the inconsistency (by proving Richard paradox) using the axiom of regularity but instead we used the full second order version of it, namely the well-foundedness.
So, I hope I have explained why real mathematicians (not the hyped up NEOCO mathematicians who destroyed our free market economy) are interested in these problems in suspense.
Anyway as I said, there is nothing mathematically interesting in quantum computing. It is a trivia that using nondeterministic computation we can solve NP problem in polynomial time. It is by definition. So, the only issue here is the implementation of good nondeterministic computing systems.
Well to my knowledge analogue computers are also nondeterministic non sequential computing machines. I do not know why this is mnot taken seriously.
I want to know if it is possible to beat Church's thesis by adding AD converters to analogue computers.
Best regards,
AKT
AKT
07/24/2010
Posts:382
This is not a personal attack, but your assaults on physics and physicists are a bit hard to take. The fact is that most of mathematics (at least that part of practical importance) was invented by physicist. Take Newton's invention of calculus. Now from your point of view, it would seem that his work was a complete failure because it lacks the purity of logic needed to defend it (for example from Bishop Berkley's attacks). I would point out that after this invention; it took mathematicians many years to arrive at a formalism in which calculus could be properly understood.
It's all well and good that such a formalism was arrived at, but in the meantime Newton's invention was predicting the motions of the heavenly bodies and many other things.
I have nothing against theoretical mathematics. It's just the unjustified arrogance that troubles me.
TooMany
08/01/2010
Posts:79
We are not here to fight each other, but to have a friendly debate and throw ideas and knowledge at each other.
I for one tried to understand relativity and it took me some time to resolve Einsteins first equation(15 mins-synchronous time..loved it), thats how difficult it is looking at something without knowing what came before. The second equation lost me for I had no foundation to extrapolate it from.
Hence I love these blogs, the people here can turn equations into words, and i can understand words.
Do not fault the people, fault yourself.
mattgroom
08/01/2010
Posts:198
Very few will care and I doubt much of anything in the world will change if someones proves P=NP or it's opposite. But Einstein's discoveries did indeed change the world and deserve some respect.
The contrast between AKT's take and cripdyke's is interesting. Cripdyke's point is that from a practical standpoint whether P=NP or not is of little importance if NP != P posses no practical barrier. On the other hand AKT trivializes this, in effect asserting it is unimportant because it is only a practical matter and not a solution to the theoretical problem.
I guess it depends on which world you find more important, the real or the theoretical.
TooMany
08/01/2010
Posts:79
Physicists do not know much about reality. Sure, engineers know much more about reality.
They know nothing about mathematics. They just talk big and make sweeping statement on things which they do not understand.
Best regards,
AKT
AKT
08/02/2010
Posts:382
P = NP problem has importance as it is related to the fundamental problem of power set which causes all kind of problems in set theory. If you talk about theory, please look at things from wider perspective. Anything in between, which is what dominates in this age of Reaganic NEOCON nonsense, tons of public money has been wasted on those wishy washy "scieitific" projects which has neither practical nor theoretical significance.
Best regards,
AKT
AKT
08/02/2010
Posts:382
It is not this generation of academic physicists who will pay the price. These corrupted generation have extracted a lot of earthly by defending the cult activity of the syndicate. It is the future generation of physicists who will pay for the crime committed by the current generation.
This world is now ruled by information scientists and they are well equipped to see that theoretical physics is all pure nonsense.
Best regards,
AKT
AKT
08/02/2010
Posts:382