[MUSIC PLAYING]
BORIS ALTSHULER: OK,
please be seated.
I'm Boris Altshuler,
from Colombia University,
and I'm supposed to
chair this session.
And the first speaker
will be Helmut Katzgraber,
from Texas A&M, and
it's about quantum
versus classical optimization.
HELMUT KATZGRABER: Thank you.
It's a pleasure to be here.
What I'd like to do
today is give you
a status update on quantum
versus classical optimization.
And because right now we have
the [INAUDIBLE] de las Americas
and the Euro Cup, I
figured I'll keep tabs
on how things are going
with a little scoreboard
throughout my presentation.
Now, the results that
I will be showing you--
and this is a slide that
I always like to show--
are really at a crossroads
from statistical physics,
quantum information theory,
and high performance computing.
And you will see today that
statistical physics is actually
quite important when
you want to study
quantum computing-related
problems,
and especially if you want
to optimize complex systems.
Now, there's a lot
of questions we
would like to have answers to.
For example, can
quantum annealers
be faster than
classical computers?
Do applications exist where
quantum annealing excels?
We've so far studied mostly
random spin glass problems.
And so far, results have
been rather inconclusive.
And then, of course,
what are the limitations
of transverse field
quantum annealing?
Are there things
that we know ahead
of time will be very
hard to overcome
if you use this type of
optimization technique?
And so what we've been doing
is we've been developing
state-of-the-art
classical solvers,
in an attempt to raise the
bar for a quantum annealers,
but at the same time, to also
create benchmark problems
for quantum annealers.
We also refined, a little
bit, the definition
of quantum speed-up.
And I'll get to this
later in this talk,
just so that we can do a
slightly fairer comparison.
And one of the things that,
really, we are doing mostly
is using statistical physics
to analyze benchmark problems.
And in particular,
we're trying to predict
if a problem is well-suited
for quantum annealing or not.
Now, this sounds
almost crazy that we're
trying to predict
something, but I hopefully
will be able to show you an
example where it actually
seems to work.
This was done with a lot of
people, [INAUDIBLE], Sergei,
and Hartmut at Google, as
well as [INAUDIBLE] at D-Wave,
Alejandro and Salvatore
[INAUDIBLE] at NASA,
[INAUDIBLE] in
Leipzig and a bunch
of guys that work with me.
As you see, it's
usually hot in Texas,
so this is how we
dress most of the year.
Now, why do we actually need
new computing technologies?
There was a beautiful editorial
in "Nature" earlier this year,
entitled Beyond Moore's Law.
And I think we all
know Moore's Law.
I think that's
something we can assume.
It basically says that the
transistor count will double,
roughly every two years.
And this trend has been going
on for a very, very long time.
You can just send a
straight line through that,
and you see it's still going.
This is great news.
But there is a
piece of information
that is often swept
under the rug.
And that piece of information
is that the clock speed
has stalled since about a
decade and a half or so.
So if you look, now, at the
clock speed of the processors,
it's basically a constant,
meaning that you're
reaching fabrication limits.
You can't go much faster.
So the only way to pack
more transistors into a chip
is just to add more cores.
The other thing that a lot
of people don't think about
is that if we ever want to
build an exaflop machine,
we will need gigawatt power.
And so it's a little bit
like electricity for a town
or running a computer,
which is going to be a very
difficult issue to tackle.
And so this has led
to many investments--
Google, IBM, Microsoft,
and many others.
And of course, the big question
is, is quantum the technology
of the future?
Now, we do have now
commercially-available quantum
devices.
There's all kinds of things.
However, the current
state of the art
when it comes to computing
are special-purpose computers.
And I think we all
know exactly which
machine I'm talking about.
It is the big black box
from D-Wave Systems,
Inc. As you know, it's a
special-purpose quantum
annealer, so there's
only one thing it can do.
It can optimize problems
mappable in its topology.
And there have been
sold a few of them.
And I think that this is still a
groundbreaking result. Building
such a device with so
many qubits is not easy.
I've heard it will come out with
a 2,000-qubit chip in the near
future.
And so this is, in my opinion,
a huge technological feat.
Now, what can it do?
Well, it can minimize
problems in qubal format.
In other words, if you write
it as a quadratic form,
something like an Ising
model, once you can encode it
onto the fixed
topology of the chip--
known as Chimera, and within
the machine constraints--
for example, precision.
And if you want to
see some of the ideas
that we have been developing
about how to improve Chimera
itself, I encourage you to look
at the poster by Mark Novotny
later today.
Now, one thing that I want
to talk about very briefly
is how the machine optimizes.
And this is important,
because what I will do
is, I will do an analysis of
the performance of the machine.
And for this, I should
remind you how it works.
And actually, the way it
optimizes is sequentially.
Now, you might wonder, why
is there a big axe on here?
And the reason is that the
way that D-Wave optimizes
was developed about 7,000 years
ago, in the Neolithic era.
The Germans, of
course, discovered
that if you anneal a piece of
metal, it's more malleable.
You can make a better axe,
and you can more efficiently
bash each other's heads in.
Now, we don't want
to do this here.
But basically, we want to
just use the same approach
numerically, and this is
known as simulated annealing.
You have a Hamiltonian
or a cost function.
You stochastically sample it.
Once the system is
thermalized, you cool it.
And you do this according
to some annealing schedule--
for example, here,
a linear schedule.
And then you hope
to find the optimum.
In fact, if you anneal
infinitely slow,
there is a theorem
that proves that you
should find the optimum.
However, that is, of
course, not very efficient.
Now, when you have a problem
with a rough energy landscape--
say like a spin glass or a
complex optimization problem--
then simulated annealing
has the potential
of getting stuck in any of
those metal stable states.
And to overcome
this, what people
have done in previous
studies is very simple.
You just do multiple restarts.
In other words, you rain
down on the landscape
until you hit the jackpot.
This allows you
to do statistics,
and then basically figure out
if you found the optimum or not,
at least with a
given probability.
Now, the D-Wave device
does basically the same,
using quantum annealing.
This is why we're all
here, except that instead
of quenching thermal
fluctuations, what you actually
do is, you just quench
quantum fluctuations.
It's basically the same thing.
Now, the nice thing
is that you're not
limited to a local search.
And potentially, if
barriers are thin enough,
your system might be able to
tunnel through the barrier
and find the optimum.
And the way it's
done in D-Wave 2X
is transversely of quantum
annealing, where you just
apply a transverse field.
It doesn't commute.
And there was a
beautiful animation
earlier by [INAUDIBLE]
that showed this.
And then, basically, it reduces
quantum fluctuations [? d ?],
according to some given
annealing protocol.
Now, there have been many, many
attempts to see if this machine
can do something that
classical computers cannot do.
And I think that the
most recent results
that are most
promising, and that
were presented in detail
earlier by [INAUDIBLE],
are the recent results by the
Google/NASA team, where they
showed that there can be a
very large speed-up for very
carefully tailored problems.
I'll show you again the
results, and I'll just
focus on the 50
percentile for simplicity.
And of course, the result
is simple to summarize.
If you compare, first of
all, just absolute numbers,
this here is around
10 to the 13.
This is about 10 to the 5.
So you have roughly a
10 to the 8 speed-up
for the largest system
size of 945 or so qubits.
However, this offset is not
the most important thing.
The most important
thing is actually
the slope of this curve,
because asymptotically, this
is what is going to
determine who wins the race.
And you see very nicely that the
simulated thermal annealing has
a much steeper slope
than either quantum Monte
Carlo or the D-Wave device.
So this is, in my
opinion, really
the first strong signature that
quantum approaches scale better
than classical approaches.
And what this means
is 1, 0 for quantum.
Now, let me say
a little bit more
about Google's weak-strong
cluster instances.
As I said, [INAUDIBLE]
mentioned this already before.
I just want to look at it from
the spin glass point of view.
And that is, you have what
they call weak-strong clusters.
Basically, they're all
ferromagnetically coupled.
You have one field that is
stronger than the other,
and this cluster here
is just basically
kind of like the Siamese
twin to this one.
And this one over here,
then, connects to the rest
of the system in the network.
Now, the important
thing is to zoom out
as far as you can, and just
look at this rectangle as one
object.
And if you look at
it, what you get
is basically a spin glass
with positive and negative
interactions on some
kind of network topology.
OK?
The only job that these
weak-strong clusters have
is to basically fool
a thermal annealer
into a meta-stable state.
Quantum annealer,
however, might be
able to overcome this problem.
Now, there are some
potential issues.
If you compare, now,
quantum annealing
to simulated annealing,
well, simulated annealing
is known to be an extremely
poor optimization method.
There is far more state of
the art algorithms out there.
And don't ask me for a
reference-- this is just
from me doing this
for the last 10,
15 years-- some
Monte Carlo methods
are extremely inefficient
the second you
turn on strong uniform fields.
And the reason is that
flipping individual spins
becomes a very hard task.
So we figured, let's
do a fair comparison,
and use what is
known as population
annealing Monte Carlo instead
of simulated annealing.
Some computer scientists
here might know it
as particle swarm method.
And the idea here
is that we want
to use something
that is sequential.
In other words, you have
a control parameter--
either quantum fluctuations
or temperature--
that you tune from a
large to a small value.
And at the same time, we know
that population annealing
is pretty much unaffected
by external fields, which
is phenomenal if you want
to simulate spin glasses.
So how does this population
annealing work, in a nutshell?
Well, let me remind
you, simulated annealing
usually gets stuck.
You run it in repetition
mode, and what you then get,
basically, is the optimum.
In population annealing,
you do the same,
except that you run all
these runs in parallel,
at the same time.
And at each
temperature step, you
cull the population, according
to the Boltzmann distribution.
What this means is, if
some of these instances
are stuck in a
meta-stable state,
they get killed and replaced
by fitter instances that
actually are getting
to the true optimum.
And so what this means is that
basically, your [INAUDIBLE]
were shuffled, and then you
get to the optimum much better.
So again, the way it
works is, you just perform
capital R simulated
annealing runs in parallel.
OK?
Typically, R is, say, 10
to the 5, 10 to the 6.
It's a very large number.
And then at each
temperature step,
you do a re-sampling
of these guys.
You kill off some, and you
repopulate with others.
So think of it as a
little bit of a mixture
of a genetic algorithm
with simulated annealing.
And then you do a
handful of Monte Carlo
sweeps, just to make sure
that Boltzmann is happy.
Now, if you simulate spin
glasses at a [? finer ?]
temperature, you will find
that population annealing is
as efficient as a
state-of-the-art parallel
tempering Monte Carlo.
It's an extremely good method.
The other nice thing is
that the numerical effort
is the exact same as
simulated annealing.
The re-sampling step is
really very small overhead.
So it's fair to compare
population annealing
to simulated annealing.
And you can just switch
off, on this side,
the re-sampling step.
And then you just have simulated
annealing running parallel.
And it out-performs simulated
annealing in repetition mode.
Now, I can demonstrate
this to you.
What you see here is data
for a three-dimensional spin
glass with 512 sides
and 1,000 sides--
so roughly the size of the
D-Wave and the D-Wave 2X.
OK?
And on the horizontal axis,
you have the population size,
or the number of times we
ran simulated annealing,
in log 10 base.
And this is the percentage
of solved problems.
And you see that, if we run
a population of 10 to the 5,
or we do the simulated
annealing 10 to the 5
times on these problems,
then population annealing
finds all solutions.
Simulated annealing only
finds about a third.
If we increase the system
size by a factor of 2,
you see that simulated annealing
wasn't able to solve anything
at this size problem, whereas
population annealing clearly
does solve, still, all problems.
So it is a much more powerful
method, and it is sequential.
So let's toss this
into the whole picture.
And I just highlighted the
line for population annealing.
These are, again, the
results by Google.
And you see very nicely
that the slope, of course,
is less steep than
simulated annealing,
but still far from
the scaling we got
with quantum Monte
Carlo or the D-Wave 2X.
So one could see this
as additional evidence
of some quantum advantage--
in other words, 2, 0.
Now, population annealing
is just one method.
What if we now opened
a drawer and pull out
all possible methods that
we can think of, basically
a long laundry list of
algorithms, and see how
did they compare
against all of those?
And so before I show you
the list of algorithms,
I'd like to just
very briefly refine
the notion of quantum speed-up,
such that the comparison later
is a little bit more apparent.
Until now, in the paper
by [INAUDIBLE] et al.
In 2014, it was introduced
that we have provable quantum
speed-up.
In other words, you
can prove that there
is no classic
algorithm that will do
better-- say, Grover's search.
Then with strong
quantum speed-up,
where we compare to the
best-known classical
algorithms-- say,
Shor's algorithm.
You have potential
quantum speed-up,
where you compare it
to a set of algorithms.
And these, of course,
can be short-lived,
until somebody finds
a better method.
And then there was what
is called limited quantum
speed-up, where we
just look at speed-up
over a classical counterpart.
And so we decided to take
limited quantum speed-up
and just refine it
ever so slightly.
We first introduced limited
tailored quantum speed-up.
What does it mean?
It means that you know the
structure of the problem.
So you're not receiving a
problem which has no structure.
You can look at it and say, ha.
If I use this trick, I
can abuse the structure
and find the optimum faster.
Prime example, the
[INAUDIBLE] algorithm,
which basically exploits the
tree structure of Chimera.
Then we have limited
non-tailored quantum speed-up,
and I would call this
the gold standard.
These are generic algorithms.
They assume nothing
about the system,
but they are the fastest
that you can find.
And then there is limited
sequential quantum speed-up,
which basically is
a sequential method
like population annealing,
simulated annealing, quantum
annealing.
And the motivation
for us to do this
was to basically
perform a better
description of the benchmarks.
So we went through this
long list of algorithms.
We looked at tailored ones--
for example, the [INAUDIBLE]
algorithm, a super-spin
approximation
that [INAUDIBLE], who will
talk after me, introduced,
which is basically
something rather brutal.
You take each of the
weak-strong clusters,
and you call it one spin.
In other words, you just take
this and replace it by that.
And instead of solving a
problem with 900 and something
variables, you end
up solving a problem
with maybe 12 variables.
Obviously, you'll find
the solution instantly.
OK?
And then there is the
hybrid cluster method
by Salvatore
[INAUDIBLE], et cetera.
Then you have the
non-tailored algorithms--
for example,
population annealing,
which basically is sequential,
but is not tailored.
Parallel tempering, with
[INAUDIBLE] cluster moves
is the solver that we use.
And then we use
some other things
like replica Monte Carlo.
And then, of course, we
compare to simulated annealing
and quantum Monte Carlo.
Let me show you the results.
And I ask you to not
try to discern what
is what in this spaghetti plot.
OK?
These are the simulations
with all these algorithms,
and I just
highlighted two lines.
One is, again, the D-Wave
result on the machine,
and this is quantum Monte Carlo.
And you see that these here are
simulated annealing, population
annealing.
But all the other ones
are pretty much comparable
to the performance
of the D-Wave device.
Now, we decided to do
an asymptotic scaling--
in other words, exclude
the small system sizes.
The reason for
this being that it
seems that there is a double
scaling in the D-Wave,
due to noise.
[INAUDIBLE] will give a
talk this afternoon at 3:30,
actually addressing
this point in detail
with his beautiful,
simple model that he
developed to address this.
Now, because we're doing
an asymptotic scaling,
again, all that
matters are the slopes.
We're going to try
to fit an exponential
with some coefficient b.
And we also tried to do
this with a polynomial
[? pre-factor ?]
to normalize it.
And all that matters
is this exponent b,
because it will tell
you what this slope is,
of these individual lines.
And what you see here
are these exponents b.
Now, let me walk you through it.
There is red blobs
and blue blobs.
Forget about the blue blobs.
This is where we assume there
is a polynomial in front.
The red blobs are this
coefficient b here,
for the different algorithms--
simulated annealing, population
annealing, D-Wave 2, quantum
Monte Carlo, hybrid cluster,
replica Monte Carlo, parallel
tempering, HFS, super-spin.
I'm done.
And the important thing now
is, I should color those in.
And of course, a
smaller value of b
means a better scaling-- in
other words, a faster method.
And you can see very
nicely, I drew a line here
through the D-Wave results
that, within the category
of sequential
algorithms, clearly
quantum Monte Carlo
and D-Wave-- sorry,
I drew a line through
quantum Monte Carlo.
Quantum Monte Carlo and D-Wave
outperform population annealing
and simulated annealing.
However, when you even use
non-tailored algorithms--
in other words, generic
methods that we developed-- you
see very nicely that
they perform better.
So in other words, I would
say that what we have here
is sequential quantum speed-up.
And so what this
means is 1 to 2.
Now, the next important
question is, does the scaling
persist for large system sizes?
And this is going to be
a little bit technical.
OK?
This is where the
statistical physicist in me
comes into the picture.
And it starts with
something that Hartmut
mentioned this morning--
this p of q thing.
And so what we do is, we need
to find an order parameter
for a spin glass.
And the natural order
parameter for a spin glass
is the overlap between
two copies of the system.
Why is that?
If you look at a ferromagnet,
and you lower the temperature
close to 0, then
what you will see
is that either all spins are
up or all spins are down.
So you just look at the
picture and know right away,
the system is ordered.
In a spin glass, the spins
will freeze randomly in space.
And so if you just
look at a snapshot,
you will not be able to
tell if it's in the ordered
or disordered phase.
So what you do is, you
simulate two copies
of the system with
the same disorder.
And then you compare,
spin by spin.
And we call this quantity
the spin overlap q.
And you see that, if these
two copies agree, then
for low temperatures,
q should go
to 1, [? model of this ?]
normalization.
And for high temperatures,
it goes to 0.
So it's a natural order
parameter for the problem.
Now, you show-- you can now
measure the distribution
of this quantity.
And again, I'd like to remind
you of the ferromagnet.
If you look at a ferromagnet
at very low temperatures,
and you look at the distribution
of the magnetization,
either the spins will
be all up or all down.
In other words, you
will get two delta peaks
at roughly plus, minus 1.
OK?
But if you now increase
the temperature,
magnetization will
average out to 0.
And due to the
central limit theorem,
you will just get a
Gaussian centered around 0.
In a spin glass, you
have the same behavior
at high temperatures.
However, at very
low temperatures,
you can have dominant
states that form,
and form different basins
in the energy landscape.
In other words,
instead of just having
one peak at plus, minus
1, you can actually
have a multitude of peaks.
And the position of
these peaks-- here
you have three examples,
red, black, and blue--
strongly depends on the
disorder that you chose
for that particular problem.
And so we've been staring
at these functions
for a long time.
And if you have no linear
terms in the field,
it's spin reversal
symmetric, so it's
enough to just look at
half of the distribution.
And you can show that, if
there are many features,
then likely you will have
something that corresponds
to a wide barrier,
and I don't have time
to go into all the
details of this.
And when you see thin,
sharp features, then likely
you will have thin
barriers that show
the potential for tunneling.
And I'd like to also mention
that if you typically
have a single wide
feature, then it could be
a problem without any features.
What do I mean by this?
Basically, something like
a ferromagnet-- something
parabolic and simple,
modulo some little bumps.
Now, I swept a lot of
details under the rug.
But we did very
careful studies here,
in this first paper with
[INAUDIBLE] a few years back.
And you can very nicely show
that this complexity of this
function also correlates very
well with the auto-correlation
times of state-of-the-art
algorithms like parallel
tempering.
So we went back now and
measured this quantity
for the Google instances.
And what we found is, typically,
two types of problems--
one that looks like this,
a single, sharp needle
peak that is away from 1.
And the other one basically
looks like a tooth,
with maybe two or three peaks
that are really close together.
And so what this means is-- and
this is based on more than just
looking at pictures--
that whenever
you have a very thin peak,
you have either a thin or no
dominant barrier.
And typically, the
Hamming distance for that
is about less than [? 16s ?].
And we know that D-Wave will
have some tunneling advantage,
if the barrier is thin enough.
However, when you have
double or triple features
like this that
overlap, the barriers
are too thick to
see any tunneling.
And so what we can
now do is, we can
plot the fraction of
problems that have
a thin versus a thick barrier.
And what you see very nicely
is that with increasing system
size, the fraction of
problems with wide barriers
becomes dominating.
In other words, the bigger
you make the system,
the more the spin glass backbone
will dominate, as [INAUDIBLE]
said in the morning,
and you will eventually
lose your scaling, and
the quantum advantage
will vanish for large
N. So sadly, we're tied.
Good.
Now, I showed you these results.
And now the question,
of course, is,
can we use this
for something else?
And what I'll show you
now are very new results
that we have just produced.
And I'll just show you one
case study, because [INAUDIBLE]
will show you a whole palette
of problems that we've analyzed.
And this is weighted
partial MAX-SAT.
It's just a typical constraint
satisfaction problem.
MAX-SAT is the
problem where you want
to determine the maximum number
of clauses which satisfies
a given Boolean formula.
And weighted partial means
that you satisfy all clauses
and maximize the sum of the
weights of the soft clauses.
And you can encode this into
a [INAUDIBLE] Hamiltonian,
and then basically
solve this with whatever
solver you want to solve.
Now, what does the p of q look
like for this very particular
problem?
Well, you get something
that has many spikes.
And when you have
many, many thin spikes,
it's suggestive that if there
is some kind of tunneling,
you should be able to
tunnel through these spikes.
And so what we did is,
we sent these problems
to Sergei [INAUDIBLE].
He ran them using simulated
annealing and quantum Monte
Carlo.
And what you will
see in the next slide
is basically the
speed-up of quantum
annealing over
simulated annealing
measure in Monte Carlo sweeps.
And what you see very nicely
is that, first of all,
this is a logarithmic scale.
And for about 90%
of the problems,
you needed about a factor of
1,000 less Monte Carlo sweeps
in quantum Monte Carlo than
in classical Monte Carlo.
In other words, we
were able to predict
that this type of problem would
be perfectly suited to run
on a quantum-type architecture.
In the meantime, we've
tested, of course,
everything we can get our
hands on-- random spin glasses,
well, they're random.
But if you mine the data
according to the features,
again, you can show speed-up.
Same thing for vertex covers, 3
SAT, 4 SAT, graph partitioning,
circuit fault diagnosis,
et cetera, et cetera.
So in other words, we
have now an opportunity
to basically go in and
decide, ahead of time,
if a problem might benefit
of quantum speed-up.
And this is really
great, because it comes
back to what Hartmut said.
You can do [? runner ?]
test of the problem--
and of course, there is still
a lot to be learned here--
and then decide if you farm
it to a silicon-type machine
or to a quantum device.
And again, if you want to learn
more about all these things
here, just stick around for
the talk right after mine.
So I would say, given this
information, it's a 2, 3.
Now, the last thing I want to
address is something very new
that we did, and this is
what we call fair sampling.
And so fair sampling,
everybody gets a beer.
Basically, it's
very simply defined
as the ability of an algorithm
to find all solutions
to some degenerate problem, with
roughly the same probability.
So if you run your
algorithm and you
know the problem has
17 different solutions,
and you run this 10,000 times,
and you make a histogram,
you want to make sure that
these 17 bins are roughly
filled the same, modulo
Poissonian fluctuations.
That means your algorithm
can find all solutions
to a problem, and
not just the minimum.
And this is very important,
because sometimes solutions
are more important
than the minimum.
Think, for example,
of SAT filters,
where you need many
uncorrelated solutions.
[? Hash SAT ?], or if you want
to do contingency testing,
or for example, if your problem
has some other constraints that
are not part of the
optimization procedure--
think solving a traveling
salesman problem,
but then it happens
that your trucks are
parked in a place where
you are not right now.
So you would like to have a
better solution that matches
this additional constraint.
So the gold standard
for any optimizer
is, find the ground
state fast and reliable.
A much stronger test is to find
all minimizing configurations
[INAUDIBLE].
And back in 2008, 2009
I did a very nice study
with [INAUDIBLE] and [INAUDIBLE]
where we looked at, first,
at a toy model of five spins.
Here, dashed line means
anti-ferromagnetic, solid lines
ferromagnetic.
And basically, what
we found is that this
has three degenerate solutions,
modulo spin reversal symmetry.
And when you now look
at the probability
of finding these three
solutions as a function
of annealing time, if you have
a transverse-field quantum
annealer, what you find
is that solutions 2 and 3,
you get 50% of the time,
but solution number 1
is exponentially suppressed.
Similarly, if you
now say, well, let's
use a more complex
driving Hamiltonian,
like the one shown over here,
suddenly this weird behavior
goes away, and you find
all three solutions
with 1/3 probability,
which suggested
that transverse-field quantum
annealing might be biased.
So we thought, let's do
a more thorough test,
and use a model that has
a really nasty collection
of solutions.
And that's the so-called
fully-frustrated Ising model.
It's just an Ising model,
but every second row here
is anti-ferromagnetic.
And you see now that every
[INAUDIBLE], this model
has no disorder, but every
[INAUDIBLE] is frustrated.
So a system with
36 spins already
has about 45,000 different
degenerate ground states.
And when we ran this again,
using quantum annealing,
you see very nicely that
some states are exponentially
suppressed.
OK?
However, if you were to do
this with classical methods,
this is not the case.
So what about quantum annealers?
Well, we ran experiments
on the D-Wave,
and we chose our disorder to
be in 5, 6, 7, plus, minus.
And we modeled those
interactions in a way
that there was no floppy spins,
and we can very carefully
control the degeneracy to
be 3 times 2 to the k-- so
6, 12, 24, 48, etc.
OK?
And then, for fixed c and k,
we studied the distribution
of ranked ground states.
Now, I don't want to bother
you with the details of showing
every single plot.
I can just show you one
characteristic plot here.
These are experiments run on the
D-Wave for a different number
of ground states.
And you see very nicely that,
again, the data are biased.
In other words, there is
an exponential suppression
of certain states.
And this, of course,
is very bad news,
because this means that
transverse field quantum
annealing is an
exponentially biased sampler.
And this also
suggests that we need
to think beyond
transverse field.
So this leads,
basically, to a tie.
But a tie in quantum
mechanics is nothing else
than a coherent superposition.
So we're basically
stuck with this.
And with this, I'd like to
thank you for your attention.
[APPLAUSE]
BORIS ALTSHULER:
Thank you very much.
Questions, comments?
AUDIENCE: Should I
come up to the front?
BORIS ALTSHULER: We
have microphones now,
so if somebody doesn't want
to come all the way up,
Austin and I-- we will
hand you a microphone.
AUDIENCE: Thank you.
I can see that this
method would work
for multi-spin interactions,
for multi-spin terms
in the Hamiltonian.
And I wonder if you have
a feel for how much harder
the calculations
get, as you add more
and more multi-qubit terms.
HELMUT KATZGRABER:
So I don't have
a feel as to how
much harder they get,
but they do get harder.
AUDIENCE: OK.
You don't know how much, but--
HELMUT KATZGRABER: No.
I can't quantify it
at the moment, no.
BORIS ALTSHULER: More questions?
OK.
Let me come around.
AUDIENCE: OK, thank you.
So you're finding that the
distribution of solutions
is not uniform, when
you use the transverse
[INAUDIBLE] algorithm.
But I think-- what would
happen if you varied the paths?
I would bet that if you had
randomly sampled your paths,
you would flatten out
that distribution.
HELMUT KATZGRABER: What I can
tell you is that-- so we have--
obviously, in the D-Wave,
you cannot really do that.
And in some ways, my
point was basically,
we need to think about
more clever things--
better driving Hamiltonians,
the influence of thermal noise,
say, with this quantum parallel
tempering, better paths, etc.
But these results,
I should mention,
were done with many gauges.
So despite applying
gauges to the system,
the bias was still there.
So my guess is that
unless you happen
to find the optimal path,
which is a measure of 0,
it's not going to
do much for you.
AUDIENCE: [INAUDIBLE].
HELMUT KATZGRABER:
Yeah, sure-- but I
don't think that it
would help too much.
AUDIENCE: OK.
AUDIENCE: This idea that
your gauge transfer machine
is a classical operation,
whereas changing paths is
a quantum operation-- takes
you to different corners
of the potential.
And also, the
second comment is I
would encourage people to
listen to D-Wave talks,
because we can do
multiple paths.
And we have seen the effect
of that in optimization.
I encourage people
to listen to those.
HELMUT KATZGRABER: Oh, cool.
That is news to me, so
I'll look forward to that.
AUDIENCE: So I know
with the D-Wave machine,
that there's some fuzziness
in each individual coupling,
from systematic random
variations, et cetera.
Do you know how much that
affects the fair sampling?
HELMUT KATZGRABER:
Well, if anything,
I would expect it to help.
You see?
Because if some fluctuation
or error is applied,
basically you are kind of
breaking that bias introduced
by the strong transverse field
at the beginning of the anneal.
So obviously, in the
end, the question
is, are you still solving
the right problem, because
of fluctuations?
But I think that for
something like fair sampling--
and we haven't tested in detail.
We can, of course,
simulate this.
Any type of fluctuation will
likely be of a slight help,
in my opinion.
BORIS ALTSHULER: More questions?
Yeah.
AUDIENCE: Sorry [INAUDIBLE].
Great talk, Helmut.
Thanks very much.
So we've also been looking
at the backbone of samples
coming from the system.
You mentioned,
during your talk, you
could imagine using this
as an analysis technique
to determine which instances to
send to the quantum annealer.
But one of the
things we've observed
is that getting a
good estimate of what
that sort of spectrum of
the [INAUDIBLE] looks like
can actually be very complex.
And in fact, we've been finding
that using the quantum annealer
to try to heuristically
estimate what that is
is actually one of the
fastest methods for that.
Do you agree?
HELMUT KATZGRABER: No.
Sorry, I just had to say that.
AUDIENCE: Yeah.
HELMUT KATZGRABER: So
this is one metric.
We also have other metrics
that we have developed
and that we're
currently testing,
especially based with
population annealing.
What I like about
this is, this is just
a feature of the problem,
not the algorithm.
But we can also use
algorithms to basically get
a handle on how complicated a
problem could potentially be,
at least for a
sequential method.
And that is, at least,
a fair comparison now
to a quantum annular.
In there, the
experiments we have
done with that metric, that
is extremely quick to measure.
We have promising
results, suggesting
that there is a strong
correlation-- in fact,
even stronger correlation
than with this p of q.
But having said that--
and this is something
that I always keep
saying-- there is really
very little to no understanding
about this spin glass physics,
especially when it comes to the
order parameter distribution.
And everything that
we have learned so far
has just been, literally,
often by trial and error
over the last two
years-- by tailoring
a problem to a particular
physics outcome,
and then seeing
what it looks like,
and then using that to
go on problems where
we don't know the outcome,
and try to do predictions.
So there is a lot to be learned,
from all kinds of points
of view.
AUDIENCE: Thanks, Helmut, for
the very interesting talk.
Back to the benchmarking of
the weighted partial MAX-SAT
problems and the speed-up
that was predicted,
given the fact that [INAUDIBLE]
are equivalent to weighted MAX
2 SATs, I was curious
to know-- what model
of weighted MAX-SAT
problems did you try?
HELMUT KATZGRABER: Yeah,
it's a complicated thing.
You see, I wanted to sweep
the details under the rug.
[INAUDIBLE] is going to
show you more about this
in the next talk, but there
are some [INAUDIBLE] in there,
and-- yeah.
It's not just a
standard MAX 2 SAT.
But at least it's a
whole class of problem.
You see?
Before we were saying,
here are spin glasses.
Look, these five are
fast, these 100 are slow.
Here we have something
where it doesn't
matter what we generate,
it's almost always fast.
BORIS ALTSHULER: Maybe last
one and short question, please.
AUDIENCE: Hi.
You said that a fair comparison
is only if you-- it feels fair
if you compare the
quantum annealer
to a non-tailored approach.
Now, I definitely
understand that feeling.
But usually, you
know the architecture
of the quantum annealer.
So it feels like
in the real world,
we will always be able to come
up with a tailored approach.
HELMUT KATZGRABER: I agree
and I disagree with that.
So we can produce problems
on the Chimera architecture
that we can predict will be
extremely hard for quantum
annealing, and also for tailored
algorithms like the HFS method.
So you see, there is ways.
And if you look at the problem,
yes, you know the structure.
But you just see random bonds.
You cannot really discern
what we did to it.
Yet, it will be
really, really hard.
BORIS ALTSHULER: OK.
Thank you very much, again.
[APPLAUSE]
[MUSIC PLAYING]
