- Okay. Hi, my name's Alwin Zulehner.
And I'm from Johannes Kepler University in Linz. Austria.
And now we're getting a bit more technically I would say,
because now we're diving into the topic
of Compiling Quantum Circuits to NISQ Devices.
So just a brief recap, we already heard it,
and I probably can assume that everyone is aware of that.
NISQ stands for Noisy Intermediate-Scale Quantum.
And for example, IBM has some architecture for them.
And here I took IBM QX5
which is of course, available for cloud access,
has 16 qubits,
and have there seems to be some issues on this PowerPoint.
So you can see the error rates here,
but single-qubit gate error rate
is about 10 to the minus two.
And a multi-qubit gate tend also, no, sorry,
same cubic gate should 10 to minus three,
and multi-qubit gate to 10 to minus two.
Okay. So if we want actually to run
any sort of algorithm described
as a circuit on this devices,
then we have to do some things.
Actually we have to decompose our operations
into elementary operations supported by a quantum computer.
And those are single qubit gates,
which are apartment tries by three parameters,
they are describing a rotation
about the C, X and Z axis.
And of course we have some two qubit gates,
which are basically controlled Not gates
or also called CNOT gates.
So the problem, what I'm basically talking about,
I mean, some formulas are still missing,
but it's spelled them before,
as set we have some sort of gates.
We have single qubit gates.
Those are visualized by those boxes.
And we have some sort of CNOTs
and those are allowed to interact
with two qubits at the same time.
And as set when we want
to run anything on a device,
we have, for example, to decompose,
you can see here at toughly gate,
into a sequence of single qubit gates and CNOTs.
And as you can see here, this can be quite costly.
So a lot of one or two qubit gates are needed,
but what's even more important is that we have,
some constraints that are given by our architectures.
And you can see there on the right hand side,
a picture of QX5.
And basically, since it's a physical device,
we have some restrictions because not all qubits
are coupled with each other.
And this physical layout easily translates
to a directed graph.
And here we have visualize qubits the physical ones,
with vertices and the arrows indicate whether
we can apply a CNOT or not.
So for example, this arrow down here means,
that we can't apply a CNOT where we have Q1 target source
and Q0 as target qubit.
And if there's no arrow in between two qubits,
we can not interact those two.
So I call this now CNOT-constraints,
for the rest of my talk
and assume that we have given,
such a quantum circuit as shown there,
where we have some logical qubits Q0 to Q5.
And what we want to do is we want to map them,
onto the physical ones of the device.
So we can do it like this quite easy,
map Q0 to the physical bond to Q14,
Q1 to Q15 so on and so forth,
so we can choose whatever we want.
And if you check then our gates, we can see,
here I highlight the control of the CNOT
with in gray and the target in blue.
And whenever there's an arrow in between
those two physical qubits, then we can apply the gate.
So no problem for the first one,
same for the second one.
But here at the third one,
we have some sort of issue.
So there's no connection from Q3 to Q0
and similar to the fourth gate.
The fifth gate is okay again and also again,
an issue for the last one.
So what you might think,
which has for unlucky,
we should do a better choice for mapping,
but the problem is usually it's not possible
to find such a mapping.
You can easily imagine why this is not possible.
So assume we have any qubit that is,
has a CNOT with assume six other qubits.
Then you will never find a spot here on the coupling graph,
where you can map them.
And the idea now is that we have to change,
that mapping dynamically during our compilation process.
And to this end,
we in search so-called SWAP operations or SWAP gates.
And this basically changes the state of two physical qubits.
And if you assume that Q0 and Q1 the logical bonds,
are mapped to them and we apply SWAP,
we actually insert values.
So basically the mapping also changes.
This means we can easily amuse those SWAP operations
to move around the physical,
the logical qubits on the physical ones.
And of course, since this decomposition of a SWAP gate
has also said to satisfy the coupling map,
we have to change the direction of the middle CNOT,
and this can be easily done
by inserting Hadamard operation.
So this is a bit cheaper than using as well.
And now I just to give you a feeling,
how this could work out by presenting a naive solution.
So we're just looking at one gate at the time,
and of course, a set for the first two it's not a problem.
And now we have the problem here,
that you want to conduct a CNOT where the control
is currently mapped to Q3,
but the target is mapped to Q1 or to Q0.
So what we can do here is applies a SWAP,
And by this, we can move the control towards the target.
Then we can apply the gate.
And then we just repeat the same thing for the next gate.
Again, one and two SWAPs,
we can apply the gate
and then the gates possible,
here we need another SWAP and then we're done.
So this is quite easy,
but if you remember how to decompose a SWAP gates,
then you can imagine this is quite costly.
So originally we have just 6 CNOTs
and afterwards we have 6 CNOTs plus for each of the SWAPs,
we have three more CNOTs,
So this is quite a huge overhead.
And the question is,
can we do that in cheaper version?
And of course we can,
but the problem is if we want to do it optimally,
then we run to issue that it's an NP-complete problem.
So to leverage further research on such compilers
and how to reduce the overheads,
to solve this NP-complete a problem.
IBM has launched and developed the developer challenge.
And here the goal is that we want to optimize the circuit
that's results from the compilation is optimized,
regardless certain cost function.
And here we give the penalty of 10 to the CNOTs
and the penalty of Von for single qubit gates.
And the reason for that is that the fidelity
of CNOT is 10 times worse than fidelity
for single qubit gates.
So we're aiming for optimizing the fidelity
of the compile circuit.
Then some example, architectures are given by IBM,
such as six qubit circular architecture,
is shown on the right hand side.
And finally some random circuits surface input,
where each of those had here,
you can see a circle with six qubits
and in each layer we have and have gates
and those gates are randomly sample from SU(4),
which means that they are described by a random four
by four, a unitary matrix.
And of course there's again, that decomposition for debt.
IBM has fortunately given that.
So if you have an arbitrary gate from SU(4),
then you can always decompose it into sequence
of three CNOTs and seven single qubit gates.
And what the task is now,
is we have that circuit given on the right hand side,
and we want to map it to the given architecture.
And now I can present you the solution that I had in mind.
So first I start with the circuit.
And what I do is,
I group gates that are applied to the same qubits,
basically this undoes the decomposition seen before,
but this allows to reduce the compile time significantly.
So what I did is I formed those groups,
and I just then transformed the circuit
into some sort of interaction graph or dependency graph.
So the groups G0 to one to two stands for,
the three gates of the first layer.
And of course after those,
if they're depend operating the same qubits,
we can apply the gates of the next layer
and then the gates of the final layer.
And what the idea was now is,
that we start with an arbitrary mapping,
because especially if we consider random circuits,
then the initial mapping doesn't matter too much,
because you need a lot of SWAP operations anyways.
And so then our own or my algorithm
was basically separated into three steps.
We had to pre-processing,
Then we have the compilation algorithm,
where we first search for groups that can be applied next.
So for our initial mapping,
we can immediately map those gate groups.
Then, as a next step,
we look for groups that could be applied, next.
Those are now highlighted in blue.
And the problem here is that,
we cannot directly apply them,
because the conditions of the coupling map
are not satisfied.
So we call our A* based search algorithm
that finds a permutation,
so SWAP gates that allows to map at least one of the groups.
In this case, it finds a solution
where both groups can be mapped.
And then we just repeat our algorithm
until we map all the groups.
So again, we determined which operations could be,
or which groups could be applied next,
highlighted in blue.
We call the mapper,
which just finds a solution with one SWAP,
and then we can apply group G6.
So we have to call our mapper again,
those are the potential groups to be mapped next.
And after applying bond word SWAP gate,
we can compile all those groups and sobers on.
So this basically generates a circuit
where all the set is constraints are satisfied.
However, we can do it even better.
And for that, we do some post-mapping optimization
where we Re-group again.
So we consider gates actionably same qubits as a group,
and we Re-compile those groups.
So for example, if you consider the box highlighted in red,
this is a group from SU(4) a gate from SU(4),
followed by a SWAP operation.
And if you draw it, this part here,
the decomposed version of this part,
then you can see this is actually composed of six CNOTs
and seven single cubic gates.
However, as we know any unitary matrix
of dimension four by four can be decomposed into,
three CNOTs and seven CNOT cubic gates.
So what we do, if we Re-compile,
we just have to adjust the parameters for,
you want to use seven,
and then safe our SWAP gate.
So this means that some of the SWAP gates,
are basically for free, if you do this Re-compiling.
And the nice thing about it,
is actually that we already know that during compilation.
So if we are aware that we perform a post-map,
a post-mapping optimization afterwards,
we can immediately incorporate that into our compiler
and by that this prefer some of the SWAP gates,
for which we know that,
they will be canceled out later again.
So then I want to show you,
a small comparison to the QISKit compiler.
And this is the compiler of version 4.0.4 pound 15.
And again,
I used circuits and architectures provided by IBM.
And for example, here, you can see results for,
this is a bit blurry, for 5 qubit architectures.
So what I did here is I plot the cost
for the QISKit compiler on the X axis
and the cost for my compiler on the Y axis.
This means whenever there's a data point,
underneath the main diagonal,
that my compiler performed better than IBMs.
And in addition to that,
I also plotted horizontal and vertical lines,
which indicate the cost of the circuit before compilation.
And this is quite interesting to see here,
that with the post-mapping optimization,
it's even possible to generate or compile circuits,
that are cheaper than the original ones.
So this was actually quite unexpected.
Then we did the same for 16 qubit architectures.
And again, similar thing here,
we are always better than a QISKit compiler.
However, what's also very interesting to see here,
is that dependent on the architecture,
the circuits tend to group.
So for example, on the right hand side here,
the red dots indicate a linear architecture.
And of course, if you just have very few connections
between the qubits that are allowed,
then we have a very huge overhead cost by compilation.
And finally also have some results
for a 20 cubit architectures.
And those look pretty similar to the 16 qubit ones.
And for compilation,
not only the quantity of the compile circuit matters,
but also a compilation speed.
And for example, compared for the 20 qubit architectures,
we also achieved a speed up of, up to a factor of 35.
So also quite a good improvement here.
And if you're interested in more details of this method,
there I've written a paper about that,
and it has been accepted and presented
to this year at the ASP-DAC in Tokyo.
And if you want to talk more about my methods,
you can of course ask questions in,
for example, the unconference sessions.
So this is about my solution for the developer challenge,
and just to give you a brief outline,
what we're also doing at the university
is that we have some other directions,
where we have for example,
synthesis of pooling components for quantum computing,
where we have some sort of a new of design flow.
And also we do some simulation.
So we have here a new method where we basically try,
to decrease the memory overhead
by using some clever data-structures,
which in some case turns out to be really efficient.
And what's nice about this is that,
it's currently been integrated
into QISKit as well as an add on.
And I also want to thank the guys from IBM
for helping with that integration.
So that's all from my site and I'll hand over.