Quantum Routing and Entanglement Dynamics Through Bottlenecks

To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mi>L</a:mi> <a:mo>,</a:mo> <a:mi>R</a:mi> </a:math> with <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"> <c:msub> <c:mi>N</c:mi> <c:mi>L</c:mi> </c:msub> <c:mo>,</c:mo> <c:msub> <c:mi>N</c:mi> <c:mi>R</c:mi> </c:msub> </c:math> qubits, respectively, coupled only through an intermediate region <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"> <e:mi>C</e:mi> </e:math> with <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"> <g:msub> <g:mi>N</g:mi> <g:mi>C</g:mi> </g:msub> </g:math> qubits, for any <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline"> <i:mi>δ</i:mi> <i:mo>&gt;</i:mo> <i:mn>0</i:mn> </i:math> we show a lower bound of <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"> <k:mi mathvariant="normal">Ω</k:mi> <k:mo stretchy="false">(</k:mo> <k:msubsup> <k:mi>N</k:mi> <k:mi>R</k:mi> <k:mrow> <k:mn>1</k:mn> <k:mo>−</k:mo> <k:mi>δ</k:mi> </k:mrow> </k:msubsup> <k:mo>/</k:mo> <k:msqrt> <k:msub> <k:mi>N</k:mi> <k:mi>L</k:mi> </k:msub> </k:msqrt> <k:msub> <k:mi>N</k:mi> <k:mi>C</k:mi> </k:msub> <k:mo stretchy="false">)</k:mo> </k:math> on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between <p:math xmlns:p="http://www.w3.org/1998/Math/MathML" display="inline"> <p:mi>L</p:mi> </p:math> and <r:math xmlns:r="http://www.w3.org/1998/Math/MathML" display="inline"> <r:mi>C</r:mi> <r:mo>,</r:mo> <r:mi>R</r:mi> </r:math> that can be generated in time <t:math xmlns:t="http://www.w3.org/1998/Math/MathML" display="inline"> <t:mi>t</t:mi> </t:math> by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from <v:math xmlns:v="http://www.w3.org/1998/Math/MathML" display="inline"> <v:mi>O</v:mi> <v:mo stretchy="false">(</v:mo> <v:msub> <v:mi>N</v:mi> <v:mi>L</v:mi> </v:msub> <v:mi>t</v:mi> <v:mo stretchy="false">)</v:mo> </v:math> to <z:math xmlns:z="http://www.w3.org/1998/Math/MathML" display="inline"> <z:mi>O</z:mi> <z:mo stretchy="false">(</z:mo> <z:msqrt> <z:msub> <z:mi>N</z:mi> <z:mi>L</z:mi> </z:msub> </z:msqrt> <z:mi>t</z:mi> <z:mo stretchy="false">)</z:mo> </z:math> . As a special case, when applied to the star graph (i.e., one vertex connected to <db:math xmlns:db="http://www.w3.org/1998/Math/MathML" display="inline"> <db:mi>N</db:mi> </db:math> leaves), we obtain an <fb:math xmlns:fb="http://www.w3.org/1998/Math/MathML" display="inline"> <fb:mi mathvariant="normal">Ω</fb:mi> <fb:mo stretchy="false">(</fb:mo> <fb:msqrt> <fb:msup> <fb:mi>N</fb:mi> <fb:mrow> <fb:mn>1</fb:mn> <fb:mo>−</fb:mo> <fb:mi>δ</fb:mi> </fb:mrow> </fb:msup> </fb:msqrt> <fb:mo stretchy="false">)</fb:mo> </fb:math> lower bound on the routing time and on the time to prepare <kb:math xmlns:kb="http://www.w3.org/1998/Math/MathML" display="inline"> <kb:mi>N</kb:mi> <kb:mo>/</kb:mo> <kb:mn>2</kb:mn> </kb:math> Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time <mb:math xmlns:mb="http://www.w3.org/1998/Math/MathML" display="inline"> <mb:mi mathvariant="normal">Θ</mb:mi> <mb:mo stretchy="false">(</mb:mo> <mb:msqrt> <mb:mi>N</mb:mi> </mb:msqrt> <mb:mo stretchy="false">)</mb:mo> </mb:math> using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time <rb:math xmlns:rb="http://www.w3.org/1998/Math/MathML" display="inline"> <rb:mi mathvariant="normal">Θ</rb:mi> <rb:mo stretchy="false">(</rb:mo> <rb:mi>N</rb:mi> <rb:mo stretchy="false">)</rb:mo> </rb:math> .