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:quant-ph/0503188 · Physical Review E

Quantum computing of delocalization in small-world networks

O. Giraud, Bertrand Georgeot, Dima L. Shepelyansky

Published Sep 2, 2005• 47 citations
arXivHTMLPDF

Abstract

We study a quantum small-world network with disorder and show that the system exhibits a delocalization transition. A quantum algorithm is built up which simulates the evolution operator of the model in a polynomial number of gates for an exponential number of vertices in the network. The total computational gain is shown to depend on the parameters of the network and a larger than quadratic speedup can be reached. We also investigate the robustness of the algorithm in presence of imperfections.

DOI
10.1103/physreve.72.036203

Related papers

Quantum computation of the Anderson transition in the presence of imperfections

A. A. Pomeransky, Dima L. Shepelyansky

We propose a quantum algorithm for simulation of the Anderson transition in disordered lattices and study numerically its sensitivity to static imperfections in a quantum computer. In the vicinity of the critical point the algorithm gives a quadratic speedup in computation of diffusion rate and localization length, comparing to the known classical algorithms. We show that the Anderson transition can be detected on quantum computers with 7--10 qubits.

arXiv:quant-ph/0306203•Physical Review A•Jan 12, 2004•25 citations

Quantum computation of a complex system: The kicked Harper model

B. Lévi, Bertrand Georgeot

The simulation of complex quantum systems on a quantum computer is studied, taking the kicked Harper model as an example. This well-studied system has a rich variety of dynamical behavior depending on parameters, displays interesting phenomena such as fractal spectra, mixed phase space, dynamical localization, anomalous diffusion, or partial delocalization, and can describe electrons in a magnetic field. Three different quantum algorithms are presented and analyzed, enabling us to simulate efficiently the evolution operator of this system with different precision using different resources. Depending on the parameters chosen, the system is near integrable, localized, or partially delocalized. In each case we identify transport or spectral quantities which can be obtained more efficiently on a quantum computer than on a classical one. In most cases, a polynomial gain compared to classical algorithms is obtained, which can be quadratic or less depending on the parameter regime. We also present the effects of static imperfections on the quantities selected and show that depending on the regime of parameters, very different behaviors are observed. Some quantities can be obtained reliably with moderate levels of imperfection even for large number of qubits, whereas others are exponentially sensitive to the number of qubits. In particular, the imperfection threshold for delocalization becomes exponentially small in the partially delocalized regime. Our results show that interesting behavior can be observed with as little as 7-8 qubits and can be reliably measured in presence of moderate levels of internal imperfections.

arXiv:quant-ph/0409028•Physical Review E•Nov 22, 2004•27 citations

Speedup of the quantum adiabatic algorithm using delocalization catalysis

Chenfeng Cao, Jian Xue, Nic Shannon +1 more

We propose a method to speed up the quantum adiabatic algorithm using catalysis by many-body delocalization.This is applied to random-field antiferromagnetic Ising spin models.The algorithm is catalyzed in such a way that the evolution approximates a Heisenberg model in the middle of its course, and the model is in a delocalized phase.We show numerically that we can speed up the standard algorithm for finding the ground state of the random-field Ising model using this idea.We also demonstrate that the speedup is due to gap amplification, even though the underlying model is not frustration-free.The crossover to speedup occurs at roughly the value of the interaction which is known to be the critical one for the delocalization transition.We also calculate the participation ratio and entanglement entropy as a function of time: Their time dependencies indicate that the system is exploring more states and that they are more entangled than when there is no catalyst.Together, all these pieces of evidence demonstrate that the speedup is related to delocalization.Even though only relatively small systems can be investigated, the evidence suggests that the scaling of the method with system size is favorable.Our method is illustrated by experimental results from a small online IBM quantum computer, showing how to verify the method in future as such machines improve.The cost of the catalytic method compared with the standard algorithm is only a constant factor.

arXiv:2007.11212•Physical Review Research•Jan 29, 2021•17 citations

Quantum Simulation of Tunneling in Small Systems

Andrew T. Sornborger

A number of quantum algorithms have been performed on small quantum computers; these include Shor's prime factorization algorithm, error correction, Grover's search algorithm and a number of analog and digital quantum simulations. Because of the number of gates and qubits necessary, however, digital quantum particle simulations remain untested. A contributing factor to the system size required is the number of ancillary qubits needed to implement matrix exponentials of the potential operator. Here, we show that a set of tunneling problems may be investigated with no ancillary qubits and a cost of one single-qubit operator per time step for the potential evolution, eliminating at least half of the quantum gates required for the algorithm and more than that in the general case. Such simulations are within reach of current quantum computer architectures.

arXiv:1202.1536•Scientific Reports•Aug 22, 2012•25 citations

Real-space visualization of quantum phase transitions by network topology

Shehtab Zaman, Wei‐Cheng Lee

We demonstrate that with appropriate quantum correlation function, a real-space network model can be constructed to study the phase transitions in quantum systems. For a three-dimensional bosonic system, a single-particle density matrix is adopted to construct an adjacency matrix. We show that a Bose-Einstein condensate transition can be interpreted as a transition into a small-world network, which is accurately captured by a small-world coefficient. For a one-dimensional disordered system, using the electron diffusion operator to build the adjacency matrix, we find that Anderson localized states create many weakly linked subgraphs, which significantly reduces the clustering coefficient and lengthens the shortest path. We show that the crossover from delocalized to localized regimes as a function of the disorder strength can be identified as a loss of global connection, which is revealed by the small-world coefficient as well as other independent measures such as robustness, efficiency, and algebraic connectivity. Our results suggest that quantum phase transitions can be visualized in real space and characterized by network analysis with suitable choices of quantum correlation functions.

arXiv:1904.04275•Physical review. E•Jul 11, 2019•6 citations

A Quantum Algorithm for Network Reliability

Stefan Pabst, Yunseong Nam

Building a network that is resilient to a component failure is vital. Our access to electricity and telecommunications or the internet of things all hinge on an uninterrupted service provided by a robust network. Calculating the network reliability $R$ is $\sharp$P-complete and intractable to calculate exactly for medium and large networks. Here, we present an explicit, circuit-level implementation of a quantum algorithm that computes $R$. Our algorithm requires $O(EV/ε)$ gate operations and $O(E)$ qubits, where $V$ and $E$ are the number of nodes and edges in the graph and $ε$ is the uncertainty in the reliability estimation. This constitutes a significant polynomial speedup over the best classical approaches currently known. We further provide quantum gate counts, relevant for both pre-fault-tolerant and fault-tolerant regimes, sufficient to compute $R$.

arXiv:2203.10201•Mar 19, 2022•4 citations
We study a quantum small-world network with disorder and show that the system exhibits a delocalization transition. A quantum algorithm is built up which simulates the evolution operator of the model in a polynomial number of gates for an exponential number of vertices in the network. The total computational gain is shown to depend on the parameters of the network and a larger than quadratic speedup can be reached. We also investigate the robustness of the algorithm in presence of imperfections.
The simulation of complex quantum systems on a quantum computer is studied, taking the kicked Harper model as an example. This well-studied system has a rich variety of dynamical behavior depending on parameters, displays interesting phenomena such as fractal spectra, mixed phase space, dynamical localization, anomalous diffusion, or partial delocalization, and can describe electrons in a magnetic field. Three different quantum algorithms are presented and analyzed, enabling us to simulate efficiently the evolution operator of this system with different precision using different resources. Depending on the parameters chosen, the system is near integrable, localized, or partially delocalized. In each case we identify transport or spectral quantities which can be obtained more efficiently on a quantum computer than on a classical one. In most cases, a polynomial gain compared to classical algorithms is obtained, which can be quadratic or less depending on the parameter regime. We also present the effects of static imperfections on the quantities selected and show that depending on the regime of parameters, very different behaviors are observed. Some quantities can be obtained reliably with moderate levels of imperfection even for large number of qubits, whereas others are exponentially sensitive to the number of qubits. In particular, the imperfection threshold for delocalization becomes exponentially small in the partially delocalized regime. Our results show that interesting behavior can be observed with as little as 7-8 qubits and can be reliably measured in presence of moderate levels of internal imperfections.
We propose a method to speed up the quantum adiabatic algorithm using catalysis by many-body delocalization.This is applied to random-field antiferromagnetic Ising spin models.The algorithm is catalyzed in such a way that the evolution approximates a Heisenberg model in the middle of its course, and the model is in a delocalized phase.We show numerically that we can speed up the standard algorithm for finding the ground state of the random-field Ising model using this idea.We also demonstrate that the speedup is due to gap amplification, even though the underlying model is not frustration-free.The crossover to speedup occurs at roughly the value of the interaction which is known to be the critical one for the delocalization transition.We also calculate the participation ratio and entanglement entropy as a function of time: Their time dependencies indicate that the system is exploring more states and that they are more entangled than when there is no catalyst.Together, all these pieces of evidence demonstrate that the speedup is related to delocalization.Even though only relatively small systems can be investigated, the evidence suggests that the scaling of the method with system size is favorable.Our method is illustrated by experimental results from a small online IBM quantum computer, showing how to verify the method in future as such machines improve.The cost of the catalytic method compared with the standard algorithm is only a constant factor.
A number of quantum algorithms have been performed on small quantum computers; these include Shor's prime factorization algorithm, error correction, Grover's search algorithm and a number of analog and digital quantum simulations. Because of the number of gates and qubits necessary, however, digital quantum particle simulations remain untested. A contributing factor to the system size required is the number of ancillary qubits needed to implement matrix exponentials of the potential operator. Here, we show that a set of tunneling problems may be investigated with no ancillary qubits and a cost of one single-qubit operator per time step for the potential evolution, eliminating at least half of the quantum gates required for the algorithm and more than that in the general case. Such simulations are within reach of current quantum computer architectures.
We demonstrate that with appropriate quantum correlation function, a real-space network model can be constructed to study the phase transitions in quantum systems. For a three-dimensional bosonic system, a single-particle density matrix is adopted to construct an adjacency matrix. We show that a Bose-Einstein condensate transition can be interpreted as a transition into a small-world network, which is accurately captured by a small-world coefficient. For a one-dimensional disordered system, using the electron diffusion operator to build the adjacency matrix, we find that Anderson localized states create many weakly linked subgraphs, which significantly reduces the clustering coefficient and lengthens the shortest path. We show that the crossover from delocalized to localized regimes as a function of the disorder strength can be identified as a loss of global connection, which is revealed by the small-world coefficient as well as other independent measures such as robustness, efficiency, and algebraic connectivity. Our results suggest that quantum phase transitions can be visualized in real space and characterized by network analysis with suitable choices of quantum correlation functions.
Building a network that is resilient to a component failure is vital. Our access to electricity and telecommunications or the internet of things all hinge on an uninterrupted service provided by a robust network. Calculating the network reliability RRR is ♯\sharp♯P-complete and intractable to calculate exactly for medium and large networks. Here, we present an explicit, circuit-level implementation of a quantum algorithm that computes RRR. Our algorithm requires O(EV/ε)O(EV/ε)O(EV/ε) gate operations and O(E)O(E)O(E) qubits, where VVV and EEE are the number of nodes and edges in the graph and εεε is the uncertainty in the reliability estimation. This constitutes a significant polynomial speedup over the best classical approaches currently known. We further provide quantum gate counts, relevant for both pre-fault-tolerant and fault-tolerant regimes, sufficient to compute RRR.