The Swap gate is a ubiquitous tool for moving information on quantum hardware, yet it can be considered a classical operation because it does not entangle product states. Genuinely quantum operations could outperform Swap for the task of permuting qubits within an architecture, which we call routing. We consider quantum routing in two models: (1) allowing arbitrary twoqubit unitaries, or (2) allowing Hamiltonians with normbounded interactions. We lower bound the circuit depth or time of quantum routing in terms of spectral properties of graphs representing the architecture interaction constraints, and give a generalized upper bound for all simple connected $n$vertex graphs. In particular, we give conditions for a superpolynomial classicalquantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gatebased and Hamiltonian routing models with a constant number of local ancillas per qubit and of an $\Omega(n)$ speedup if we also allow fast local interactions.
Quantum routing with fast reversals
We present methods for implementing arbitrary permutations of qubits under interaction constraints. Our protocols make use of previous methods for rapidly reversing the order of qubits along a path. Given nearestneighbor interactions on a path of length n , we show that there exists a constant ϵ ≈ 0.034 such that the quantum routing time is at most ( 1 − ϵ ) n , whereas any swapbased protocol needs at least time n − 1 . This represents the first known quantum advantage over swapbased routing methods and also gives improved quantum routing times for realistic architectures such as grids. Furthermore, we show that our algorithm approaches a quantum routing time of 2 n / 3 in expectation for uniformly random permutations, whereas swapbased protocols require time n asymptotically. Additionally, we consider sparse permutations that route k ≤ n qubits and give algorithms with quantum routing time at most n / 3 + O ( k 2 ) on paths and at most 2 r / 3 + O ( k 2 ) on general graphs with radius r .
 Publication Date:
 NSFPAR ID:
 10296764
 Journal Name:
 Quantum
 Volume:
 5
 Page Range or eLocationID:
 533
 ISSN:
 2521327X
 Sponsoring Org:
 National Science Foundation
More Like this


Understanding the structure of minorfree metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “smallcomplexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minorfree metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion ϵD. Namely, given a minorfree graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidthOϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minorfree metrics; (2) themore »

We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function f : R n → R , our quantum algorithm outputs an ϵ approximate secondorder stationary point using O ~ ( log 2 ( n ) / ϵ 1.75 ) queries to the quantum evaluation oracle (i.e., the zerothorder oracle). Compared to the classical stateoftheart algorithm by Jin et al. with O ~ ( log 6 ( n ) / ϵ 1.75 ) queries to the gradient oracle (i.e., the firstorder oracle), our quantum algorithm is polynomially better in terms of log n and matches its complexity in terms of 1 / ϵ . Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the improvement in the quantum query complexity with log n factors for escaping from saddle points. We also show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our theoretical findings.

The constraint satisfaction problems kSAT and Quantum kSAT (kQSAT) are canonical NPcomplete and QMA_1complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with onesided error. Whereas kSAT has been wellstudied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for kQSAT. Here, we study the open problem of computing satisfying assignments to kQSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomialtime classical algorithm for kQSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for kQSAT instances from a certain nontrivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools tomore »

Allsolidstate batteries (ASSBs) have garnered increasing attention due to the enhanced safety, featuring nonflammable solid electrolytes as well as the potential to achieve high energy density. 1 The advancement of the ASSBs is expected to provide, arguably, the most straightforward path towards practical, highenergy, and rechargeable batteries based on metallic anodes. 1 However, the sluggish ion transmission at the cathodeelectrolyte (solid/solid) interface would result in the high resistant at the contact and limit the practical implementation of these all solidstate materials in real world batteries. 2 Several methods were suggested to enhance the kinetic condition of the ion migration between the cathode and the solid electrolyte (SE). 3 A composite strategy that mixes active materials and SEs for the cathode is a general way to decrease the ion transmission barrier at the cathodeelectrolyte interface. 3 The active material concentration in the cathode is reduced as much as the SE portion increases by which the energy density of the ASSB is restricted. In addition, the mixing approach generally accompanies lattice mismatches between the cathode active materials and the SE, thus providing only limited improvements, which is imputed by random contacts between the cathode active materials and the SE during the mixingmore »