ON THE LINEAR GROWTH OF

QUANTUM CIRCUIT COMPLEXITYJENS EISERT, FU BERLIN
With J. Haferkamp, P. Faist, N. Kothakonda, A. Munson, N. Yunger Halpern

Nature Physics 18, 528 (2022), Phys Rev A 106, 062417 (2022), Phys Rev Lett 127, 020501 (2021), Commun Math Phys (2022)

‣ High energy physics,
holography and thewormhole growth paradox‣ Quantum computing

QUANTUM CIRCUIT COMPLEXITY‣ Statistical physics andthermodynamics

‣ High energy physics,
holography and thewormhole growth paradox‣ Quantum computing

QUANTUM CIRCUIT COMPLEXITY‣ Statistical physics andthermodynamics‣ This talk

CIRCUIT AND STATE COMPLEXITY‣ Complexity is studied to make senseof the enormity of Hilbert space…

CIRCUIT AND STATE COMPLEXITY‣Circuit complexity of a computation captures the number of
elementary steps it minimally takes to determine its outcome‣ Separate computational tasks into ‘easy’ and ‘hard’CIRCUIT AND STATE COMPLEXITY‣Circuit complexity of a computation captures the number of
elementary steps it minimally takes to determine its outcome‣ Separate computational tasks into ‘easy’ and ‘hard’‣ In quantum setting relevant for phases of matter

CIRCUIT COMPLEXITY‣Circuit complexity of a computation captures the number of
elementary steps it minimally takes to determine its outcome‣

CIRCUIT COMPLEXITY‣Circuit complexity of a computation captures the number of
elementary steps it minimally takes to determine its outcome

NOTORIOUSLY HARD TO COMPUTECIRCUIT COMPLEXITY‣Circuit complexity of a computation captures the number of
elementary steps it minimally takes to determine its outcome‣

Gosset, Gosset, Kliuchnikov, Mosca, Russo, Quant Inf Comp 14, 1277 (2014)
Aaronson, Gottesman, Phys Rev A 70, 02328 (2004)‣Circuit lower bounds

STATES AND UNITARIES THROUGH THE GLASSES OF COMPLEXITY‣Circuit and state complexities organize unitaries and quantum states
Topological phases

Long time quantum
chaotic dynamics

Thermalization<latexit sha1_base64="jnSku69SOIMOL3mL1AJo5WlgAso=">AAAB63icbVBNSwMxEJ2tX7V+VT16CRahXsquFfVY8OLNCvYD2qVk02wbmmSXJCuUpX/BiwdFvPqHvPlvzLZ70NYHA4/3ZpiZF8ScaeO6305hbX1jc6u4XdrZ3ds/KB8etXWUKEJbJOKR6gZYU84kbRlmOO3GimIRcNoJJreZ33miSrNIPpppTH2BR5KFjGCTSfdV73xQrrg1dw60SrycVCBHc1D+6g8jkggqDeFY657nxsZPsTKMcDor9RNNY0wmeER7lkosqPbT+a0zdGaVIQojZUsaNFd/T6RYaD0Vge0U2Iz1speJ/3m9xIQ3fspknBgqyWJRmHBkIpQ9joZMUWL41BJMFLO3IjLGChNj4ynZELzll1dJ+6LmXdXqD5eVRiOPowgncApV8OAaGnAHTWgBgTE8wyu8OcJ5cd6dj0VrwclnjuEPnM8f306NeQ==</latexit><latexit sha1_base64="3D6yYj9ICMQmLqs21lT6g/IZeyE=">AAAB9HicbVBNSwMxEJ2tX7V+VT16CRahXsquinosePFYwX5Au5Rsmm1Ds8maZAvL0t/hxYMiXv0x3vw3pu0etPXBwOO9GWbmBTFn2rjut1NYW9/Y3Cpul3Z29/YPyodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDfz2xOqNJPi0aQx9SM8FCxkBBsr+VlPRSiWPJ1WxXm/XHFr7hxolXg5qUCORr/81RtIkkRUGMKx1l3PjY2fYWUY4XRa6iWaxpiM8ZB2LRU4otrP5kdP0ZlVBiiUypYwaK7+nshwpHUaBbYzwmakl72Z+J/XTUx462dMxImhgiwWhQlHRqJZAmjAFCWGp5Zgopi9FZERVpgYm1PJhuAtv7xKWhc177p2+XBVqdfzOIpwAqdQBQ9uoA730IAmEHiCZ3iFN2fivDjvzseiteDkM8fwB87nD2FOkdg=</latexit>

O(1)<latexit sha1_base64="g0eznMEo10d74rW0C0yr1Ps5tZk=">AAAB63icbVBNSwMxEJ2tX7V+VT16CRahXsquFfVY8OLNCvYD2qVk02wbmmSXJCuUpX/BiwdFvPqHvPlvzLZ70NYHA4/3ZpiZF8ScaeO6305hbX1jc6u4XdrZ3ds/KB8etXWUKEJbJOKR6gZYU84kbRlmOO3GimIRcNoJJreZ33miSrNIPpppTH2BR5KFjGCTSfdVeT4oV9yaOwdaJV5OKpCjOSh/9YcRSQSVhnCsdc9zY+OnWBlGOJ2V+ommMSYTPKI9SyUWVPvp/NYZOrPKEIWRsiUNmqu/J1IstJ6KwHYKbMZ62cvE/7xeYsIbP2UyTgyVZLEoTDgyEcoeR0OmKDF8agkmitlbERljhYmx8ZRsCN7yy6ukfVHzrmr1h8tKo5HHUYQTOIUqeHANDbiDJrSAwBie4RXeHOG8OO/Ox6K14OQzx/AHzucPPA6Ntg==</latexit>

O(n)<latexit sha1_base64="uHh0Ynszn/FGa3qBmLFnzu++XPA=">AAAB83icbVBNSwMxEM36WetX1aOXYBHqpeyqqMeCF48V7Ad0l5JNp21okg1JVixL/4YXD4p49c9489+YtnvQ1gcDj/dmmJkXK86M9f1vb2V1bX1js7BV3N7Z3dsvHRw2TZJqCg2a8ES3Y2KAMwkNyyyHttJARMyhFY9up37rEbRhiXywYwWRIAPJ+owS66QwC7XA8KQmFXnWLZX9qj8DXiZBTsooR71b+gp7CU0FSEs5MaYT+MpGGdGWUQ6TYpgaUISOyAA6jkoiwETZ7OYJPnVKD/cT7UpaPFN/T2REGDMWsesUxA7NojcV//M6qe3fRBmTKrUg6XxRP+XYJngaAO4xDdTysSOEauZuxXRINKHWxVR0IQSLLy+T5nk1uKpe3F+Wa7U8jgI6RieoggJ0jWroDtVRA1Gk0DN6RW9e6r14797HvHXFy2eO0B94nz+C35FX</latexit>

poly(n)exp(n)

Quantum states
Matrix productstates, GHZ states

ProductstatesMulti-scale
renormalization

Unitaries
Variational quantum
circuits, QAOA
Circuits forclassical shadows

Unitary k-designs
Polynomial
random circuits

Haar-random
unitaries

RANDOM QUANTUM CIRCUITS‣Random circuits: Proxies for quantum chaotic dynamics‣ Bricklayer circuits

L

Haar random gates

LT

Causal slice

RANDOM QUANTUM CIRCUITS‣Random circuits: Proxies for quantum chaotic dynamics‣ Bricklayer circuits, random arrangements

L

Haar random gates

LT

Causal slice

RANDOM QUANTUM CIRCUITS‣Random circuits: Proxies for quantum chaotic dynamics‣ Bricklayer circuits, random arrangements

L

Haar random gates

LT

Causal slice

RANDOM QUANTUM CIRCUITS‣Random circuits: Proxies for quantum chaotic dynamics‣ Bricklayer circuits, random arrangements

HOW DOES THE COMPLEXITY GROW?
L

Haar random gates

LT

Causal slice

HOLOGRAPHY‣Holographic context: Complexity growth of thermofield doubles
Haar random gates

R

R

R

T
Brown, Roberts, Susskind, Swingle, Zhao, Phys Rev Lett 116, 191301 (2016)
Brown, Roberts, Susskind, Swingle, Zhao, Phys Rev D 93, 086006 (2016)
Chapman, Eisert, Hackl, Heller, Jefferson, Marrochio, Myers, SciPost Phys 6, 034 (2019)
Brown, Susskind, Phys Rev D 97, 086015 (2018)

HOLOGRAPHY‣Holographic context: Wormhole-growth paradox‣ AdS: Volume grows for
exponentially long time

‣ CFT: Local observables
equilibrating?
| i<latexit sha1_base64="DdW3PNUYeMO3f9c4yrZqhXQMKPw=">AAAB83icbVBNS8NAEJ3Ur1q/qh69LBbBU0lU1JMUvHisYD+gCWWznbRLN5uwuxFK7d/w4kERr/4Zb/4bt20O2vpg4PHeDDPzwlRwbVz32ymsrK6tbxQ3S1vbO7t75f2Dpk4yxbDBEpGodkg1Ci6xYbgR2E4V0jgU2AqHt1O/9YhK80Q+mFGKQUz7kkecUWMl/8lPNfcVlX2B3XLFrbozkGXi5aQCOerd8pffS1gWozRMUK07npuaYEyV4UzgpORnGlPKhrSPHUsljVEH49nNE3JilR6JEmVLGjJTf0+Maaz1KA5tZ0zNQC96U/E/r5OZ6DoYc5lmBiWbL4oyQUxCpgGQHlfIjBhZQpni9lbCBlRRZmxMJRuCt/jyMmmeVb3L6vn9RaV2k8dRhCM4hlPw4ApqcAd1aACDFJ7hFd6czHlx3p2PeWvByWcO4Q+czx9to5Hv</latexit>

Brown, Roberts, Susskind, Swingle, Zhao, Phys Rev Lett 116, 191301 (2016)
Brown, Roberts, Susskind, Swingle, Zhao, Phys Rev D 93, 086006 (2016)
Chapman, Eisert, Hackl, Heller, Jefferson, Marrochio, Myers, SciPost Phys 6, 034 (2019)
Brown, Susskind, Phys Rev D 97, 086015 (2018)

BROWN SUSSKIND CONJECTURE FOR RANDOM QUANTUM CIRCUITS‣Brown-Susskind conjecture: Linear growth until exponential time
Haar random gates

THIS WOULD MEAN THAT ‘CANCELLATIONS’ACTUALLY HARDLY MATTER
R

R

R

T
Brown, Susskind, Phys Rev D 97, 086015 (2018)

BROWN SUSSKIND CONJECTURE FOR RANDOM QUANTUM CIRCUITSBUT HOW CAN THIS BE JUDGED?

Complexity
Dimension

BUT HOW CAN THIS BE JUDGED?

SKETCH OF THE PROOF

Contraction map

Accessible dimension

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension“Reachable set”
Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension*‣* U (A) is not a manifold, but a semialgebraic set,by virtue of Tarski-Seidenberg principle

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension*‣* U (A) is not a manifold, but a semialgebraic set,by virtue of Tarski-Seidenberg principle
A
F
Rank
of
in x important: Rank of a matrix that‣A
approximates F linearly around x
A
F
Prove
that
has the same rank throughout the‣domain, except on a measure-zero set
AHaferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension*‣* U (A) is not a manifold, but a semialgebraic set,by virtue of Tarski-Seidenberg principle
A
F
Rank
of
in x important: Rank of a matrix that‣A
approximates F linearly around x
A
F
Prove
that
has the same rank throughout the‣domain, except on a measure-zero set
AHaferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension*‣Identify an x where r grows linearly with R

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension*‣Identify an x where r grows linearly with R‣ Demonstrate the point’s existence by perturbing Clifford circuits,‘appending infinitesimal unitaries’, ‘count independent directions’Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF

Contraction map

Accessible dimension*

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF‣Elaborate counting

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF THE PROOF‣ Let R be less than a linear fraction of R :‣ For every R0 gate architecture A0,
′

0

holds

‣ Almost every U 2 U(AT ) has complexity greater than greatest
possible R0‣Elaborate counting (last step has been much simplified) Li, arXiv:2205.05668

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF‣ THE PROOF‣Elaborate counting (last step has been much simplified) Li, arXiv:2205.05668

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF‣ THE PROOF

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

SKETCH OF‣ THE PROOF

SO THERE IS A LINEAR COMPLEXITY GROWTH

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)

INTERLUDE: APPROXIMATEC NOTIONS? CONNECTIONSTO ENTANGLEMENT? TO UNITARY DESIGNS?

CONNECTION TO ENTANGLEMENT?

‣Fair resolution of the Brown-Susskind conjecture‣Approximate notions desirable: Approximate in k.k1 -norm<latexit sha1_base64="0uTX6PFSTK5xxYXdvo3bMk0ueN8=">AAAB83icbVBNS8NAEJ3Ur1q/qh69BIvgKSQq6rHgxWMF+wFNKJvtpl262YTdiVDS/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTAXX6LrfVmltfWNzq7xd2dnd2z+oHh61dJIpypo0EYnqhEQzwSVrIkfBOqliJA4Fa4eju5nffmJK80Q+4jhlQUwGkkecEjSS708cf9LzuYxw3KvWXMedw14lXkFqUKDRq375/YRmMZNIBdG667kpBjlRyKlg04qfaZYSOiID1jVUkpjpIJ/fPLXPjNK3o0SZkmjP1d8TOYm1Hseh6YwJDvWyNxP/87oZRrdBzmWaIZN0sSjKhI2JPQvA7nPFKIqxIYQqbm616ZAoQtHEVDEheMsvr5LWheNdO5cPV7V6vYijDCdwCufgwQ3U4R4a0AQKKTzDK7xZmfVivVsfi9aSVcwcwx9Ynz8ZipG7</latexit>

Haferkamp, Faist, Kothakonda, Eisert, Yunger-Halpern, Nature Physics 18, 528 (2022)
Bouland, Fefferman, Vazirani, arXiv:1910.14646
Brandão, Chemissany, Hunter-Jones, Kueng, Preskill, PRX Quantum 2, 030316 (2021)
Dowling, Nielsen, Quant Inf Comp 8, 861–899 (2008)

CONNECTION TO ENTANGLEMENT?

‣Fair resolution of the Brown-Susskind conjecture‣Approximate notions desirable: Approximate in k.k1 -norm<latexit sha1_base64="0uTX6PFSTK5xxYXdvo3bMk0ueN8=">AAAB83icbVBNS8NAEJ3Ur1q/qh69BIvgKSQq6rHgxWMF+wFNKJvtpl262YTdiVDS/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTAXX6LrfVmltfWNzq7xd2dnd2z+oHh61dJIpypo0EYnqhEQzwSVrIkfBOqliJA4Fa4eju5nffmJK80Q+4jhlQUwGkkecEjSS708cf9LzuYxw3KvWXMedw14lXkFqUKDRq375/YRmMZNIBdG667kpBjlRyKlg04qfaZYSOiID1jVUkpjpIJ/fPLXPjNK3o0SZkmjP1d8TOYm1Hseh6YwJDvWyNxP/87oZRrdBzmWaIZN0sSjKhI2JPQvA7nPFKIqxIYQqbm616ZAoQtHEVDEheMsvr5LWheNdO5cPV7V6vYijDCdwCufgwQ3U4R4a0AQKKTzDK7xZmfVivVsfi9aSVcwcwx9Ynz8ZipG7</latexit>‣Nielsen cost and entanglement
Write circuits as
integralZ
1

U = P exp

i

dt

0

X

yI (t)MII!

Cost (common l1 choice)
C := inf

Z 1X
0Theorem 2:C<latexit sha1_base64="QwGv7WCUXf4NhOArzQD69wNmGEI=">AAAB+nicbVDLSgNBEOyNrxhfGz16GQyChxB2VdRTCATBYwTzgOwSZiezyZDZhzOzSljzKV48KOLVL/Hm3zhJ9qCJBQ1FVTfdXV7MmVSW9W3kVlbX1jfym4Wt7Z3dPbO435JRIghtkohHouNhSTkLaVMxxWknFhQHHqdtb1Sf+u0HKiSLwjs1jqkb4EHIfEaw0lLPLNadAb1HBF2XkVNGpGr1zJJVsWZAy8TOSAkyNHrml9OPSBLQUBGOpezaVqzcFAvFCKeTgpNIGmMywgPa1TTEAZVuOjt9go610kd+JHSFCs3U3xMpDqQcB57uDLAaykVvKv7ndRPlX7kpC+NE0ZDMF/kJRypC0xxQnwlKFB9rgolg+lZEhlhgonRaBR2CvfjyMmmdVuyLytntealWzeLIwyEcwQnYcAk1uIEGNIHAIzzDK7wZT8aL8W58zFtzRjZzAH9gfP4AARuR4g==</latexit>I|yI (t)|ds

cE, c > 0

Eisert, Phys Rev Lett 127, 020501 (2021)

Compare Balasubramanian, DeCross, Kar, Parrikar, arXiv:1811.04085 (2018)
Susskind, arXiv:1411.0690 (2014)

UNITARY DESIGNS FROM CLIFFORD AND T-GATES‣Fair resolution of the Brown-Susskind conjecture‣Approximate notions desirable: Approximate in k.k1 -norm<latexit sha1_base64="0uTX6PFSTK5xxYXdvo3bMk0ueN8=">AAAB83icbVBNS8NAEJ3Ur1q/qh69BIvgKSQq6rHgxWMF+wFNKJvtpl262YTdiVDS/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTAXX6LrfVmltfWNzq7xd2dnd2z+oHh61dJIpypo0EYnqhEQzwSVrIkfBOqliJA4Fa4eju5nffmJK80Q+4jhlQUwGkkecEjSS708cf9LzuYxw3KvWXMedw14lXkFqUKDRq375/YRmMZNIBdG667kpBjlRyKlg04qfaZYSOiID1jVUkpjpIJ/fPLXPjNK3o0SZkmjP1d8TOYm1Hseh6YwJDvWyNxP/87oZRrdBzmWaIZN0sSjKhI2JPQvA7nPFKIqxIYQqbm616ZAoQtHEVDEheMsvr5LWheNdO5cPV7V6vYijDCdwCufgwQ3U4R4a0AQKKTzDK7xZmfVivVsfi9aSVcwcwx9Ynz8ZipG7</latexit>‣Unitary designs: The generation of unitary t-designs at a depth O(nt)would imply the approximate Brown-Susskind conjecture<latexit sha1_base64="9h1TkWq6jhMFlKNptotoKMD3IGU=">AAAB7HicbVBNS8NAEJ34WetX1aOXxSLUS0lU1GPBizcr2A9oQ9lsN+3SzSbsToQS+hu8eFDEqz/Im//GbZuDtj4YeLw3w8y8IJHCoOt+Oyura+sbm4Wt4vbO7t5+6eCwaeJUM95gsYx1O6CGS6F4AwVK3k40p1EgeSsY3U791hPXRsTqEccJ9yM6UCIUjKKVGvcVhWe9UtmtujOQZeLlpAw56r3SV7cfszTiCpmkxnQ8N0E/oxoFk3xS7KaGJ5SN6IB3LFU04sbPZsdOyKlV+iSMtS2FZKb+nshoZMw4CmxnRHFoFr2p+J/XSTG88TOhkhS5YvNFYSoJxmT6OekLzRnKsSWUaWFvJWxINWVo8ynaELzFl5dJ87zqXVUvHi7LtVoeRwGO4QQq4ME11OAO6tAABgKe4RXeHOW8OO/Ox7x1xclnjuAPnM8fEjCONA==</latexit>

HOW CAN UNITARY DESIGNS BE IMPLEMENTED?

Brandão, Chemissany, Hunter-Jones, Kueng, Preskill, PRX Quantum 2, 030316 (2021)
Brandao, Harrow, Horodecki, Phys Rev Lett 116, 170502 (2016)

Clifford
circuits
unitary 3-designs
UNITARY DESIGNSFROMCLIFFORD
AND areT-GATES‣RandomT-gatesupliftthentoarbitraryorder
designs*‣‣Fair resolution of the Brown-Susskind conjecture<latexit sha1_base64="UmWhLyRkySwkpG9S6JfvmMYEnQM=">AAAB6HicbVDLSgNBEOyNrxhfUY9eBoPgKeyqqCcJePGYQF6QLGF20puMmZ1dZmaFEPIFXjwo4tVP8ubfOEn2oIkFDUVVN91dQSK4Nq777eTW1jc2t/LbhZ3dvf2D4uFRU8epYthgsYhVO6AaBZfYMNwIbCcKaRQIbAWj+5nfekKleSzrZpygH9GB5CFn1FipVu8VS27ZnYOsEi8jJchQ7RW/uv2YpRFKwwTVuuO5ifEnVBnOBE4L3VRjQtmIDrBjqaQRan8yP3RKzqzSJ2GsbElD5urviQmNtB5Hge2MqBnqZW8m/ud1UhPe+hMuk9SgZItFYSqIicnsa9LnCpkRY0soU9zeStiQKsqMzaZgQ/CWX14lzYuyd12+rF2VKndZHHk4gVM4Bw9uoAIPUIUGMEB4hld4cx6dF+fd+Vi05pxs5hj+wPn8AbERjNw=</latexit>‣Approximate notions desirable: Approximate in k.k1 -norm<latexit sha1_base64="0uTX6PFSTK5xxYXdvo3bMk0ueN8=">AAAB83icbVBNS8NAEJ3Ur1q/qh69BIvgKSQq6rHgxWMF+wFNKJvtpl262YTdiVDS/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTAXX6LrfVmltfWNzq7xd2dnd2z+oHh61dJIpypo0EYnqhEQzwSVrIkfBOqliJA4Fa4eju5nffmJK80Q+4jhlQUwGkkecEjSS708cf9LzuYxw3KvWXMedw14lXkFqUKDRq375/YRmMZNIBdG667kpBjlRyKlg04qfaZYSOiID1jVUkpjpIJ/fPLXPjNK3o0SZkmjP1d8TOYm1Hseh6YwJDvWyNxP/87oZRrdBzmWaIZN0sSjKhI2JPQvA7nPFKIqxIYQqbm616ZAoQtHEVDEheMsvr5LWheNdO5cPV7V6vYijDCdwCufgwQ3U4R4a0AQKKTzDK7xZmfVivVsfi9aSVcwcwx9Ynz8ZipG7</latexit>‣Unitary designs: The generation of unitary t-designs at a depth O(nt)would imply the approximate Brown-Susskind conjecture<latexit sha1_base64="9h1TkWq6jhMFlKNptotoKMD3IGU=">AAAB7HicbVBNS8NAEJ34WetX1aOXxSLUS0lU1GPBizcr2A9oQ9lsN+3SzSbsToQS+hu8eFDEqz/Im//GbZuDtj4YeLw3w8y8IJHCoOt+Oyura+sbm4Wt4vbO7t5+6eCwaeJUM95gsYx1O6CGS6F4AwVK3k40p1EgeSsY3U791hPXRsTqEccJ9yM6UCIUjKKVGvcVhWe9UtmtujOQZeLlpAw56r3SV7cfszTiCpmkxnQ8N0E/oxoFk3xS7KaGJ5SN6IB3LFU04sbPZsdOyKlV+iSMtS2FZKb+nshoZMw4CmxnRHFoFr2p+J/XSTG88TOhkhS5YvNFYSoJxmT6OekLzRnKsSWUaWFvJWxINWVo8ynaELzFl5dJ87zqXVUvHi7LtVoeRwGO4QQq4ME11OAO6tAABgKe4RXeHOW8OO/Ox7x1xclnjuAPnM8fEjCONA==</latexit>*In approximate sense
Brandão, Chemissany, Hunter-Jones, Kueng, Preskill, PRX Quantum 2, 030316 (2021)
Brandao, Harrow, Horodecki, Phys Rev Lett 116, 170502 (2016)

Clifford
circuits
unitary 3-designs
UNITARY DESIGNSFROMCLIFFORD
AND areT-GATES‣RandomT-gatesupliftthentoarbitraryorder
designs*‣‣Fair resolution of the Brown-Susskind conjecture<latexit sha1_base64="UmWhLyRkySwkpG9S6JfvmMYEnQM=">AAAB6HicbVDLSgNBEOyNrxhfUY9eBoPgKeyqqCcJePGYQF6QLGF20puMmZ1dZmaFEPIFXjwo4tVP8ubfOEn2oIkFDUVVN91dQSK4Nq777eTW1jc2t/LbhZ3dvf2D4uFRU8epYthgsYhVO6AaBZfYMNwIbCcKaRQIbAWj+5nfekKleSzrZpygH9GB5CFn1FipVu8VS27ZnYOsEi8jJchQ7RW/uv2YpRFKwwTVuuO5ifEnVBnOBE4L3VRjQtmIDrBjqaQRan8yP3RKzqzSJ2GsbElD5urviQmNtB5Hge2MqBnqZW8m/ud1UhPe+hMuk9SgZItFYSqIicnsa9LnCpkRY0soU9zeStiQKsqMzaZgQ/CWX14lzYuyd12+rF2VKndZHHk4gVM4Bw9uoAIPUIUGMEB4hld4cx6dF+fd+Vi05pxs5hj+wPn8AbERjNw=</latexit>

notions desirable: Approximate in k.k1 -norm‣Approximate‣Theorem 3: A constant (!) number of T -gates is sufficientO(nt)Thegenerationof
unitary
t-designs
at
a
depth
‣Unitary designs:
Haferkamp, Montaelegre-Mora, Heinrich, Eisert, Gross, Roth, Comm Math Phys (2022)
arXiv:2002.09524(2022)
would imply theapproximate
Brown-Susskind conjecture<latexit sha1_base64="0uTX6PFSTK5xxYXdvo3bMk0ueN8=">AAAB83icbVBNS8NAEJ3Ur1q/qh69BIvgKSQq6rHgxWMF+wFNKJvtpl262YTdiVDS/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTAXX6LrfVmltfWNzq7xd2dnd2z+oHh61dJIpypo0EYnqhEQzwSVrIkfBOqliJA4Fa4eju5nffmJK80Q+4jhlQUwGkkecEjSS708cf9LzuYxw3KvWXMedw14lXkFqUKDRq375/YRmMZNIBdG667kpBjlRyKlg04qfaZYSOiID1jVUkpjpIJ/fPLXPjNK3o0SZkmjP1d8TOYm1Hseh6YwJDvWyNxP/87oZRrdBzmWaIZN0sSjKhI2JPQvA7nPFKIqxIYQqbm616ZAoQtHEVDEheMsvr5LWheNdO5cPV7V6vYijDCdwCufgwQ3U4R4a0AQKKTzDK7xZmfVivVsfi9aSVcwcwx9Ynz8ZipG7</latexit><latexit sha1_base64="UmWhLyRkySwkpG9S6JfvmMYEnQM=">AAAB6HicbVDLSgNBEOyNrxhfUY9eBoPgKeyqqCcJePGYQF6QLGF20puMmZ1dZmaFEPIFXjwo4tVP8ubfOEn2oIkFDUVVN91dQSK4Nq777eTW1jc2t/LbhZ3dvf2D4uFRU8epYthgsYhVO6AaBZfYMNwIbCcKaRQIbAWj+5nfekKleSzrZpygH9GB5CFn1FipVu8VS27ZnYOsEi8jJchQ7RW/uv2YpRFKwwTVuuO5ifEnVBnOBE4L3VRjQtmIDrBjqaQRan8yP3RKzqzSJ2GsbElD5urviQmNtB5Hge2MqBnqZW8m/ud1UhPe+hMuk9SgZItFYSqIicnsa9LnCpkRY0soU9zeStiQKsqMzaZgQ/CWX14lzYuyd12+rF2VKndZHHk4gVM4Bw9uoAIPUIUGMEB4hld4cx6dF+fd+Vi05pxs5hj+wPn8AbERjNw=</latexit><latexit sha1_base64="9h1TkWq6jhMFlKNptotoKMD3IGU=">AAAB7HicbVBNS8NAEJ34WetX1aOXxSLUS0lU1GPBizcr2A9oQ9lsN+3SzSbsToQS+hu8eFDEqz/Im//GbZuDtj4YeLw3w8y8IJHCoOt+Oyura+sbm4Wt4vbO7t5+6eCwaeJUM95gsYx1O6CGS6F4AwVK3k40p1EgeSsY3U791hPXRsTqEccJ9yM6UCIUjKKVGvcVhWe9UtmtujOQZeLlpAw56r3SV7cfszTiCpmkxnQ8N0E/oxoFk3xS7KaGJ5SN6IB3LFU04sbPZsdOyKlV+iSMtS2FZKb+nshoZMw4CmxnRHFoFr2p+J/XSTG88TOhkhS5YvNFYSoJxmT6OekLzRnKsSWUaWFvJWxINWVo8ynaELzFl5dJ87zqXVUvHi7LtVoeRwGO4QQq4ME11OAO6tAABgKe4RXeHOW8OO/Ox7x1xclnjuAPnM8fEjCONA==</latexit>

Compare also Zhou, Yang, Hamma, Chamon, arXiv:1906.01079

Brandão, Chemissany, Hunter-Jones, Kueng, Preskill, PRX Quantum 2, 030316 (2021)
Brandao, Harrow, Horodecki, Phys Rev Lett 116, 170502 (2016)

WHAT ARE THERMODYNAMICIMPLICATIONS?
CANACRESOURCE THEORY OF UNCOMPLEXITY BE DEFINED?

THINKING IN OPERATIONAL TERMSHOW CAN COMPLEXITY CAPTURE WHAT WE
CAN DO OPERATIONALLY TO A SYSTEM?

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)

THINKING IN OPERATIONAL TERMS

Low complexity
pure states

Complexity

THINKING IN OPERATIONAL TERMS

Low complexity
pure states‣ Second law ofcomplexity?
Brown, Susskind, Phys Rev D 97,
086015 (2018)

Complexity

THINKING IN OPERATIONAL TERMS

Entropy?
Low complexity
pure states‣ Second law ofcomplexity?
Brown, Susskind, Phys Rev D 97,
086015 (2018)

Complexity

THINKING IN OPERATIONAL TERMS‣ What processes can be performed
by a macroscopic observer?

Entropy‣ Second law ofthermodynamics

Low complexity
pure states?
‣ Second law ofcomplexity?
Brown, Susskind, Phys Rev D 97,
086015 (2018)

Complexity

THINKING IN OPERATIONAL TERMS‣ What processes can be performed
by a macroscopic observer?

Entropy‣ Second law ofthermodynamics

Low complexity
pure states?

‣ How can computational resources
to carry out a process be captured?

‣ Second law ofcomplexity?
Brown, Susskind, Phys Rev D 97,
086015 (2018)

Complexity

LANDAUER ERASURE‣Landauer erasure resetting a collection of quantum systems|0i|0i
Reset register
|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>?

<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>?

<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>?

<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>?

<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>?

Erasure requires
thermodynamic workkT log(2) per bit discarded in environment at temperature T<latexit sha1_base64="BeoJNbT4Q96zt2aVXjHWXAUlHHk=">AAAB8XicbVBNSwMxEJ2tX7V+VT16CRahXspuK+qx4MVjhX5hu5Rsmm1Ds8mSZIWy9F948aCIV/+NN/+NabsHbX0w8Hhvhpl5QcyZNq777eQ2Nre2d/K7hb39g8Oj4vFJW8tEEdoikkvVDbCmnAnaMsxw2o0VxVHAaSeY3M39zhNVmknRNNOY+hEeCRYygo2VHidN1OdyVK5eDoolt+IugNaJl5ESZGgMil/9oSRJRIUhHGvd89zY+ClWhhFOZ4V+ommMyQSPaM9SgSOq/XRx8QxdWGWIQqlsCYMW6u+JFEdaT6PAdkbYjPWqNxf/83qJCW/9lIk4MVSQ5aIw4chINH8fDZmixPCpJZgoZm9FZIwVJsaGVLAheKsvr5N2teJdV2oPV6V6PYsjD2dwDmXw4AbqcA8NaAEBAc/wCm+Odl6cd+dj2ZpzsplT+APn8wcZ+4/k</latexit><latexit sha1_base64="8ZIweZ4n1CULXw0IrCn4+cFHF9s=">AAAB6HicbVBNS8NAEJ34WetX1aOXxSJ4KomKeix48dhCv6ANZbOdtGs3m7C7EUroL/DiQRGv/iRv/hu3bQ7a+mDg8d4MM/OCRHBtXPfbWVvf2NzaLuwUd/f2Dw5LR8ctHaeKYZPFIladgGoUXGLTcCOwkyikUSCwHYzvZ377CZXmsWyYSYJ+RIeSh5xRY6V6o18quxV3DrJKvJyUIUetX/rqDWKWRigNE1Trrucmxs+oMpwJnBZ7qcaEsjEdYtdSSSPUfjY/dErOrTIgYaxsSUPm6u+JjEZaT6LAdkbUjPSyNxP/87qpCe/8jMskNSjZYlGYCmJiMvuaDLhCZsTEEsoUt7cSNqKKMmOzKdoQvOWXV0nrsuLdVK7q1+VqNY+jAKdwBhfgwS1U4QFq0AQGCM/wCm/Oo/PivDsfi9Y1J585gT9wPn8AsauM3g==</latexit>

Landauer, IBM J Res Dev 5, 183 (2015)
Bennett, Stud Hist Phil Mod Phys 34, 501 (2003)
Reeb, Wolf, New J Phys 16, 103011 (2014)

LANDAUER ERASURE‣Landauer erasure resetting a collection of quantum systems|0i|0i
Reset register
|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>

Schumacher
compression⇢<latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>

kT log(2)H 1 ✏ (⇢) total work cost<latexit sha1_base64="ZXUu/JsehW2qbgV6bHIRSZ0j8Q8=">AAACCHicbVC7SgNBFJ31GeNr1dLCwSAkhWE3iloGbFJGyAuya5idzCZDZmeWmVkhLClt/BUbC0Vs/QQ7/8ZJsoUmHrhwOOde7r0niBlV2nG+rZXVtfWNzdxWfntnd2/fPjhsKZFITJpYMCE7AVKEUU6ammpGOrEkKAoYaQej26nffiBSUcEbehwTP0IDTkOKkTZSzz4ZNaDHxKBYKcHafeqeeyRWlAk+KXpyKEo9u+CUnRngMnEzUgAZ6j37y+sLnESEa8yQUl3XibWfIqkpZmSS9xJFYoRHaEC6hnIUEeWns0cm8MwofRgKaYprOFN/T6QoUmocBaYzQnqoFr2p+J/XTXR446eUx4kmHM8XhQmDWsBpKrBPJcGajQ1BWFJzK8RDJBHWJru8CcFdfHmZtCpl96p8cXdZqFazOHLgGJyCInDBNaiCGqiDJsDgETyDV/BmPVkv1rv1MW9dsbKZI/AH1ucPXbqYTw==</latexit>

Brandao, Horodecki, Oppenheim, Renes, Spekkens, Phys Rev Lett 111, 250404 (2013)
Faist, Dupuis, Oppenheim Renner, Nature Comm 6, 7669 (2015)

LANDAUER ERASURE‣Start from high complexity pure state|0i|0i
Reset register
|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>| i<latexit sha1_base64="vskFdwgCtCwyc5pNV0oFxNG+D3Y=">AAAB83icbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMFWwtNKJvtpF262Sy7G6HE/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvkpxp43nfTmlldW19o7xZ2dre2d2r7h+0dZopii2a8lR1IqKRM4EtwwzHjlRIkojjQzS6mfoPj6g0S8W9GUsMEzIQLGaUGCsFT4HULFBEDDj2qjWv7s3gLhO/IDUo0OxVv4J+SrMEhaGcaN31PWnCnCjDKMdJJcg0SkJHZIBdSwVJUIf57OaJe2KVvhunypYw7kz9PZGTROtxEtnOhJihXvSm4n9eNzPxdZgzITODgs4XxRl3TepOA3D7TCE1fGwJoYrZW106JIpQY2Oq2BD8xZeXSfus7l/Wz+8uao1GEUcZjuAYTsGHK2jALTShBRQkPMMrvDmZ8+K8Ox/z1pJTzBzCHzifP249kfE=</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>

Reset using Landauer
erasure at little complexity

Uncompute at no work
cost, but at high complexity

SUGGESTS TRADE-OFF
Brandao, Horodecki, Oppenheim, Renes, Spekkens, Phys Rev Lett 111, 250404 (2013)
Faist, Dupuis, Oppenheim Renner, Nature Comm 6, 7669 (2015)

COMPLEXITY-RESTRICTED ERASURE‣Allow for at most r quantum gates
Reset using
Landauer erasure⇢<latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit>|0i|0i k to be maximized|0i<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates

OPERATIONAL INTERPRETATION: AMOUNT OF WORK REQUIRED TORESET A STATE FOR AN AGENT THAT CAN DO AT MOST R GATES<latexit sha1_base64="IvtZBhbfgj3ozFCjMyRnx9T2Ovk=">AAACE3icbVDLSgMxFM3UV62vUZdugkWoYsuMiroRCm66rGAf0BmHTJq2oZlkSDJCGfoPbvwVNy4UcevGnX9j2s5CqwcuHM65l3vvCWNGlXacLyu3sLi0vJJfLaytb2xu2ds7TSUSiUkDCyZkO0SKMMpJQ1PNSDuWBEUhI61weD3xW/dEKir4rR7FxI9Qn9MexUgbKbCPhkHqyQiKWI/hFeSwDGvB4C6Vx27ZI7GiTPBxyZMDcRjYRafiTAH/EjcjRZChHtifXlfgJCJcY4aU6rhOrP0USU0xI+OClygSIzxEfdIxlKOIKD+d/jSGB0bpwp6QpriGU/XnRIoipUZRaDojpAdq3puI/3mdRPcu/ZTyONGE49miXsKgFnASEOxSSbBmI0MQltTcCvEASYS1ibFgQnDnX/5LmicV97xyenNWrFazOPJgD+yDEnDBBaiCGqiDBsDgATyBF/BqPVrP1pv1PmvNWdnMLvgF6+Mbrcqcyg==</latexit>‣ Theorem 4: kopt = n

r,1 ✏
Hh
(⇢)

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)
Brandao, Datta, IEEE Trans Inf Th 57,1754 (2011)

quantity that accounts for complexity
COMPLEXITY-RESTRICTED‣A new entropyERASURE
r,⌘
H
gates minh (⇢) = log‣Allow for at most r quantum<latexit sha1_base64="4ZLrVFWnnSb18qwbBAXOVIbcIYg=">AAACL3icbVBdSxtBFJ31o2pq29Q++jIYhAgl7FqxfREChZJHA0aFbLrMTm6SwflYZ+4WwrL/yJf+lbyIKOKr/8JJjODXgYHDOedy5540k8JhGF4FC4tLyx9WVtcqH9c/ff5S/bpx7ExuOXS4kcaepsyBFBo6KFDCaWaBqVTCSXr2e+qf/APrhNFHOM6gp9hQi4HgDL2UVP+0ktHfwn6PAVlZj+3I7NADGkszjJXQSVHEVlG0Zb098+IhnNNplpb0yaL19k5SrYWNcAb6lkRzUiNzHCbVSdw3PFegkUvmXDcKM+wVzKLgEspKnDvIGD9jQ+h6qpkC1ytm95Z02yt9OjDWP410pj6fKJhybqxSn1QMR+61NxXf87o5Dn71CqGzHEHzx0WDXFI0dFoe7QsLHOXYE8at8H+lfMQs4+grrvgSotcnvyXHu41ov/GjvVdrNud1rJJNskXqJCI/SZO0yCHpEE4uyIRck5vgf3AZ3AZ3j9GFYD7zjbxAcP8AgAuoGA==</latexit>tr(Q⇢) ⌘
Q2Mr

tr(Q)

<latexit sha1_base64="DTGOB/J3pyfXFP1Kt/JUtckjXeE=">AAAB+HicbVBNS8NAEJ34WetHox69LBbBg5RERT0WvHgRWrAf0ISw2W7bpZtN2N0INeSXePGgiFd/ijf/jds2B219MPB4b4aZeWHCmdKO822trK6tb2yWtsrbO7t7FXv/oK3iVBLaIjGPZTfEinImaEszzWk3kRRHIaedcHw79TuPVCoWiwc9Sagf4aFgA0awNlJgVzLvLA+ypscEug9kHthVp+bMgJaJW5AqFGgE9pfXj0kaUaEJx0r1XCfRfoalZoTTvOyliiaYjPGQ9gwVOKLKz2aH5+jEKH00iKUpodFM/T2R4UipSRSazgjrkVr0puJ/Xi/Vgxs/YyJJNRVkvmiQcqRjNE0B9ZmkRPOJIZhIZm5FZIQlJtpkVTYhuIsvL5P2ec29ql00L6v1ehFHCY7gGE7BhWuowx00oAUEUniGV3iznqwX6936mLeuWMXMIfyB9fkDUuSS4A==</latexit>

How mixedmust Q be?

|0i Reset using
POVMs with at|0i Landauer erasure most complexity r
captures most of ⇢|0i
|0i k to be maximized<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>⇢<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit><latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>|0i<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates<latexit sha1_base64="IvtZBhbfgj3ozFCjMyRnx9T2Ovk=">AAACE3icbVDLSgMxFM3UV62vUZdugkWoYsuMiroRCm66rGAf0BmHTJq2oZlkSDJCGfoPbvwVNy4UcevGnX9j2s5CqwcuHM65l3vvCWNGlXacLyu3sLi0vJJfLaytb2xu2ds7TSUSiUkDCyZkO0SKMMpJQ1PNSDuWBEUhI61weD3xW/dEKir4rR7FxI9Qn9MexUgbKbCPhkHqyQiKWI/hFeSwDGvB4C6Vx27ZI7GiTPBxyZMDcRjYRafiTAH/EjcjRZChHtifXlfgJCJcY4aU6rhOrP0USU0xI+OClygSIzxEfdIxlKOIKD+d/jSGB0bpwp6QpriGU/XnRIoipUZRaDojpAdq3puI/3mdRPcu/ZTyONGE49miXsKgFnASEOxSSbBmI0MQltTcCvEASYS1ibFgQnDnX/5LmicV97xyenNWrFazOPJgD+yDEnDBBaiCGqiDBsDgATyBF/BqPVrP1pv1PmvNWdnMLvgF6+Mbrcqcyg==</latexit>‣ Theorem 4: kopt = n

r,1 ✏
Hh
(⇢)

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)
Brandao, Datta, IEEE Trans Inf Th 57,1754 (2011)

quantity that accounts for complexity
COMPLEXITY-RESTRICTED‣A new entropyERASURE
r,⌘
H
gates minh (⇢) = log‣Allow for at most r quantum<latexit sha1_base64="4ZLrVFWnnSb18qwbBAXOVIbcIYg=">AAACL3icbVBdSxtBFJ31o2pq29Q++jIYhAgl7FqxfREChZJHA0aFbLrMTm6SwflYZ+4WwrL/yJf+lbyIKOKr/8JJjODXgYHDOedy5540k8JhGF4FC4tLyx9WVtcqH9c/ff5S/bpx7ExuOXS4kcaepsyBFBo6KFDCaWaBqVTCSXr2e+qf/APrhNFHOM6gp9hQi4HgDL2UVP+0ktHfwn6PAVlZj+3I7NADGkszjJXQSVHEVlG0Zb098+IhnNNplpb0yaL19k5SrYWNcAb6lkRzUiNzHCbVSdw3PFegkUvmXDcKM+wVzKLgEspKnDvIGD9jQ+h6qpkC1ytm95Z02yt9OjDWP410pj6fKJhybqxSn1QMR+61NxXf87o5Dn71CqGzHEHzx0WDXFI0dFoe7QsLHOXYE8at8H+lfMQs4+grrvgSotcnvyXHu41ov/GjvVdrNud1rJJNskXqJCI/SZO0yCHpEE4uyIRck5vgf3AZ3AZ3j9GFYD7zjbxAcP8AgAuoGA==</latexit>tr(Q⇢) ⌘Q2Mr

How mixedmust Q be?

tr(Q)<latexit sha1_base64="DTGOB/J3pyfXFP1Kt/JUtckjXeE=">AAAB+HicbVBNS8NAEJ34WetHox69LBbBg5RERT0WvHgRWrAf0ISw2W7bpZtN2N0INeSXePGgiFd/ijf/jds2B219MPB4b4aZeWHCmdKO822trK6tb2yWtsrbO7t7FXv/oK3iVBLaIjGPZTfEinImaEszzWk3kRRHIaedcHw79TuPVCoWiwc9Sagf4aFgA0awNlJgVzLvLA+ypscEug9kHthVp+bMgJaJW5AqFGgE9pfXj0kaUaEJx0r1XCfRfoalZoTTvOyliiaYjPGQ9gwVOKLKz2aH5+jEKH00iKUpodFM/T2R4UipSRSazgjrkVr0puJ/Xi/Vgxs/YyJJNRVkvmiQcqRjNE0B9ZmkRPOJIZhIZm5FZIQlJtpkVTYhuIsvL5P2ec29ql00L6v1ehFHCY7gGE7BhWuowx00oAUEUniGV3iznqwX6936mLeuWMXMIfyB9fkDUuSS4A==</latexit>|0i Reset using
POVMs with at|0i Landauer erasure most complexity r
captures most of ⇢|0i
hypothesis
entropy‣ Variant of |0i
k to betesting
maximized‣ Monotonous|0iin r, ⌘<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>⇢<latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="XtqVGFCf8rstq6wC5d0PdLJm3XU=">AAAB7XicbVBNS8NAEJ3Ur1q/qh69LBbBg5RERT0WvHisYD+gDWWz3bRrN9mwOxFK6H/w4kERr/4fb/4bt20O2vpg4PHeDDPzgkQKg6777RRWVtfWN4qbpa3tnd298v5B06hUM95gSirdDqjhUsS8gQIlbyea0yiQvBWMbqd+64lrI1T8gOOE+xEdxCIUjKKVmvqsy5H2yhW36s5AlomXkwrkqPfKX92+YmnEY2SSGtPx3AT9jGoUTPJJqZsanlA2ogPesTSmETd+Nrt2Qk6s0ieh0rZiJDP190RGI2PGUWA7I4pDs+hNxf+8TorhjZ+JOEmRx2y+KEwlQUWmr5O+0JyhHFtCmRb2VsKGVFOGNqCSDcFbfHmZNM+r3lX14v6yUqvlcRThCI7hFDy4hhrcQR0awOARnuEV3hzlvDjvzse8teDkM4fwB87nD0crjvA=</latexit>r gates

Appears highly mixed at thiscomplexity scale - high Landauer costHh⌘ (⇢)<latexit sha1_base64="CBUF6vOE0GWPXdQR3est/Tp/vIA=">AAAB+XicbVDLSsNAFJ3UV62vqEs3g0Wom5KoqMuimy4r2Ac0MUymk2boZCbMTAol9E/cuFDErX/izr9x2mahrQcuHM65l3vvCVNGlXacb6u0tr6xuVXeruzs7u0f2IdHHSUyiUkbCyZkL0SKMMpJW1PNSC+VBCUhI91wdD/zu2MiFRX8UU9S4idoyGlEMdJGCmy7GcRPuUc0mtY8GYvzwK46dWcOuErcglRBgVZgf3kDgbOEcI0ZUqrvOqn2cyQ1xYxMK16mSIrwCA1J31COEqL8fH75FJ4ZZQAjIU1xDefq74kcJUpNktB0JkjHatmbif95/UxHt35OeZppwvFiUZQxqAWcxQAHVBKs2cQQhCU1t0IcI4mwNmFVTAju8surpHNRd6/rlw9X1cZdEUcZnIBTUAMuuAEN0AQt0AYYjMEzeAVvVm69WO/Wx6K1ZBUzx+APrM8fBHmTRA==</latexit>

r!1<latexit sha1_base64="NRk9N+zm7gmldjSzMN+6QP6yS6I=">AAAB+3icbVBNS8NAEN34WetXrEcvi0XwVBIV9Vjw4rGC/YAmlM120y7d7IbdiVpC/4oXD4p49Y9489+4bXPQ1gcDj/dmmJkXpYIb8LxvZ2V1bX1js7RV3t7Z3dt3DyotozJNWZMqoXQnIoYJLlkTOAjWSTUjSSRYOxrdTP32A9OGK3kP45SFCRlIHnNKwEo9t6IDzQdDIFqrx4DLGMY9t+rVvBnwMvELUkUFGj33K+grmiVMAhXEmK7vpRDmRAOngk3KQWZYSuiIDFjXUkkSZsJ8dvsEn1ilj2OlbUnAM/X3RE4SY8ZJZDsTAkOz6E3F/7xuBvF1mHOZZsAknS+KM4FB4WkQuM81oyDGlhCqub0V0yHRhIKNq2xD8BdfXiats5p/WTu/u6jW60UcJXSEjtEp8tEVqqNb1EBNRNETekav6M2ZOC/Ou/Mxb11xiplD9AfO5w/pZZUC</latexit>

Low Landauer cost

‣ Not unitarily invariant<latexit sha1_base64="IvtZBhbfgj3ozFCjMyRnx9T2Ovk=">AAACE3icbVDLSgMxFM3UV62vUZdugkWoYsuMiroRCm66rGAf0BmHTJq2oZlkSDJCGfoPbvwVNy4UcevGnX9j2s5CqwcuHM65l3vvCWNGlXacLyu3sLi0vJJfLaytb2xu2ds7TSUSiUkDCyZkO0SKMMpJQ1PNSDuWBEUhI61weD3xW/dEKir4rR7FxI9Qn9MexUgbKbCPhkHqyQiKWI/hFeSwDGvB4C6Vx27ZI7GiTPBxyZMDcRjYRafiTAH/EjcjRZChHtifXlfgJCJcY4aU6rhOrP0USU0xI+OClygSIzxEfdIxlKOIKD+d/jSGB0bpwp6QpriGU/XnRIoipUZRaDojpAdq3puI/3mdRPcu/ZTyONGE49miXsKgFnASEOxSSbBmI0MQltTcCvEASYS1ibFgQnDnX/5LmicV97xyenNWrFazOPJgD+yDEnDBBaiCGqiDBsDgATyBF/BqPVrP1pv1PmvNWdnMLvgF6+Mbrcqcyg==</latexit>‣ Theorem 4: kopt = n

r,1 ✏
Hh
(⇢)

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)
Brandao, Datta, IEEE Trans Inf Th 57,1754 (2011)

STEPS TOWARDS A RESOURCE THEORY OF UNCOMPLEXITY‣Uncomplexity extraction:
Distills pure qubits from a state⇢<latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit>

|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates“Uncomplexity”

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)

STEPS TOWARDS A RESOURCE THEORY OF UNCOMPLEXITY‣Uncomplexity extraction:
Distills pure qubits from a state‣Uncomplexity expenditure:
Imitates a state
Junk⇢<latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit>

|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates⇢?
<latexit sha1_base64="ZVyslXZeEOAoRGVr23AoUTbDZjU=">AAAB7HicbVDLSgNBEOyNrxhfUY9eBoPgKeyqqDcDXjxGcE0gWcLsZDYZMo9lZlYIS77BiwdFvPpB3vwbJ8keNLGgoajqprsrTjkz1ve/vdLK6tr6RnmzsrW9s7tX3T94NCrThIZEcaXbMTaUM0lDyyyn7VRTLGJOW/Hoduq3nqg2TMkHO05pJPBAsoQRbJ0UdvVQ3fSqNb/uz4CWSVCQGhRo9qpf3b4imaDSEo6N6QR+aqMca8sIp5NKNzM0xWSEB7TjqMSCmiifHTtBJ07po0RpV9Kimfp7IsfCmLGIXafAdmgWvan4n9fJbHId5UymmaWSzBclGUdWoennqM80JZaPHcFEM3crIkOsMbEun4oLIVh8eZk8ntWDy/r5/UWt0SjiKMMRHMMpBHAFDbiDJoRAgMEzvMKbJ70X7937mLeWvGLmEP7A+/wBp7mOlg==</latexit>

|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates

Agent“Uncomplexity”

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)

STEPS TOWARDS A RESOURCE THEORY OF UNCOMPLEXITY‣Uncomplexity extraction:
Distills pure qubits from a state‣Uncomplexity expenditure:
Imitates a state
Junk⇢<latexit sha1_base64="sZJh6LFontZRU3o5mcZ0ta47ygs=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKeyqqMeAF48RzAOSJcxOZrND5rHMzAoh5Be8eFDEqz/kzb9xNtmDJhY0FFXddHdFKWfG+v63V1pb39jcKm9Xdnb39g+qh0dtozJNaIsornQ3woZyJmnLMstpN9UUi4jTTjS+y/3OE9WGKfloJykNBR5JFjOCbS71daIG1Zpf9+dAqyQoSA0KNAfVr/5QkUxQaQnHxvQCP7XhFGvLCKezSj8zNMVkjEe056jEgppwOr91hs6cMkSx0q6kRXP198QUC2MmInKdAtvELHu5+J/Xy2x8G06ZTDNLJVksijOOrEL542jINCWWTxzBRDN3KyIJ1phYF0/FhRAsv7xK2hf14Lp++XBVazSKOMpwAqdwDgHcQAPuoQktIJDAM7zCmye8F+/d+1i0lrxi5hj+wPv8ASGujk0=</latexit>

|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates⇢?
<latexit sha1_base64="ZVyslXZeEOAoRGVr23AoUTbDZjU=">AAAB7HicbVDLSgNBEOyNrxhfUY9eBoPgKeyqqDcDXjxGcE0gWcLsZDYZMo9lZlYIS77BiwdFvPpB3vwbJ8keNLGgoajqprsrTjkz1ve/vdLK6tr6RnmzsrW9s7tX3T94NCrThIZEcaXbMTaUM0lDyyyn7VRTLGJOW/Hoduq3nqg2TMkHO05pJPBAsoQRbJ0UdvVQ3fSqNb/uz4CWSVCQGhRo9qpf3b4imaDSEo6N6QR+aqMca8sIp5NKNzM0xWSEB7TjqMSCmiifHTtBJ07po0RpV9Kimfp7IsfCmLGIXafAdmgWvan4n9fJbHId5UymmaWSzBclGUdWoennqM80JZaPHcFEM3crIkOsMbEun4oLIVh8eZk8ntWDy/r5/UWt0SjiKMMRHMMpBHAFDbiDJoRAgMEzvMKbJ70X7937mLeWvGLmEP7A+/wBp7mOlg==</latexit>

|0i
|0i
|0i
<latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit><latexit sha1_base64="YubJ/3VgzYIzcE/y08c+lACh9BM=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69BIvgqSQq6rHgxWMF+yFtKJvtpF26uwm7G6HE/govHhTx6s/x5r9x2+agrQ8GHu/NMDMvTDjTxvO+ncLK6tr6RnGztLW9s7tX3j9o6jhVFBs05rFqh0QjZxIbhhmO7UQhESHHVji6mfqtR1SaxfLejBMMBBlIFjFKjJUenryuInLAsVeueFVvBneZ+DmpQI56r/zV7cc0FSgN5UTrju8lJsiIMoxynJS6qcaE0BEZYMdSSQTqIJsdPHFPrNJ3o1jZksadqb8nMiK0HovQdgpihnrRm4r/eZ3URNdBxmSSGpR0vihKuWtid/q922cKqeFjSwhVzN7q0iFRhBqbUcmG4C++vEyaZ1X/snp+d1Gp1fI4inAEx3AKPlxBDW6hDg2gIOAZXuHNUc6L8+58zFsLTj5zCH/gfP4AtyuQWw==</latexit>r gates

Agent“Uncomplexity”

CAN YET ANOTHER BROWN-SUSSKIND CONJECTURE - WHETHER ARESOURCE THEORY OF UNCOMPLEXITY CAN BE FORMULATED - BE SHOWN?
It seems so: Governed by the complexity entropy
Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, Faist, Phys Rev A 106, 062417 (2022) (2021)
Munson, Kothakonda, Haferkamp, Yunger-Halpern, Eisert, Faist, in preparation (2023)

OUTLOOKOPEN QUESTIONS‣ Settled the linear growth conjecture due to Brown and Susskind

COMPLEXITY WITH MEASUREMENTS

APPROXIMATE NOTIONS?

⇡ENTANGLEMENT?

HOLOGRAPHIC
setting?
‣ HolographicSETTING?
QUANTUM ADVANTAGES?

CONNECTIONS TO
QUANTUM CHAOS?

NIELSEN’S COST?
QUANTUM ERROR CORRECTION?

OPEN QUESTIONSTHANKS FOR YOUR ATTENTION!

COMPLEXITY WITH MEASUREMENTS

APPROXIMATE NOTIONS?

⇡ENTANGLEMENT?

HOLOGRAPHIC
setting?
‣ HolographicSETTING?
QUANTUM ADVANTAGES?

CONNECTIONS TO
QUANTUM CHAOS?

NIELSEN’S COST?
QUANTUM ERROR CORRECTION?