(xx4direction_ x10of)
1_
kinda
in
the
|
{z
}

A route towards quantum-enhanced artificial intelligence
Vedran Dunjko

v.dunjko@liacs.leidenuniv.nl

What is AI

Justus Piater

Piater: “An unsuccessful meta-science that spawns successful scientific disciplines”“Catch-22: once we understand how to solve a problem, it is no longer considered
to require intelligence…”

What is this talk about? So what is AI? All? Nothing?

Quantum Machine
Learning (QML)

Reinforcement learning and a bit “beyond”
Machine Learning/AI(ML/AI)

Quantum Information
Processing (QIP)Outline

Part 1: “Ask not what Reinforcement Learning can do for you”
The theory, bottlenecks and applications

Part 2: “… ask what you can do for reinforcement learning…”
Quantum environments and model-based learning

Part 3: “… and for some aspects of planning on small QCs”
Learning and reasoning (actually…SAT solving)But… what is Machine Learning?

Learning P(labels|data) given Learning structure in P(data)
samples from P(data,labels) give samples from P(data)
Generalize knowledge

Generate knowledge

Also: MIT technology review breakthrough technology of 2017
[AlphaGo anyone?]

RL more formal
Basic concepts:
Environment:
Markov Decision Process
Policy:Return:Figures of merit:
finite-horizon:

infinite-horizon:

Optimality:8Is that all?

•More complicated than it seems already in the simplest case;value iteration, policy search, value function approximation,model-free, model-based, actor-critic, Projective Simulation…

•

Infinite action/state spaces
Partially observable MDPs
Goal MDPs•

Knowledge transfer (and representation), Planning…
…AI?

•
•

9

Reinforcement learning vs. supervised learning•learning “action” - “state” associations similar to “label” - “data” association•

how data is accessed, and how it is organized is different•

not i.i.d, not learning a distribution, examples provided implicitly(delayed reward, credit assignment problems)10

RL vs. SL

Example: learning chess•

MDP is tree-like11

RL vs. SL
Example: learning chess••

MDP is tree-like, but not a tree
examples given only indirectly: credit assignment(unless immediate reward)•

strong causal & temporal structure(agent’s actions influence the environment)
NB: supervised learning, oracle identification, etc.
can be cast as (degenerate) MDP learning problems

12

From pretty MDPs … to Using RL in Real Life
Navigating a city…

https://sites.google.com/view/streetlearn
P. Mirowski et. al, Learning to Navigate in Cities Without a Map, arXiv:1804.00168
13

So how to do RL (real life) RL• via pure RL: know only what to do in situations one encounters• better: generalize over personal experiences — do similar in similar situations(still, unlike in big data, “training set” is a near-negligible fraction…)• what we actually do: generate fictitious experiences(“if I play X, my opponent plays Y, I play Z….”)

conjecture: most human experiences are fictitious (tilted face problem)

Learning unified•

via pure RL:

old-school RL

Slow

•

better: generalize overpersonal experiences

supervised learning-like

Doing…ok

further: generatefictitious experiences

unsupervised learning-like

Hard as heck•conjecture: most human experiences are fictitious (tilted face problem)

“The cake picture” for general RL/AI: unifying ML

Direct experienceexpensive

pure RL
generalization(SL)generation(UL)

Can generalize (only)
over direct experienceCan generalize oversimulated experience?

“If intelligence was a cake, unsupervised learning would be the cake,supervised learning would be the icing on the cake, and reinforcement
learning would be the cherry on the cake.”-Yann LeCun

even the cherry can be as complicated as you wish

Progress in RL (connecting RL, SL ,and UL)a) generalization (SL):associating the correct actions,to previously unseen states⇡(a|s)⇡(a|s)

function approximation⇡✓ (a|s)⇡ (a|s)✓ models (Sutton, ’88)
-linear-neural networks (Lin, ’92)
-decision trees, etc…

deep learning(+ MTCS!)

AlphaGo?

b) generation (UL): model-based learning

17

Another aspect:2) generation as simulation

because real experiences can be painful(and expensive)What I want to do when I grow up

train here

Build a perfect home

to do better
here

good AI willlearn hierarchicallyand transfer
the learned to a
new domain

Pre-training will have at least two flavors…

1) reinforcement learning (slow, faster than real life)2) optimization (find optimal patterns of behaviour)

Both are computational bottlenecks
19

Progress in RL (connecting RL, SL ,and UL)a) generalization (SL):associating the correct actions,to previously unseen states⇡(a|s)⇡(a|s)

function approximation⇡✓ (a|s)⇡ (a|s)✓ models (Sutton, ’88)
-linear-neural networks (Lin, ’92)
-decision trees, etc…

deep learning(+ MTCS!)

AlphaGo

Quantum enhancements have been?
considered for both problems.
Here we focus on b)b) generation (UL): model-based learning

20

Part 2: … ask what you can do for reinforcement learning…

Can I RL better if the environment is quantum?
What are environments?

…

Quantum Agent - Environment paradigm

is equivalent toAgent

Envir.
Agents (environments) are sequences of CPTP maps, acting on a private
and a common register - the memory and the interface, respectively.
Memory channels = combs = quantum strategies

What is the motivation again?
Fundamental meaning of learning in the quantum world
Speed-ups! “faster”, “better” learning
What can we make better?
b) learning efficiency (“genuine learning-related figures of merit”)

success
probabilitya) computational complexity

time-steps

related to query complexity

24

Q

Q

speeding up classical interaction
is like Groverizing an old-school telephone book..
2
XV.

SYMBOLS FOR TALK

XV.

XV. SYMBOLSTALKSYMBOLS
FORFORTALK

2

2

S = {s1 , s2 , . . .}Quantum-enhanced XV.
quantum-accesible
SYMBOLS FOR TALK RL
S = {s , s , . . .}
1

2

2

S=
A
= {s
{a11,,sa22,,.....}.}

A = {a1 , a2 , . . .}ak , ak+1 , sk , s

Agenta ,a ,s ,sk

k+1

Environmentkak , ak+1 , sk , s

S = {s1 , s2 , . . .}A = {a1 , a2 , . . .}Q
A = {aAgent
1 , a2 , . . .}

XVI.

…

ak , ak+1 , sk , s

INTRO

XVI.

INTRO

Q

EnvironmentQ

The clear motivation for considering quantum internal processes in a an agent is to see whether such agent can
The clearmotivationconsidering
quantuminternal
processes
in a an agent
is to see whether such based
agent can
XVI. agent.
INTRO
be more successful,in anysense, forthana fully classicalBy
construction,aprojective-simulation
agent
XVI.agent.
INTRO
be more successful, in any sense, than a fully classicalBy construction, a projective-simulation based agent
realizes its input-output
relations by performing a random walk, that is a Markovian process, over the clips. It isrealizes its input-output relations by performing a random walk, that is a Markovian process, over the clips. It isverytotemptingseegeneric
improvements
canbeinbeobtained
if iftheparticularwalk
performed
Thetempting
clear very
motivation
forquantuminternal
processes
ainan
agent
isthe
see
such
agent
The
clearwhether
motivation
for considering
quantuminternal
processes
a an
agent
isto
to
see whether
whethersuch
agent
cancanto considering
see obvious
whether
obviousgeneric
improvements
canobtainedparticular
walk
is is
performedinaquantum
way.
This
is
also
statable
in
terms
of
a
searchproblem,
if
the
walk
indeedperformsasearch.
Here,besuccessful,in anythan classicala fullyclassical
agent.
By construction,
aprojective-simulation
projective-simulation
based
agent
in amorequantumway.
This
is sense,
alsoa statablein terms
of a search
problem,
if the awalkindeed performs a search.
Here,be more successful,inanysense,
than
fully
agent.
By construction,
based
agent
realizes
its input-output
bya randomthat isimprovementa improvement
Markovian process,overisistheclips.
Ittheis thethe questionis question’what
do
we lookfor’performing? The
resultto awalk,’generic
theorem’given
theisrelations’what
dorelations
we
lookfor’performing?closest
The
closestresulttothata ’generictheorem’
givenviaviarealizes
its input-output
byarandomwalk,isaMarkovianprocess,overtheclips.
It isvery
temptingframework
to seewhether
obviousgeneric
improvements
canbe
if matrix
theparticular
walk is symmetricperformed(generalized)of Szegedy,
which
relates
the eigenvalues
oftransition
aobtained
transition
matrixan(egodic,(generalized)
frameworkof
Szegedy,which
relatestheeigenvalues
of
a
of
an
(egodic,
symmetric
very tempting
seedropped
whether
obviousimprovements
canproblem,bea corresponding
obtained
if theparticularwalk
is performedinatoquantum
way.later)This
is alsogenericstatablein terms
of a search
if the walkindeedperforms
a search.
Here,- thisislater)
Markovchain,
andthe eigenvalues’quantum
walk
which
is is
- this is dropped
Markovchain,
andthe
eigenvaluesof aofcorresponding’quantum
walkunitary’unitary’
whichthequestion
is
’what
do
we
look
for’
?
The
closestresulttoa’generic
improvement
theorem’
is
given
via
the
in a quantum
way.
This
is
also
statable
in
terms
of
a
searchproblem,
if
the
walk
indeedperformsasearch.
Here,definedin his formalism.
defined in his
formalism.
(generalized)
Szegedy,whicheigenvalues
ofon
a transition
offor
anthe
(egodic,
symmetric
the question isThe’what
we lookoffor’? The
closestto aapplied’generic
improvement
theorem’is given
via thefounddoframework
relationshipbetweenthetwo relates
can result
bethe
readilytheknownmatrix
resultsclassical
hitting
The found- thisrelationshipbetween
the
two
can
be
readily
applied
on
the
known
results
fortheclassical
hitting
is dropped later) Markov chain, and the eigenvalues of a corresponding ’quantum walk unitary’ whichistimeof some subsetof the nodes(themarkednodes)of the Markov
chain (which
has ofexpected
hittingsymmetrictime in(generalized)
frameworkof
Szegedy,which
relatestheeigenvaluesofatransition
matrixan(egodic,
definedin hisformalism.
time of somesubsetof thenodes(themarkedof thematrix,
Markov
chain(whichofhas
expected
hittingtime in
O(1/
✏),
with
being
the
spectralgap
of nodes)thetransition
and
✏
the
fractionmarked
nodes
vs.
all
nodes),-O(1/this isdroppedlater)
Markovchain,
andthe
eigenvaluesofacorresponding’quantumwalkunitary’whichisp✏ theThe
foundtherelationshipbetweenthe transition
two can bematrix,
readily appliedon theknownofresults
for nodes
the classicalhitting✏), with
being
spectral
gap
of
the
and
fractionmarkedvs.
allnodes),
theanalogous
hittingtimewhichnodes)
scales ofas theO(1/✏) - thisa typeof generichitting
improvement.
p Markovtimeof somesubsetquantumof the nodes(themarkedchainyields(whichhas expected
time indefinedin hisandformalism.
and the analogous
quantumhittingtimewhichscales
as
O(1/
✏)
this
yieldsa
typeofgeneric
improvement.
Motivation
story
for
the
talk:
Sure,
gettinganexponential
speedupismuchcoolerthan
gettingaquadraticone.
O(1/✏), with being
the spectral
gapof thetransition
matrix,pand the✏ theknown
fractionresultsof marked
nodes
vs. all nodes),
The
found
relationshipbetween
the
two
can
be
readily
appliedonfortheclassical
hittingV.
Dunjko,J.
M.
Taylor,H.
J.
BriegelIn
problems
we quantum
address
talk about
agents,scales
whichspeedup
abstractionsof yields
entitiesa thanwhich
exist,
andinteractwith
Motivation storyforthe talk:
Sure, wegetting
an exponential
is✏) muchcoolergettinga improvement.
quadraticone.
andthetheanalogous
hitting
time
which
asare
O(1/
- thistypeQuantum-enhancedofgeneric
machine learning
time
someansubsetofstory
the fornodes(themarkedtheMarkov
chain(whichhas
expected
hitting
timeinenvironment.
And
they
do Sure,so
inagents,
real nodes)
time.
Soofletusabstractions
considerananda whichsetting
wherereactiontime
isRev. Lett.
117,
130501(2016)In theofproblems
we address
wethe
talk
about
which
are
of
entities
exist,
andinteractwith
Motivationtalk:getting
an exponential
speedupisagent,much
coolerthanPhys.
gettingaquadratic
one.
important,
and
see
what
happens
ifabout
we,’only’
slow
down
the
agent.
We willdo andthisby solving
a is
O(1/
✏), withbeing
thespectralgapofthetransition
matrix,andfractionmarkednodes
vs.
all nodes),In
theproblems
wedo
address
wetalkagents,which
arep
abstractionsofentities
which
exist,
interactwithan environment.
And
they
so in
real
time.
So
letquadratically,us
consideran✏ theagent,
andaofsetting
wherereactiontimecartoonFermi problem.
Considera particulara mouse.
mouse
can
find
itself ofinwheretrickyreaction
situations,anenvironment.
And
they
do
so in
real time.
SoasletO(1/usconsideragent,
andsetting
timelikeisand the analogous
quantumhittingtimewhichscalesagent:✏) A- anthisyieldsaa typegeneric
improvement.

Quantum-enhanced access:Inspiration from oracular quantum computation…
Agent-like

Environment-likethink of Environment as OracleQuantum-enhanced access:Inspiration from oracular quantum computation…
Agent-like

Environment-likeUse “quantum access” to oracle to learn useful information fasterBut… environments are not like standard oracles…

“Oraculization”(taming the open environment)(blocking, accessing purification and recycling)

strict generalizationMaze:Classical agent-environment
Agent

Environment
Markov Decision Process:A
T(A, (A

B

B

T(B, (
D

C
T(C, (C,,
E

E

L. Trenkwalder MSc.

Maze:Classical agent-environment
Agent

Environment

Agent
A

Markov Decision Process:

B
C
D

A

E

B

D

C

,,
E

Maze:(Semi-)classical agent-environment
Agent

Agent
Markov Decision Process:

A

B

D

C

,,
E

Maze:(Semi-)classical agent-environment
Agent

Agent

Markov Decision Process:A

Environment

B

D

C

,,
E

Maze:(Semi-)classical agent-environment
Agent

Agent

Have:
|a1 , . . . , aM i ! |s1 , . . . , sM +1 iA |a1 , . . . , an iE|a1 , . . . , aM i ! |a1 , . . . , an iE

Want e.g.:

Environment|a1 , . . . , aM i0iA ! |a1 , . . . , aM iA |??iA
Why? Grover search for “best actions”
i.e.. convert environment to reflection about| !, #, #, !iMaze:(Semi-)classical agent-environment
Agent

Agent

Have:
|a1 , . . . , aM i ! |s1 , . . . , sM +1 iA |a1 , . . . , an iE|a1 , . . . , aM i ! |a1 , . . . , an iE

Want e.g.:

Environment|a1 , . . . , aM i0iA ! |a1 , . . . , aM iA |??iA
How? Oraculization

Oraculization (blocking)(taming the open environment)

1)

quantum comb2)

causal network

3)“blocking”

Oraculization (recovery and recycling)(taming the open environment)

Classically specified oracle

i

t
n
a
“qu

”
n
o
i
z at

f

36

(A flavour of) quantum-enhanced reinforcement learning
A few results:
Oraculization

Grover-like amplification for optima:
Learning speedup in luck-favoring environments
quadratic improvements in meta-learning

Quantum-enhanced machine learning
Vedran Dunjko, Jacob M. Taylor, Hans J. Briegel Phys. Rev. Lett 117, 130501 (2016)
Advances in quantum reinforcement learning
Vedran Dunjko, Jacob M. Taylor, Hans J. Briegel accepted to IEEE SMC 2017 (2017).

Just Grover-type speed-ups?
No… actually, most speedups are on the table…
in a booooooring way….

One step further: embedding oracles with exponential separation

Many oracular problems can be embedded into MDPs, while
breaking some “degeneracies”

One step further: embedding oracles with exponential separation

Oracle hiding a necessary “key”

oraculization
process

Inherited
separations

Few technical steps: make sure a) oraculization goes through; b) classical hardness ismaintained.
VD, Liu,Wu Taylor, arXiv:1710.11160

Open problems:-how far this can be pushed towards practically useful-oraculization seems far fetchedOraculization seems a stretch?
Think of it as intermediary step…

train here

Build a perfect home

to do better
here

Summary:-quantum-accesible environments can be “turned” into useful oracles-these we can access using standard quantum tricks

Caveat: Speedups are relative to a black-box model
42

What if I want to reason
over my model

Why ML/AI and QIP
make a perfect match

43

Why are ML/AI and QIP a perfect match

Both are natural enhancers
of other technologies

There are algorithmic
conspiracies!

Noise kills other algorithms…but
Noise is natural in ML!
Noise tolerance of problem-better applicability to nearterm devices-helps in database loadingReasoning and planning is hardPart 3: “… and for some aspects of planning on small QCs”

or: Hard computational problems, AI,
and restricted quantum computers

45

Reinforcement learning:Goal-achieving policy?

Supervised learning & COLT:
training perceptrons
under noise & consistent hypothesis

NP-hard

Unsupervised learning:
sampling from cold Boltzmann

Combinatorial optimization & planningplaying simple games (sudoku, Lemmings)

Many problems are harder: “do I win chess”, finding good policies in (PO)MDP are PSPACE,
many games are EXPTIME, and verification of processes is undecidable…

Can quantum computers help here?
-fundamental, but…
-not believed to be in BQP - not elucidating power of quantum computing, less explored-exponential run-times… in practice heuristics-results studied continuously (Montanaro, Ambainis, Aaronson, etc…)-a class of heuristics: annealers

QeML (quantum-enhanced learning)-exponential separations…
-particularly well-matched class of applications,also for near term!
-plays well with noise, plays wellwith shallow computations…

NP-problems (quantum-enhanced reasoning)-only poly-speed ups-a-priori, unlikely to be well-suited for(near-term) quantum computing

Can quantum computers help here?
-fundamental, but…
-not believed to be in BQP - not elucidating power of quantum computing, less explored-exponential run-times… in practice heuristics-results studied continuously (Montanaro, Ambainis, Aaronson, etc…)-a class of heuristics: annealers

QeML (quantum-enhanced learning)-exponential separations…
-particularly well-matched class of applications,also for near term!
-plays well with noise, plays wellwith shallow computations…

NP-problems (quantum-enhanced reasoning)-only poly-speed ups-a-priori, unlikely to be well-suited for(near-term) quantum computing
remainder of talk is in here

A general question: suppose you have a problem of size n,
and quantum computer handling m<<n qubits.
What can you do?

Could be… nothing!
Good algorithms exploit problem structure. Break it by “chunking”,
you loose (a lot of) speed. Thresholds!
An example: thresholds when quantum-enhancing a SAT solving algorithm.

VD, Ge, Cirac, arXiv:1807.08970

3SAT

f (x1 , . . . , xn ) = C1 ^ C2 ^ · · · Ck ^ · · · CL

f : {0, 1}n ! {0,Ck1}= (u _ v _ w), u, v, w 2 {x1 , . . . , xn } [ {x̄1 , . . . , x̄n }f (x1 , . . . , xn ) = (x1 _ x10 _ x̄51 ) ^ (x̄3 _ x̄10 _ x̄11 ) ^ (x̄_ x̄51)) · · ·(x111 __ x̄x44
4 _ x10
|
{z
}
"

"

“or”

“and”

clause or constraint
all constraints have to be satisfied

SAT problem: Is there a choice (assignment) of the variables,such that f evaluates to 1 (“true”)

3SAT

f (x1 , . . . , xn ) = C1 ^ C2 ^ · · · Ck ^ · · · CL

f : {0, 1}n ! {0, 1}Ck = (u _ v _ w), u, v, w 2 {x1 , . . . , xn } [ {x̄1 , . . . , x̄n }f (x1 , . . . , xn ) = (x1 _ x10 _ x̄51 ) ^ (x̄3 _ x̄10 _ x̄11 ) ^ (x̄11 _ x̄44 _ x̄51 ) · · ·Schöning:
9? x11., Pick
. . . ,assignment
xn s.t. f (x1 , . . . , xn ) =1
randomly.
2. Check if satisfying; output if is, and terminate
3. Find first unsatisfied clause,
flip any variable of the clause in the assignment

Do 3n times

A random, gently directed, walk in the space of assignments…

3SAT
Schöning (1999): if sat. exists, the walk finds it with probability (3/4) (3/4)
nnnn n=2 n(4/3),, ==loglog⇡ 0.415...
2 (4/3)Monte Carlo: (4/3) = 2(4/3)⇡ 0.415...
2

3SAT
Schöning (1999): if sat. exists, the walk finds it with probability (3/4) (3/4)
nnnn n=2 n(4/3),, ==loglog⇡ 0.415...
2 (4/3)Monte Carlo: (4/3) = 2(4/3)⇡ 0.415...
2

Quantum Schöning / any such sampling algorithm?
Instead of sampling, amplitude amplification (Grover):
Run-time:

⇤

O (2

n

⇤

) ! O (22n⇤) = O (2qn)

How many qubits needed? Cca. 3n qubits just for purified randomness + evaluation

Ambainis ‘04

What if I have only enough qubits for an m-sized formula?

f (x1 , . . . , xn ) = C1 ^ C2 ^What if I have only enough qubits for an m-sized formula?

Ck = (u _ v _ w), u, v, w 2 {x1 , . . . , xn }Setting some variables shrinks the formula:f (x1 , . . . , xn ) = (x1 _ x10 _ x̄51 ) ^ (x̄3 _ x̄10 _ x̄11 ) ^ (x̄11x1 = 0x1 = 1x1 = 0x1 = 1(x10 _ x̄51 )(true)(x10 _ x̄51 )(xx10 ),x(x1,x_ x,xx10…
)
x 1,x_ x,x
4 _ ,x4 _,x| 1 2{z 3 4} |5 6 {z7 8 }

set

free

(true)

What could I do if I have only enough qubits for an m-sized formula?
(xx10 ),x(x1,x_ x,xx10…
)
x 1,x_ x,x
4 _ ,x4 _,x| 1 2{z 3 4} |5 6 {z7 8 }Guess some variables:

set

free

1) Fix xV = x (1) , . . . , x (n m)
|

1

4

{z

solve on QC!

#

2) F (~x) ! F(xx_v (~x x c))
x _|Vmust do 2n m times

10}

formula of size m

How fast is this?
↵ = m/n((1 ↵)·1+↵· q )n= (xO⇤1(2_
x4 _ x10 ))|{z

quantum}What could I do if I have only enough qubits for an m-sized formula?
(xx10 ),x(x1,x_ x,xx10…
)
x 1,x_ x,x
4 _ ,x4 _,x| 1 2{z 3 4} |5 6 {z7 8 }Guess some variables:

set

free

1) Fix xV = x (1) , . . . , x (n m)
|

1

4

{z

10

}

solve on QC!

#

2) F (~x) ! F(xx_v (~x x c))
x _|Vmust do 2n m times

formula of size m

How fast is this?
↵ = m/n((1 ↵)·1+↵· q )n= (xO⇤1(2_
x4 _ x10 ))|{z

quantum

}

v.s.

⇤
n
⇤
2 n)
O
(x _(2x _ x )) ! O (2
|

1

4

{z

10

classical}Naïve solution - did we win?
= O⇤ (2((1 ↵)·1+↵· q )n )

↵ <>

1
1

2

⇡ 0.73<>speed in “rate”“brute-force” search:rate γ = 1

O⇤ (2 n ) ! O⇤ (2 2 n )m > 0.73n

Schöning:
rate γc“Quantum” Schöning:rate γq0

threshold1
ratio m/n

threshold effectother thresholds: speedup kicks in too late, e.g.

1015 ⇥ n 2 O(n) v.s. n2 2 O(n2 )Why? Problems have structure (except unstructured search)
How do you chop it up into chunks?

Can be avoided for some for certain classes of problems-if the algorithm does not use (too much) randomness-If the algorithm recursively calls itself or other sub-routines(like in dynamical programming)-If the subroutines do not depend on the original problem size

then we can use a “hybrid approach”:
use classical calls, until instance small enough!

SAT solving a-la Schöning…
1)

derandomized Schöning

r-partition assignment space into r-balls-solve PromiseBallSat for each→

PromiseBallSat(x,r)

NB: r will be a fraction of n

SAT solving a-la Schöning…
1) derandomized Schöning…
2) …reduces to PromiseBallSAT

→PromiseBallSat(x,r)
1. Start from x
2. Find first unsatisfied clause (or done!)
3. Recurse algorithm on flipping each of the three possibilities,
calling induced smaller formulaf(x1 , . . . , xn ) = C1 ^ C2 ^ · · · Ck ^ · · · CL
Ck = (u _ v _ w), u, v, w 2 {x1 , . . . , xn } [ {x̄1 , . . . , x̄n }Non-recursive version
select s1 , s2 , . . . , sr
Check every substring3rf(x1 , . . . , xn ) = (x1 _ x10 _ x̄51 ) ^ (x̄3 _ x̄10 _ x̄11 ) ^ (x̄11 _ x̄44 _ x̄51 ) · · ·

s1

f

s1

(1)

(1)

r

O(3 )

s

s2f fff ff .
.f. ff ..
f. f
sr
sr
(2)

Only flip ones not flipped previously

f
(1)
(2)
ff2

(3)

(2)
(3)

(3)
(1,1)

(1,1) (1,1)(1,2)(1,2) (1,2)

x1 f (1)x10
s(2)1
sf1
(3)
fs
2
2
fs(1,1)x3 (1,2) .x11
…f x10 .

.. .
.
sr

sr

f (1)

x

51
f (2)

f (3)
f (1,1)f (1,2)

Ck = (u _ v _ w), u, v, w 2 {x1 , . . . , xn } [ {x̄1 , . . . , x̄n }SAT solving a-la Schöning…

f(x1 , . . . , xn ) = (x1 _ x10 _ x̄51 ) ^ (x̄3 _ x̄10 _ x̄11 ) ^ (x̄11 _ x̄44 _ x̄51 ) · · ·1) derandomized Schöning…
2) …reduces to PromiseBallSAT…
3) …which recurses itself on smaller instance…

s1

s1

f (1)
f (1) ff(1)2(2)

ss2f fff ff .
.f. ff ..
f. f
sr
sr
(2)

(2)
(3)

(3)

(3)
(1,1)

(1,1) (1,1)(1,2)(1,2) (1,2)

f (1)

f (1)

s1

f (2)

(2)

f (3)

(3)

f (1,1)(1,1)

f (1,2)

sf1
fs 2
fs2
.
f
… . ..
..
sr
sr
(1,2)

k

SAT solving a-la Schöning…

1

n

1

n

f(x1 , . . . , xn ) = (x1 _ x10 _ x̄51 ) ^ (x̄3 _ x̄10 _ x̄11 ) ^ (x̄11 _ x̄44 _ x̄51 ) · · ·1) derandomized Schöning(n)…
2) …reduces to PromiseBallSAT(r)…
3) …which recurses itself on smaller r…

s1

s1

f (1)
f (1) ff(1)2(2)

ss2f fff ff .
.f. ff ..
f. f
sr
sr
(2)

(2)
(3)

(3)

(3)
(1,1)

(1,1) (1,1)(1,2)(1,2) (1,2)

f (1)

f (1)

s1

f (2)

(2)

f (3)

(3)

f (1,1)(1,1)

f (1,2)

sf1
fs 2
fs2
.
f
… . ..
..
sr
sr
(1,2)

the “hybrid approach” for PromiseBallSAT:
1)
2)

find a quantum implementation (QPBS) which is fast, and uses few qubits (ideally r)
Run recursive algorithm, call QPBS once r is small enoughHow fast the end result is depends on
how big a r we can handle given QC of size m

Critical: #needed qubits must not depend on initial size→
PromiseBallSat(x,r)→PromiseBallSatx(r)→Key observation: only carry r trits. Could be independent from n.
Only need to keep track of which bits to flip.
Only need 3 ancillas to check each clause sequentially

SAT solving a-la Schöning…
1)
2)
3)
4)

derandomized Schöning…
…reduces to PromiseBallSAT…
…which recurses itself on smaller instance…
…call size almost independent from n…

Is it n-independent enough?
Main step of algorithm: keeping track of flipped variables.

|s1 , . . . , sr i|V (k)i ! |s1 , . . . , sr i|V (k + 1)i|s1 , . . . ,tosr be
i|V flipped(k)i ! |s1 , . . . , sr i|V (k + 1)i) appended with (k + 1)st variable. , sr i|V(k)i|s1V, .(k). . , sappended
V (k
+!
1) =
with (k + 1)st variable to be flippedr i|V (k + 1)iwith (k + 1)st variable to be flipped

This is where the problem structure is exploited
Recall:-when m is limited, how big “r” we can handle influences when quantum speed-ups kick in-interesting cases when m/n is constantIs it n-independent enough? actually, non-triv…
Main step of algorithm: keeping track of flipped variables.

What is V? Ordered list, then O(r log(n))|s1 , . . . , sr i|V (k)i ! |s1 , . . . , sr i|V (k + 1)i|s1 , . . . ,tosr be
i|V flipped(k)i ! |s1 , . . . , sr i|V (k + 1)i) appended with (k + 1)st variable

Problem! Effective r we can handle
decays with log(n), when m/n is constant !

. , sr i|V(k)i|s1V, .(k). . , sappended
V (k
+!
1) =
with (k + 1)st variable to be flippedr i|V (k + 1)iwith (k + 1)st variable to be flippedIs it n-independent enough? actually, non-triv…
Main step of algorithm: keeping track of flipped variables.

What is V? Ordered list, then O(r log(n))|s1 , . . . , sr i|V (k)i ! |s1 , . . . , sr i|V (k + 1)i|s1 , . . . ,tosr be
i|V flipped(k)i ! |s1 , . . . , sr i|V (k + 1)i) appended with (k + 1)st variable

Problem! Effective r we can handle
decays with log(n), when m/n is constant !

. , sr i|V(k)i|s1V, .(k). . , sappended
V (k
+!
1) =
with (k + 1)st variable to be flippedr i|V (k + 1)iwith (k + 1)st variable to be flipped

If it is a set, need O(r log(n/r))

Now, this is an n-independent fraction!
Problem! Main step is no longer reversible!

Direct algorithmic deletion?
deletion recurses on r: exp(r) cost, no goSolution: special memory structure and algorithmic deletion
sets of r/2

sets of r/8

sets of r/16…
sets of r/4
log(r) depthFill k-th level:
1. Fill two k-1 levels
2. Join and copy to kth level
3. Delete two k-1 levels

Recursion of depth log(r),so in 2O(log(n)) 2 poly(n)Time AND memory efficient!

Solution: special memory structure and algorithmic deletion
sets of r/2

sets of r/8

sets of r/16…
sets of r/4
log(r) depthFill k-th level:
1. Fill two k-1 levels
2. Join and copy to kth level
3. Delete two k-1 levels

Means: given QC of size m s.t. m/n = const.
we can quantum-solve PromiseBall(r)where r/n is const.
Leads to true speedups.

Complete algorithm: combine fastest de-randomized Schöning, which speeds-up PromiseBall.

Total complexity:

⇤

O (2

( +" f (m/n))n)f (x) 2 ⇥(x/ log(1/x))

ε - can be made arbitrarily small
polynomial speedup!

Final statement: quantum enhancement for de-randomized Schöning’s algorithm of Moser & Scheder
improving for any constant ratio m/nHard problems use structure less… and this may be an advantage for near term devices
Combined with an “AI resiliencnt to noise”-type evidence
this provides further potential AI — QIP conspiracies.

Acknowledgements:

TaylorMelnikovBriegelWölk
Liu

theoreticalphysics

MakmalPoulsen Nautrup

Orsucci

Trenkwalder

Friis

Cirac

Ge

Wu

Thank you

75