Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExpansion Testing using Quantum Fast-Forwarding and Seed Sets
226
0
0.0
(
0
)
Authors
Simon Apers
Ask ChatGPT about the research
No Arabic abstract
Expansion testing aims to decide whether an $n$-node graph has expansion at least $Phi$, or is far from any such graph. We propose a quantum expansion tester with complexity $widetilde{O}(n^{1/3}Phi^{-1})$. This accelerates the $widetilde{O}(n^{1/2}Phi^{-2})$ classical tester by Goldreich and Ron [Algorithmica 02], and combines the $widetilde{O}(n^{1/3}Phi^{-2})$ and $widetilde{O}(n^{1/2}Phi^{-1})$ quantum speedups by Ambainis, Childs and Liu [RANDOM 11] and Apers and Sarlette [QIC 19], respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
rate research
Read More
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as $widetilde{O}(m^{1/3} delta^{-1/3})$, with $m$ the number of edges and $delta$ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for $st$-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an $n$-node graph in time $widetilde{O}(2^{n/3})$, surpassing the $Omega(2^{n/2})$ barrier set by index erasure.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with $P$ the Markov chain transition matrix and $D = sqrt{Pcirc P^T}$ its discriminant matrix ($D=P$ if $P$ is symmetric), we construct a quantum walk algorithm that for any quantum state $|vrangle$ and integer $t$ returns a quantum state $epsilon$-close to the state $D^t|vrangle/|D^t|vrangle|$. The algorithm uses $OBig(|D^t|vrangle|^{-1}sqrt{tlog(epsilon|D^t|vrangle|)^{-1}}Big)$ expected quantum walk steps and $O(|D^t|vrangle|^{-1})$ expected reflections around $|vrangle$. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of $s$-$t$ connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
Symmetry is a unifying concept in physics. In quantum information and beyond, it is known that quantum states possessing symmetry are not useful for certain information-processing tasks. For example, states that commute with a Hamiltonian realizing a time evolution are not useful for timekeeping during that evolution, and bipartite states that are highly extendible are not strongly entangled and thus not useful for basic tasks like teleportation. Motivated by this perspective, this paper details several quantum algorithms that test the symmetry of quantum states and channels. For the case of testing Bose symmetry of a state, we show that there is a simple and efficient quantum algorithm, while the tests for other kinds of symmetry rely on the aid of a quantum prover. We prove that the acceptance probability of each algorithm is equal to the maximum symmetric fidelity of the state being tested, thus giving a firm operational meaning to these latter resource quantifiers. Special cases of the algorithms test for incoherence or separability of quantum states. We evaluate the performance of these algorithms by using the variational approach to quantum algorithms, replacing the quantum prover with a variational circuit. We also show that the maximum symmetric fidelities can be calculated by semi-definite programs, which is useful for benchmarking the performance of the quantum algorithms for sufficiently small examples. Finally, we establish various generalizations of the resource theory of asymmetry, with the upshot being that the acceptance probabilities of the algorithms are resource monotones and thus well motivated from the resource-theoretic perspective.
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 $epsilon approx 0.034$ such that the quantum routing time is at most $(1-epsilon)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 $2n/3$ in expectation for uniformly random permutations, whereas swap-based protocols require time $n$ asymptotically. Additionally, we consider sparse permutations that route $k le n$ qubits and give algorithms with quantum routing time at most $n/3 + O(k^2)$ on paths and at most $2r/3 + O(k^2)$ on general graphs with radius $r$.
We propose a new quantum numerical scheme to control the dynamics of a quantum walker in a two dimensional space-time grid. More specifically, we show how, introducing a quantum memory for each of the spatial grid, this result can be achieved simply by acting on the initial state of the whole system, and therefore can be exactly controlled once for all. As example we prove analytically how to encode in the initial state any arbitrary walkers mean trajectory and variance. This brings significantly closer the possibility of implementing dynamically interesting physics models on medium term quantum devices, and introduces a new direction in simulating aspects of quantum field theories (QFTs), notably on curved manifold.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
