An official website of the United States government
We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup afforded by quantum teleportation—showing an upper bound on the separation in routing time for any interaction graph—and give tighter bounds for some common classes of graphs. Published by the American Physical Society2024
more »
« less
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 .
more »
« less
- PAR ID:
- 10296764
- Date Published:
- Journal Name:
- Quantum
- Volume:
- 5
- ISSN:
- 2521-327X
- Page Range / eLocation ID:
- 533
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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.more » « less
-
null (Ed.)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.more » « less
-
Abstract Let π n be a uniformly chosen random permutation on [ n ]. Using an analysis of the probability that two overlapping consecutive k -permutations are order isomorphic, we show that the expected number of distinct consecutive patterns of all lengths k ∈ {1, 2,…, n } in π n is n 2 2 ( 1 - o ( 1 ) ) {{{n^2}} \over 2}\left( {1 - o\left( 1 \right)} \right) as n → ∞. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.more » « less
-
Abstract Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers p such that $$p^r \mathrel {|}N$$ p r | N in time $$O(N^{1/4r+\epsilon })$$ O ( N 1 / 4 r + ϵ ) for any $$\epsilon > 0$$ ϵ > 0 . For example, the algorithm can be used to test squarefreeness of N in time $$O(N^{1/8+\epsilon })$$ O ( N 1 / 8 + ϵ ) ; previously, the best rigorous bound for this problem was $$O(N^{1/6+\epsilon })$$ O ( N 1 / 6 + ϵ ) , achieved via the Pollard–Strassen method.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.22331/q-2021-08-31-533
