It seems that quantum computers are required for simulating quantum mechanics in sub-exponential time, though.
When discussing asymptotic algorithmic complexity, you should specify the varying parameter of problem complexity.
The usual default parameter is number of bits it takes to write down the problem. It could also be number of particles. Either one works in this case.
What quantum algorithm for simulating quantum mechanics takes sub-exponential time with respect to the number of particles?
I didn’t have a particular algorithm in mind when I said that, but since you ask I went and found this one.
Current theme: default
Less Wrong (text)
Less Wrong (link)
Arrow keys: Next/previous image
Escape or click: Hide zoomed image
Space bar: Reset image size & position
Scroll to zoom in/out
(When zoomed in, drag to pan; double-click to close)
Keys shown in yellow (e.g., ]) are accesskeys, and require a browser-specific modifier key (or keys).
]
Keys shown in grey (e.g., ?) do not require any modifier keys.
?
Esc
h
f
a
m
v
c
r
q
t
u
o
,
.
/
s
n
e
;
Enter
[
\
k
i
l
=
-
0
′
1
2
3
4
5
6
7
8
9
→
↓
←
↑
Space
x
z
`
g
It seems that quantum computers are required for simulating quantum mechanics in sub-exponential time, though.
When discussing asymptotic algorithmic complexity, you should specify the varying parameter of problem complexity.
The usual default parameter is number of bits it takes to write down the problem. It could also be number of particles. Either one works in this case.
What quantum algorithm for simulating quantum mechanics takes sub-exponential time with respect to the number of particles?
I didn’t have a particular algorithm in mind when I said that, but since you ask I went and found this one.