I don't suppose you could spend a post or two explaining in your nice easy to understand way exactly what it is a quantum computer is supposed to do and how this might impact the NP problems.
It's not exactly known.
Grover's algorithm provides a quadratic speedup over brute-force algorithms for solving NP-complete problems, but that still leaves them as exponential-time. BQP (Bounded error, quantum, polynomial-time; basically the complexity class of quantum computers) is suspected to be disjoint from NP and a superset of P, but neither is known for sure.
Eliezer -- this post goes straight to my Favorites. Giving concise, straightforward summaries to posts is a great idea.
My attention is very fragmented (thanks to my job), so when reading Quantum Arena, I completely missed the point of the post which you gave in your excellent summary:
"Instead of a system state being associated with a single point in a classical configuration space, the instantaneous real state of a quantum system is a complex amplitude distribution over a quantum configuration space."
This sentence, in fact, has told me a lot more than the entire post -- which, of course, I'm going to re-read now.
Please consider including such summaries / guides for every series of posts you write. It would be even better if you could include such summaries into a dependency graph like the one you posted here earlier -- for example, the summaries might display when a user hovers the mouse cursor over a graph node.
Question : money derived from those ebooks, goes it to the singularity institute ? In other words, is buying one of these equivalent to donating money to the institute ?
In the Timeless Physics section:
"The laws of physics are perfectly local; the configuration space is perfectly local."
Aren't the laws global?
Will the eBooks also be available as hard copies? I'm probably not alone in preferring to read long texts on paper, and printing them out isn't quite the same.
Eliezer, thank you very much for all of these posts. I believe that this post is an excellent way of presenting them all in a reasonable sequence.
I hope you can include this Tom the Dancing Bug cartoon in your e-book, as an example of what you're arguing against.
This link appears to be broken:
http://lesswrong.com/lw/r7/quantum_physics_revealed_as_nonmysterious/
This is for everybody who can't wait on the upcoming e-book. I put the Basic quantum explanations in an e-book format myself, which you can download here: http://www.share-online.biz/dl/COXXQR5M6NJ0 The format is for the Amazon Kindle. I created it by copying the html-versions into Word, removing the comments, saving them as .pdf, and finally i created the e-book with callibre. The pictures are sligthly above the place where they are supposed be, apart from that everything should be fine.
Enjoy!
This reminds me, it has been over three years since this was stated:
My current plan calls for the quantum physics series to eventually be turned into one or more e-books.
Considering this has not happened yet, I'm just wondering if there has been any word if this is still the plan.
I've read all posts in the Basic Quantum Mechanics section, plus many of the links from it and a handful of others (working through the rest, I'm still only three days into this). Quantum mechanics is something I've had vague explanations of from education and discussions with educated people, but it seemed extremely complicated and confusing due to almost precisely the issues touched on in the normal way it's taught. Thank you for putting down the steps needed to walk me through rewriting my basic assumptions of reality to more accurately reflect how reality likely works, it's been very fun and interesting. I'm starting to feel like a native of the quantum universe, and.. it kinda makes sense. Definitely a whole lot more sense than my previous mangled understanding of probabilities and wave/particle duality. Having a base level reality which works very differently from high level phenomenon which feel more intuitive does not seem like a great surprise.
Anyway, one idea I've had which seems interesting to me, but I am not yet in knowledgeable to evaluate properly and would like thoughts on:
Would you, under the many worlds interpretation, be able to experimentally test whether a universe is infinite in time but not space?
I know that infinite time+finite space not a favored model for cosmology currently, but it's still interesting to me if quantum physics testably disproves a whole class of possible universes. And if by this (or similar) reasoning an infinite time/finite space universe is found to be incompatible with many worlds, finding evidence extremely strong evidence of an infinite time/finite space universe (highly unlikely as I understand it) would perhaps bring many worlds into question.
Possible line of reasoning:
Points one, three, and four seems to me like the most likely weak link, but I'd be interested to know why this is not the case if it is indeed not the case. Perhaps at maximum-entropy each branch gets stuck in a unique infinite loop rather than visiting the rest of configuration space?
If the chain of reasoning holds and leads to the conclusions.. perhaps a stronger version of this argument could perhaps be constructed for a universe infinite in both time and space (depending on whether indefinitely expanding thermodynamic systems will reach all possible configurations given infinite time), though I'm already feeling somewhat out of my depth dealing with the weaker argument.
From a quick glance at your argument, it seems to me that quantum mechanics breaks down on the cosmological scale.
hm, from what I've been taking from the sequence quantum physics seems to apply fully at all levels, and the idea of it working differently/not applying is simply a matter of scale. For example an event causing a "split" affecting significantly macro objects almost entirely decohere, but not perfectly avoiding any kind of hard cutoff. Large systems definitely appear to work differently when you look at them on a large scale, but.. that appearance or classical hallucination is just an emergent property of underlying quantum effects.
Saying the quantum mechanics itself breaks down.. does not fit with the mental picture of reality I've taken from this, reality as entirely locally computable and with higher level effects based entirely on the base level substrate behavior. I'd like you to clarify what you mean by "break down", and preferably how reality would choose where to draw any line between scales where quantum mechanics does and does not break down?
I have read quantum physics has issues with gravity, perhaps that is what you're referring to? If so, I'd be interested in recommended further reading.
from what I've been taking from the sequence quantum physics seems to apply fully at all levels, and the idea of it working differently/not applying is simply a matter of scale.
Nobody's resolved the fundamental problems between QM and general relativity (GR). EY comes close to claiming that MWI will do the trick, but it hasn't yet. At one point he even says that (paraphrasing) reality is a dream, and the dream satisfies special relativity -- at which point one has to ask why the dream doesn't satisfy general relativity.
Large systems definitely appear to work differently when you look at them on a large scale, but.. that appearance or classical hallucination is just an emergent property of underlying quantum effects.
See the previous note. Emergence is just another word for "magic."
Saying the quantum mechanics itself breaks down.. does not fit with the mental picture of reality I've taken from this, reality as entirely locally computable
This is an unfortunate side-effect of EY's tone in the QM sequence.
I'd like you to clarify what you mean by "break down", and preferably how reality would choose where to draw any line between scales where quantum mechanics does and does not break down?
The most evident problem in accepting both QM and SR simultaneously is that they substantially disagree on the value of the vacuum energy density.
What I think you're saying, correct me if I'm wrong, is that there's a few big unknowns as to how QM applies to gravity or on cosmological scales, and because of this the answer to my chain of reasoning is "we just don't know"? That there's major unknowns is entirely reasonable/accurate, but.. I'm struggling to see exactly how the very real and important unknowns apply specifically to my reasoning.
Simply put: Where, in the line of reasoning, do you think the unknown of quantum gravity trips up the logic, and why?
It's seems quite possible that in discovering the answers behind the big unknowns we'll change some underlying assumptions and render my reasoning unworkable. But I don't see where in the line of reasoning not knowing vacuum energy density, or quantum gravity, causes a problem. And given that, it seems like working with the best available theory means applying certain aspects of QM at universal scale is not unreasonable, though we should expect we may need to update models once some big unknowns are resolved.
I think my use of emergence does not fall into the emergence/magic trap, since I am not attempting to explain anything about how large scale systems behave through emergence, my statement is purely that whatever the details of how macro systems work the large scale effects are caused by local physics being consistently applied and only appearing to work differently due to taking a larger view. Even though I used the word "emergence", my sentence can be reworded with my intended meaning if you swap it to "emerges from", which is specifically allowed by that post.
Also, you think my picture of reality as locally computable is "an unfortunate side-effect of EY's tone in the QM sequence"? If that's the case, do you dispute reality as locally computable? I'd be interested in sources which coherently argue for reality being non-locally computable.
What I think you're saying, correct me if I'm wrong, is that there's a few big unknowns as to how QM applies to gravity or on cosmological scales, and because of this the answer to my chain of reasoning is "we just don't know"?
We do know -- QM predicts the wrong vacuum energy density by several orders of magnitude. We've measured this value empirically. Read the Baez link; he explains everything pretty clearly.
my sentence can be reworded with my intended meaning if you swap it to "emerges from", which is specifically allowed by that post.
The critical unanswered question is how "underlying quantum effects" generate the (observed) geometry of space-time. If there were a solution to that question, I'd take no issue with you saying it emerges from those quantum effects -- but we don't know if it's actually the other way around, that is, if it's actually relativistic effects on the microscale that generate quantum phenomena. Or if this is just the wrong question entirely, and that both are caused by a third thing.
That's how you fell into the emergence/magic trap.
EY has to spend a lot of time in the QM sequence insisting that QM is natural and fundamental to get over people's preconceptions of it as unnatural. However, that leads to people taking it as the unique baseline physical theory, which it is not.
Okay, I think I see where you're coming from better now. I have read that link, and at least feel like I conceptually understand some of the problems with applying quantum physics to the large scale. However, I'm still very curious as to exactly how the incompatibility in theories applies to this specific argument, and curious as to whether looking at a purely quantum universe (making the assumption that there is some way to derive relativistic experimental results from QM that we've missed, rather than that QM needs major changes) would give the results I'm describing, or whether I'm misunderstanding something about amplitude or thermodynamics in a heat death.
Hm, how to explain clearly.. It seems like what's being said is QM is at odds with observation (vacuum energy density) and at odds with our other best theory, relativity, (event horizon, thanks for chiming in shminux), so QM is wrong or incomplete in some way. I accept this as a likely conclusion, though I do not understand either theory deeply enough to be able to follow the arguments for inconsistency in full.
However, dismissing a thought experiment about a widely used theory with some possible implications (if I've not missed anything and have understood various things better than I'd guess I have, that chain of reasoning could show a certain interpretation (MW) is incompatible with finite space+infinite time, while a different interpretation (collapse) would not be), due to the underlying theory (QM) being wrong/incomplete for other reasons seems.. limiting. Even if the line of reasoning only holds meaning with the assumption that the universe is fundamentally quantum, local, and macro effects are all explainable in principle by the laws which govern the smallest parts, I'm interested in whether or not it holds.
I'm primarily trying to refine my mental model of how decoherence works with these thoughts, and an answer focused on whether in a quantum universe would, from our current understanding of quantum physics, do as I suppose (that is, in finite space+infinite time, it could never even slightly decohere due to probability 1 arriving at an identical configuration eventually), or have I made some error in my reasoning which can be explained and would allow me to improve my model of decoherence?
To chime in as a person with grad-level training in the subject matter: there is a glaring tension between Quantum Field Theory and General Relativity in the low-energy macroscopic-size limit, which is very bad. How bad? Imagine "proving" that 1=2 in Peano arithmetic, something like that. The issue is the black hole: firewall or horizon? question. GR says that there is nothing locally special about crossing the event horizon (and must be applicable, since GR has been tested in this low-curvature regime), while QFT says that, after a while, the horizon becomes a high-energy incinerator (and must be applicable, since quantum entanglement has been tested in this low-energy regime). The best physics minds on the planet are at a loss to explain the problem. Last time something like that happened in physics, a completely new and unexpected theory eventually resulted. Odds are, we are in for a similar paradigm shift some day, hopefully soon.
I see three distinct issues with the argument you present.
First is line 1 of your reasoning. A finite universe does not entail a finite configuration space. I think the cleanest way to see this is through superposition. If |A> and |B> are two orthogonal states in the configuration space, then so are all states of the form a|A> + b|B>, where a and b are complex numbers with |a|^2 + |b|^2 = 1. There are infinitely many such numbers we can use, so even from just two orthogonal states we can build an infinite configuration space. That said, there's something called Poincare recurrence which is sort of what you want here, except...
Line 4 is in error. Even if you did have a finite configuration space, a non-static point could just evolve in a loop, which need not cover every element of the configuration space. Two distinct points could evolve in loops that never go anywhere near each other.
Finally, even if you could guarantee that two distinct points would each eventually evolve through some common point A, line 6 does not necessarily follow because it is technically possible to have a situation where both evolutions do in fact reach A infinitely many times, but never simultaneously. Admittedly though, it would require fine-tuning to ensure that two initially-distinct states never hit "nearly A" at the same time, which might be enough.
This is an inclusive guide to the series of posts on quantum mechanics that began on April 9th, 2008, including the digressions into related topics (such as the difference between Science and Bayesianism) and some of the preliminary reading.
You may also be interested in one of the less inclusive post guides, such as:
My current plan calls for the quantum physics series to eventually be turned into one or more e-books.
Preliminaries:
Basic Quantum Mechanics:
Many Worlds:
(At this point in the sequence, most of the mathematical background has been built up, and we are ready to evaluate interpretations of quantum mechanics.)
Timeless Physics:
(Now we depart from what is nailed down in standard physics, and enter into more speculative realms - particularly Julian Barbour's Machian timeless physics.)
Rationality and Science:
(Okay, so it was many-worlds all along and collapse theories are silly. Did first-half-of-20th-century physicists really screw up that badly? How did they go wrong? Why haven't modern physicists unanimously endorsed many-worlds, if the issue is that clear-cut? What lessons can we learn from this whole debacle?)