[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]
