Transcript ppt
011011010101001001010100010010110001001010100100100110010010
010010100100101100101010010011001001011011110110001011101011
What Do You Mean
101000101110010011000101100100101001001110010010011001001001
100111001010010100011010101001001010100100101010011001001001
“Simulating a Quantum Computation?”
010010100100101100101010010011001001011011110110101110101001
101000101110010011000101100100101001001110010010011001001001
100111001010001010101010101001001010010010110000010010011010
010010100100101100101010010011001001011011110101010101110101
101000101110010011000101100100101001001110010010011001001001
100111001010001010101001001010110110101011000101001001001110
010010100100101100101010010011001001011011110110000101110101
101000101110010011000101100100101001001110010010011001001001
100111001010001010101010100111101101101010100100110010010010
010010100100101100101010010011001001011011110110101011101011
101000101110010011000101100110110101000100100101100100100101
010010100100101100101010010011001001011011100101010111010111
101000101110010011000101100100101001001110010010011001001001
100111001010001010101010100111000101 01001001111100100100101
October 2002
100111001010001010101010100111001010100100100010010011101101
David Poulin
IQC, University of Waterloo
&
Perimeter Institute
A second example of what Chris called
“a bad question”.
In condensed matter physics, it is often quite useful to
introduce the notion of “quasi-particles”. These are
excitations which behave almost like free particles but
have extra weird features.
For example, the mass of the quasi-particle may depend
on the direction of its motion: a mass tensor.
Yet, people don’t organize meetings on the interpretation
of quasi-particles!
David Poulin, IQC University of Waterloo & PI
It is clear at this time that quantum mechanics is not
the final theory.
In whatever turns out to be the final theory (string theory,
quantum loop gravity, etc.), quantum mechanics will only be
a good approximation.
It is also possible that some of the weirdness disappears.
But we are here having this meeting!
David Poulin, IQC University of Waterloo & PI
What Do You Mean
“Simulating a Quantum Computation?”
How is this simulation business related to
foundation of QM?
“A journey from ontic to epistemic ... with consequences”
Does this have consequences on the way we think
about simulation?
David Poulin, IQC University of Waterloo & PI
Outline
QS
QC
CC
What is known
• Some QSs can be simulated efficiently on a QC.
• “Simulating the dynamics” of some QS is as hard
as factoring.
• Entanglement is necessary for Q-computational
speed-up with pure states.
• Finding the ground state of a QS can be NP complete.
• etc.
David Poulin, IQC University of Waterloo & PI
Stuff about QS we usually compute with
CC “simulations” (at an exponential cost).
• Ground state energy
• Properties of the thermal/ground state (symmetries)
• Propagators
• Degeneracy of energy levels
• Transport properties
• Properties of spectral functions
• Properties of cross section ()
• Partition function
• etc.
David Poulin, IQC University of Waterloo & PI
The real thing should be at least as good
as the simulated one!
How much of the stuff on the previous slide can we
measure from the QS itself...
... or a polynomial number of copies of it?
Does there exist physical quantities extractable from
poly copies of a QS which requires exponential CC?
“The strongest argument indicating that the simulation
of QS is a hard problem is Gauss’ failure at finding an
efficient algorithm for factoring.”
---Gilles (maybe in a dream...)
David Poulin, IQC University of Waterloo & PI
“So I know that quantum mechanics seems to involve
probability --- and I therefore want to talk about
simulating probability.”
---Feynman
There are two ways of addressing this problem:
1. Simulate the “wave packet dynamics” (x,t) like
one would do with water waves.
1 12 . Simulating “the factual probabilities”.
2. Use a probabilistic CC which “reproduces some
statistical properties of the system”.
David Poulin, IQC University of Waterloo & PI
“One method for classically simulating a quantum computation
is to directly compute the state at each step from the
sequence of unitary operations prescribed in the quantum
algorithm.”
--- Jozsa & Linden
p-blockness:
1
2 k
On at most p qubits
p2
n
Writing the wave function requires k2 2 complex
p
amplitudes.
p2
Every step of the computation requires at most 24p
complex multiplications... must figure out what constitute
the new blocs.
Entanglement is only related to simulatability through the
way we chose to represent the wave function.
David Poulin, IQC University of Waterloo & PI
If we insist on computing an exponential amount of extra
unphysical information (), the exponential overhead is
inevitable.
Slightly weaker notion of “simulating probabilities”:
Reproduce the probabilities of a fixed final measurement.
Inputs: I = {Gi}
Outputs: O = {Hj}
Gi
QM
Hj
pij
Reproduce pij for all choice of {Hj}
“Unperformed experiments have no results”
---Peres
David Poulin, IQC University of Waterloo & PI
Simulate physics,
not counterfactual experiments
p-blockness p-blockability!
F = {I, Q1 , Q2 , ..., QL , O}
L is the circuit’s depth
Qk
= A
(k)
j
a(jk) a(jk)
p-block states
If F form a family of consistent histories, then the
measurements Qk can be carried out --- collapsing the
state to a p-block state --- without changing the
factual (physically meaningful) probabilities pij .
David Poulin, IQC University of Waterloo & PI
Probabilistic simulation
If it is possible to simulate the “wave packet’s dynamics”
or the “factual probabilities” it is possible to “statistically
reproduce the behavior of the QS”.
... but it seams otherwise impossible!
Are we being fair with CCs?
Computation: Problems which require exponential resources
are intractable.
Physics: Properties which require exponential resources to
be estimated are practically not measurable.
David Poulin, IQC University of Waterloo & PI
But Avogadro’s number is so large!
It takes a while before the exponential kicks in.
Ex. Molecule: N = 50 hydrogen-like 2-levels atoms.
Sample: m = 1g.
Number of states = 250 << Number of molecules = 1024/50
(7 orders of magnitude!)
If N = 100, then m has to be > 1Tonne!!!
Reproducing the statistics is not a fair requirement...
... what about some coarse grained version of it?
Coarse graining leads to consistency... which leads to
classical simulatability!
David Poulin, IQC University of Waterloo & PI
Beyond simulating!
When asking a CC to simulate a QS, we should only ask
about things we can actually measure on that system.
Should we expect more from a QC?
... it’s not completely crazy.
Ex. Is the ground state of this QS degenerated?
David Poulin, IQC University of Waterloo & PI