Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1906.01672

Wormhole Traversability via Quantum Random Walks

Ning Bao, Vincent Paul Su, Mykhaylo Usatyuk

Published Jun 4, 2019• 6 citations
arXivHTMLPDF

Abstract

In this work we seek to generalize the connection between traversable wormholes and quantum channels. We do this via a connection between traversable wormholes and graph geometries on which we can perform quantum random walks for signal transmission. As a proof of principle, we give an example of a geometry for which quantum random walk signal traversal occurs exponentially faster than a standard ballistic classical traversal. We then generalize this connection to superpositions over holographic states, and argue that the quantum random walk/graph geometry picture works to study quantum channel properties of such states.

DOI
10.48550/arxiv.1906.01672

Related papers

Quantum Walk-Based Algorithms for Graph Traversal

Jincheng Zhang

This paper investigates the application of quantum walk algorithms to graph traversal problems. Traditional graph traversal algorithms often suffer from performance limitations when dealing with large and complex graphs due to their inherent sequential nature. We propose utilizing quantum walks, quantum analogs of random walks, as a potential solution. Quantum walks leverage quantum superposition and interference to enable more efficient exploration of the graph. We present a theoretical framework for designing quantum walk-based algorithms for graph traversal, focusing on key aspects such as Hamiltonian construction, walker evolution, and measurement strategies. Our work demonstrates the potential for exponential speedups for specific graph algorithms compared to their classical counterparts. We analyze the core principles underpinning this approach and highlight the advantages of quantum walk based algorithms for graph traversal.

•Sep 5, 2026•0 citations

Quantum Gravity in the Lab: Teleportation by Size and Traversable Wormholes

Adam R. Brown, Hrant Gharibyan, Stefan Leichenauer +6 more

With the long-term goal of studying models of quantum gravity in the lab, we propose holographic teleportation protocols that can be readily executed in table-top experiments. These protocols exhibit similar behavior to that seen in the recent traversable wormhole constructions of [1,2]: information that is scrambled into one half of an entangled system will, following a weak coupling between the two halves, unscramble into the other half. We introduce the concept of teleportation by size to capture how the physics of operator-size growth naturally leads to information transmission. The transmission of a signal through a semi-classical holographic wormhole corresponds to a rather special property of the operator-size distribution we call size winding. For more general systems (which may not have a clean emergent geometry), we argue that imperfect size winding is a generalization of the traversable wormhole phenomenon. In addition, a form of signalling continues to function at high temperature and at large times for generic chaotic systems, even though it does not correspond to a signal going through a geometrical wormhole, but rather to an interference effect involving macroscopically different emergent geometries. Finally, we outline implementations feasible with current technology in two experimental platforms: Rydberg atom arrays and trapped ions.

arXiv:1911.06314•Nov 14, 2019•125 citations

Quantum Walk-Based Algorithms for Graph Traversal and Search

Jincheng Zhang

This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.

•Sep 6, 2026•0 citations

Regenesis and quantum traversable wormholes

Ping Gao, Hong Liu

Abstract Recent gravity discussions of a traversable wormhole indicate that in holographic systems signals generated by a source could reappear long after they have dissipated, with the need of only performing some simple operations. In this paper we argue the phenomenon, to which we refer as “regenesis”, is universal in general quantum chaotic many-body systems, and elucidate its underlying physics. The essential elements behind the phenomenon are: (i) scrambling which in a chaotic system makes out-of-time-ordered correlation functions (OTOCs) vanish at large times; (ii) the entanglement structure of the state of the system. The latter aspect also implies that the regenesis phenomenon requires fine tuning of the initial state. Compared to other manifestations of quantum chaos such as the initial growth of OTOCs which deals with early times, and a random matrix-type energy spectrum which reflects very large time behavior, regenesis concerns with intermediate times, of order the scrambling time of a system. We also study the phenomenon in detail in general two-dimensional conformal field theories in the large central charge limit, and highlight some interesting features including a resonant enhancement of regenesis signals near the scrambling time and their oscillations in coupling. Finally, we discuss gravity implications of the phenomenon for systems with a gravity dual, arguing that there exist regimes for which traversability of a wormhole is quantum in nature, i.e. cannot be associated with a semi-classical spacetime causal structure.

arXiv:1810.01444•Journal of High Energy Physics•Oct 1, 2019•43 citations

Traversable wormholes as quantum channels: exploring CFT entanglement structure and channel capacity in holography

Ning Bao, Aidan Chatwin-Davies, Jason Pollack +1 more

A bstract We interpret the traversable wormhole in AdS/CFT in the context of quantum information theory. In particular, we investigate its properties as both a quantum channel and entanglement witness. We define protocols that allow either the bounding of the channel’s entanglement capacity or the determination of aspects of the entanglement structure between the two boundary CFTs. Such protocols and connections allow for the use of quantum channel techniques in the study of gravitational physics and vice versa. More generally, our results suggest a purely quantum information-theoretic criterion for recognizing when the product of two boundary theories has a classical bulk interpretation.

arXiv:1808.05963•Journal of High Energy Physics•Nov 1, 2018•28 citations

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem

•Dec 8, 2003•0 citations
In this work we seek to generalize the connection between traversable wormholes and quantum channels. We do this via a connection between traversable wormholes and graph geometries on which we can perform quantum random walks for signal transmission. As a proof of principle, we give an example of a geometry for which quantum random walk signal traversal occurs exponentially faster than a standard ballistic classical traversal. We then generalize this connection to superpositions over holographic states, and argue that the quantum random walk/graph geometry picture works to study quantum channel properties of such states.
This paper investigates the application of quantum walk algorithms to graph traversal problems. Traditional graph traversal algorithms often suffer from performance limitations when dealing with large and complex graphs due to their inherent sequential nature. We propose utilizing quantum walks, quantum analogs of random walks, as a potential solution. Quantum walks leverage quantum superposition and interference to enable more efficient exploration of the graph. We present a theoretical framework for designing quantum walk-based algorithms for graph traversal, focusing on key aspects such as Hamiltonian construction, walker evolution, and measurement strategies. Our work demonstrates the potential for exponential speedups for specific graph algorithms compared to their classical counterparts. We analyze the core principles underpinning this approach and highlight the advantages of quantum walk based algorithms for graph traversal.
With the long-term goal of studying models of quantum gravity in the lab, we propose holographic teleportation protocols that can be readily executed in table-top experiments. These protocols exhibit similar behavior to that seen in the recent traversable wormhole constructions of [1,2]: information that is scrambled into one half of an entangled system will, following a weak coupling between the two halves, unscramble into the other half. We introduce the concept of teleportation by size to capture how the physics of operator-size growth naturally leads to information transmission. The transmission of a signal through a semi-classical holographic wormhole corresponds to a rather special property of the operator-size distribution we call size winding. For more general systems (which may not have a clean emergent geometry), we argue that imperfect size winding is a generalization of the traversable wormhole phenomenon. In addition, a form of signalling continues to function at high temperature and at large times for generic chaotic systems, even though it does not correspond to a signal going through a geometrical wormhole, but rather to an interference effect involving macroscopically different emergent geometries. Finally, we outline implementations feasible with current technology in two experimental platforms: Rydberg atom arrays and trapped ions.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.
Abstract Recent gravity discussions of a traversable wormhole indicate that in holographic systems signals generated by a source could reappear long after they have dissipated, with the need of only performing some simple operations. In this paper we argue the phenomenon, to which we refer as “regenesis”, is universal in general quantum chaotic many-body systems, and elucidate its underlying physics. The essential elements behind the phenomenon are: (i) scrambling which in a chaotic system makes out-of-time-ordered correlation functions (OTOCs) vanish at large times; (ii) the entanglement structure of the state of the system. The latter aspect also implies that the regenesis phenomenon requires fine tuning of the initial state. Compared to other manifestations of quantum chaos such as the initial growth of OTOCs which deals with early times, and a random matrix-type energy spectrum which reflects very large time behavior, regenesis concerns with intermediate times, of order the scrambling time of a system. We also study the phenomenon in detail in general two-dimensional conformal field theories in the large central charge limit, and highlight some interesting features including a resonant enhancement of regenesis signals near the scrambling time and their oscillations in coupling. Finally, we discuss gravity implications of the phenomenon for systems with a gravity dual, arguing that there exist regimes for which traversability of a wormhole is quantum in nature, i.e. cannot be associated with a semi-classical spacetime causal structure.
A bstract We interpret the traversable wormhole in AdS/CFT in the context of quantum information theory. In particular, we investigate its properties as both a quantum channel and entanglement witness. We define protocols that allow either the bounding of the channel’s entanglement capacity or the determination of aspects of the entanglement structure between the two boundary CFTs. Such protocols and connections allow for the use of quantum channel techniques in the study of gravitational physics and vice versa. More generally, our results suggest a purely quantum information-theoretic criterion for recognizing when the product of two boundary theories has a classical bulk interpretation.
We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem