[extropy-chat] D-Wave premiere of 16 qubit processor
scerir
scerir at libero.it
Wed Feb 14 07:34:29 UTC 2007
> I'm assuming S.A. is Scott Aaronson
> but that doesn't ring any bells in my
> head. Is he a QC wizz kid?
> R.
If QC means quantum complexity
I would say 'yes'. If QC means quantum
computer (hardware) I would say
'no'.
Limits on Efficient Computation in the Physical World
Scott Aaronson
http://www.arxiv.org/abs/quant-ph/0412143
More than a speculative technology, quantum computing seems to challenge
our most basic intuitions about how the physical world should behave. In
this thesis I show that, while some intuitions from classical computer
science must be jettisoned in the light of modern physics, many others
emerge nearly unscathed; and I use powerful tools from computational
complexity theory to help determine which are which.
NP-complete Problems and Physical Reality
Scott Aaronson
http://www.arxiv.org/abs/quant-ph/0502072
Can NP-complete problems be solved efficiently in the physical universe? I
survey proposals including soap bubbles, protein folding, quantum computing,
quantum advice, quantum adiabatic algorithms, quantum-mechanical
nonlinearities, hidden variables, relativistic time dilation, analog
computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike
curves, and "anthropic computing." The section on soap bubbles even includes
some "experimental" results. While I do not believe that any of the
proposals will let us solve NP-complete problems efficiently, I argue that
by studying them, we can learn something not only about computation but also
about physics.
More information about the extropy-chat
mailing list