skip to main content

Title: 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 nearest-neighbor 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 swap-based protocol needs at least time n − 1 . This represents the first known quantum advantage over swap-based 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 swap-based 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 .
; ; ; ; ;
Award ID(s):
1813814 1818914
Publication Date:
Journal Name:
Page Range or eLocation-ID:
Sponsoring Org:
National Science Foundation
More Like this
  1. 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 two-qubit unitaries, or (2) allowing Hamiltonians with norm-bounded 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 classical-quantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gate-based 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.
  2. Understanding the structure of minor-free 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 “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free 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 minor-free graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidth-Oϵ(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 minor-free metrics; (2) themore »first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth).« less
  3. 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 second-order stationary point using O ~ ( log 2 ⁡ ( n ) / ϵ 1.75 ) queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with O ~ ( log 6 ⁡ ( n ) / ϵ 1.75 ) queries to the gradient oracle (i.e., the first-order 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.
  4. The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT 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 polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial 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 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools tomore »the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.« less
  5. All-solid-state 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, high-energy, and rechargeable batteries based on metallic anodes. 1 However, the sluggish ion transmission at the cathode-electrolyte (solid/solid) interface would result in the high resistant at the contact and limit the practical implementation of these all solid-state 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 cathode-electrolyte 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 »process. Implementing high-pressure for the electrode and electrolyte of ASSB in the assembling process has been verified is a but effective way to boost the ion transmission ability between the cathode active materials and the SE by decreasing the grain boundary impedance. Whereas the short-circuit of the battery would be induced by the mechanical deformation of the electrolyte under high pressure. 4 Herein, we demonstrate a novel way to address the ion transmission problem at the cathode-electrolyte interface in ASSBs. Starting from the cathode configuration, the finite element method (FEM) was employed to evaluate the current concentration and the distribution of the space charge layer at the cathode-electrolyte interface. Hierarchical three-dimensional (HTD) structures are found to have a higher Li + transfer number (t Li+ ), fewer free anions, and the weaker space-charge layer at the cathode-electrolyte interface in the resulting FEM simulation. To take advantage of the HTD structure, stereolithography is adopted as a manufacturing technique and single-crystalline Ni-rich (SCN) materials are selected as the active materials. Next, the manufactured HTD cathode is sintered at 600 °C in an N 2 atmosphere for the carbonization of the resin, which induces sufficient electronic conductivity for the cathode. Then, the gel-like Li 1.4 Al 0.4 Ti 1.6 (PO 4 ) 3 (LATP) precursor is synthesized and filled into the voids of the HTD structure cathode sufficiently. And the filled HTD structure cathodes are sintered at 900 °C to achieve the crystallization of the LATP gel. Scanning transmission electron microscopy (STEM) is used to unveil the morphology of the cathode-electrolyte interface between the sintered HTD cathode and the in-situ generated electrolyte (LATP). A transient phase has been found generated at the interface and matched with both lattices of the SCN and the SE, accelerating the transmission of the Li-ions, which is further verified by density functional theory calculations. In addition, Electron Energy Loss Spectroscopy demonstrates the preserved interface between HTD cathode and SEs. Atomic force microscopy is employed to measure the potential image of the cross-sectional interface by the peak force tapping mode. The average potential of modified samples is lower than the sample that mix SCN and SEs simply in the 2D planar structure, which confirms a weakened space charge layer by the enhanced contact capability as well as the ion transmission ability. To see if the demonstrated method is universally applicable, LiNi 0.8 Co 0.1 Mn 0.1 O 2 (NCM811) is selected as the cathode active material and manufactured in the same way as the SCN. The HTD cathode based on NCM811 exhibits higher electrochemical performance compared with the reference sample based on the 2D planar mixing-type cathode. We believe such a demonstrated universal strategy provides a new guideline to engineer the cathode/electrolyte interface by revolutionizing electrode structures that can be applicable to all-solid-state batteries. Figure 1. Schematic of comparing of traditional 2D planar cathode and HTD cathode in ASSB Tikekar, M. D. , et al. , Nature Energy (2016) 1 (9), 16114 Banerjee, A. , et al. , Chem Rev (2020) 120 (14), 6878 Chen, R. , et al. , Chem Rev (2020) 120 (14), 6820 Cheng, X. , et al. , Advanced Energy Materials (2018) 8 (7) Figure 1« less