[MUSIC PLAYING]
NICHOLAS CHANCELLOR: My talk is on max
set multibody frustration and multibody sampling
on two localizing systems.
This work was done with many collaborators,
in particular Paul Warburton, who's in the room here.
The way a lot of this came about was things
that we were first thinking about for building couplers.
And then we realized we could use the same kinds of ideas
for many other applications, which I'll talk about.
First I'll just go over the basic idea very briefly.
It was already gone through in much more detail
in Paul's presentation.
And also we have a paper on the archive
that people can look at for the details.
I'll talk about spectral mapping [? phasing ?] spins, and then
briefly go through over two applications,
one for decoding turbo code, which
is a way of encoding classical information like for a cell
phone or something, and then another
which is quantum particle simulation, which I'll discuss.
So first let's talk about what we're not doing,
which is the penalty formalism for SAT.
So in this case, you're looking to ask whether a set of causes
can be satisfied.
And you say if the clauses can be satisfied,
we want an energy of zero.
If they can't be satisfied, we want an energy bigger
than some gap.
We want it bigger than some gap so we
don't have spurious low energy states that
will confuse our algorithm.
But we don't really care how much bigger
it is than that gap.
We just want bigger.
On the other hand, if you penalize every clause violation
equally, then, even if your clauses cannot be all
simultaneously satisfied, your solution will still be
the solution that satisfies the most number of clauses.
This method does involve ancillas,
so this is all assuming the ancillas reach their ground
state.
I'll explain very briefly how that's done.
Another point is as long as you have a good spectral separation
of your spurious states, you can also
use this to generate a Boltzmann distribution for sampling.
So a very brief introduction of what we did.
This can be found in the archive paper, which
is listed up there.
Basically we take advantage of symmetry.
We create a fully connected graph between the logical bits,
connect those to some ancilla bits by carefully choosing.
And then those ancilla bits, if we arrange it right,
will effectively count the number of logical bits
that are up.
Using this, we can build-- well for one
we could build couplers, but we could also create clauses.
And for exactly what fields and couplings we choose,
I refer you to the paper.
So a simple example is if we can choose those in this way,
those are the ancilla values that we
would have in the ground state for given logical bit values.
By applying local fields on these ancillas,
we can make it so that every state except for the zero,
zero, zero has an energy of zero,
and the zero, zero, zero state has an energy of g.
This would be an OR clause.
Only the state where none of them are true are done.
Just as a brief aside, you don't have
to choose these in such a way that you're actually
creating a degeneracy.
You could just use the same idea for a nonlinear constraint
on the number of logical bits that are up.
I'm not going to talk much about this anymore
for the rest of the talk.
But even though what I focus on is things like SAT problems,
there's no fundamental reason things
have to be sort of discretized in this way.
You could arbitrarily assign energies and then
have a nonlinear constraint on the number of bits
that are up in this gadget.
So one thing that you can do with this kind of gadget that
was actually the subject of a recent archive paper
is you can use the Choi minor-embedding plus having
some ancillas hanging off to put a SAT problem, a max SAT
problem on the Chimera.
What I've shown here is actually an XOR SAT
if you look at it carefully.
But you could do the same thing with a SAT.
This, however, has some drawbacks.
First off, you need the high connectivity.
That makes it relatively inefficient.
Secondly, and this is a more subtle thing,
is some clauses you actually can't
make very efficiently this way.
For example, this clauses with alternating ANDs and ORs,
if you try to count the number of ancillas you need for that,
it grows exponentially with the number
of those parenthetical terms.
However, I'm going to show some new ideas on how those problems
can be addressed.
After giving a brief one side aside
about another way of implementing these XOR type
things, which is somewhat similar to our thing,
but was discovered by a different group.
It's about some of the ideas that Wolfgang Lechner
and others recently put up where to do a parity check clause,
you create just a chain of three locals, in addition to
some ancillas there.
You could use our gadget to create three locals.
There are also other gadgets to do this.
And I just want to point out that this
has the same idea where it reproduces the whole spectrum.
However, what happens is if the causes are satisfied,
these ancillas in the middle act just like a spin chain.
If the parity is the other direction,
they can't all be satisfied.
It acts like a spin chain with a domain wall.
So it creates a degeneracy, which
would be bad for an application like sampling.
However, you could easily just weaken one of these.
So this could do, in the case of XOR,
this could do the same kind of thing we're looking at.
But it can't be generalized to other clauses.
So after that aside, let's come back
to what we can do with this to create these problems more
efficiently.
So let's imagine just the two-bit version of our gadget.
Now this seems like a really dumb thing to do at first,
because we already have two local couplers and fields.
So why would anyone ever want to do this?
You're recreating something you already have, just naturally
on the device.
However, there's something interesting
that happens with these, is these ancilla actually indicate
what the value would be of either an AND or an OR.
You can stack two of these gadgets on top of each other,
is one way to create something that will-- well,
whatever-- will indicate a value of an XOR between two of them.
Basically, you just apply a gadget
to the ancillas of another gadget.
If you wanted an indicator of that,
you can also just use a gadget for our three local.
There's several of those that have been proposed
that don't require three bits like our-- three ancillas
like ours would but only require a single one.
So what you can do now, that I've already kind of hinted at,
is if you take these ancilla bits
and feed them back in to other gadgets,
you can actually create bits where
applying a local field on one of these bits
higher up in this structure, in this hierarchical structure,
will create, effectively, a complicated clause
or create a penalty that corresponds
to a complex clause.
And you can imagine you can do this
efficiently for any clause that can
be written down efficiently.
Any cause you can write down efficiently using AND, OR,
XOR, and parentheses, you could also efficiently
create this way.
Also it doesn't require a fully connected graph.
We haven't published this yet.
This is something that we're currently working on,
but seems pretty exciting.
I think we should be able to do some interesting things
with this.
So let's talk about an example of this.
And let's talk about an example that just uses the XOR clause
or parity checks, which is so-called turbo code.
What a turbo code is is it's what's
known as an interleaved convolutional code.
Basically all the odd parity checks you do on the bits
in-- let's say one order you assign one, two, three, four,
five, six.
In this case it's just six, but you can do it with any number.
In real practical applications with very many, then
for the even ones you do some other random permutation
and apply these.
And this has been shown to be a good way
to decode classical communications to send.
So you can embed a decoder for this using our idea,
using basically a stack of these three local embeddings.
One thing to note is that in the case of XOR,
this is very similar to an idea that the Simon Benjamin
group have recently proposed.
However, they don't look at other clauses.
And I give the archive number of their paper right
there for those who are curious.
So now let's talk about a different application,
which is what if you wanted to use these--
because we can make higher locality terms in addition
to SAT things.
It's another example of the XOR or higher locality terms,
depending on what language you like.
But let's talk about particle simulation.
So what you could imagine doing is
you could imagine creating high locality terms
and having your individual spins, which
are the red dots there, between each of them
touch exactly two of these high locality couplers.
And you can imagine doing that.
So then what happens is if you flip one of these spins,
you'll frustrate two of those high locality couplers.
And then if you flip a spin that's already
touching one of these, it will unfrustrate one coupler
and frustrate the next one.
And then if there are two that are already frustrated,
flipping one will unfrustrate both.
So you can imagine this creates effectively a particle
Hamiltonian that's a high-dimensional analog
of a one-dimensional domain wall.
So yeah, exactly.
It will leave strings behind, just
like a domain wall will where the spin behind it will flip.
I show here examples for a square and hexagonal lattice.
You could imagine doing it for other things.
So the question is, what happens if, rather than doing this
with real couplers, we do this with our gadget?
Well, if we do this with our gadget and look
perturbedly, so look at the lowest order of perturbation
theory where something interesting happens where
you can actually flip a logical spin, some things go right,
and some things go wrong.
The things that go right is all logical bit
flips occur at third order of perturbation theory.
If all of these touch exactly two, that's good.
If some logical bit flips required flipping two ancilla--
one ancilla and one bit, whereas others required
flipping two ancillas and a single logical bit,
that would immediately be bad because it's
different orders of perturbation theory for different processes,
different particle creation, annihilation,
or translation processes.
And all of these transitions go through the same number
of paths to make these transitions,
and they all go through these intermediate states
with the same energy.
Now this is sort of difficult to believe.
I'm just presenting this.
I haven't given the details of what the fields are.
But if you go through our papers, it works.
And if you go through and actually calculate perturbedly
what the off diagonal elements of this Hamiltonian are,
that works.
What doesn't work is something subtle.
The second order fluctuations are not the same
for every logical state.
We're looking at third order of perturbation theory.
So what matters here are second order fluctuations
where a bit flips and then flips back.
And that will create an effective potential
on the perturbative Hamiltonian, we realized.
So if we just do this naively with our gadgets,
it almost works.
All the transition rates at some order of perturbation theory
are the same and you'd get a perturbative simulation
of particles.
However, it doesn't work because you get effectively
these potentials that prefer some states over others.
But there's a fix.
If you add an additional ancilla that you
attach to the ancillas with different strengths--
you make all those couplers different strengths--
you can effectively tune by how easy it
is to flip that what I call sigma f, the spin
to control the fluctuations.
You can effectively tune how strongly the fluctuations
will be about different logical states in the system,
again assuming the ancilla are in their ground state.
And I looked at this numerically.
It does seem to work.
There's also no reason you would have to only use one.
In principle if you needed more to control your fluctuations
or wanted more, you could do that.
You might be able to do it in different ways.
But it appears that in this way, you can actually perturbedly
now-- thank you-- perturbedly now create
these effective particle Hamiltonians--
or really they're particles that leave strings.
But they're effectively particle Hamiltonians
that you can realize perturbedly on using
this device by the amount of-- by the field
you applied to the ancilla, you can create both mass
and you can create things like string tension
for the strings they leave behind
and things like that and string interactions
and all kinds of things like that.
So that being said, here's our conclusions.
We have made an alternative method for mapping problems
based on MAX-SAT formalism.
We can now, with our new technique,
any clause that you can write efficiently,
you can do efficiently this way, unlike what
we have in our current paper where there's only some
that you can do efficiently.
Some will be inefficient.
And then I gave a couple examples,
this classical message decoding with the turbo code,
and talked about some ways you could realize Hamiltonians
perturbedly, basically taking advantage of the fact
that our gadget was built off of symmetry.
It has a high degree of symmetry.
And that means that the transitions just happen
to all work out to be the same.
And I believe that's it.
I will give a quick plug for some
my other work that's not related to this,
but might be of interest to some people.
And I think that's-- OK.
[APPLAUSE]
SPEAKER: Questions?
AUDIENCE: Could you say a little bit about how efficient
this method is?
You say that it's efficient, but can you
give us maybe numerical examples,
for example if you were trying to encode
a MAX-SAT problem with a thousand clauses
and three variables per clause, [INAUDIBLE] that actually
[INAUDIBLE].
NICHOLAS CHANCELLOR: I haven't looked in a lot of detail.
All I meant was that it was efficient
compared to our other method.
So our other method has some clauses
that would require an exponentially growing number
of ancilla to realize.
This new idea does not.
So in that complexity theory sense, it's efficient.
And is it better than some other thing someone else has come up
with, we'll have to see.
SPEAKER: More questions?
OK, let's thank Nick again.
[MUSIC PLAYING]