The Experts below are selected from a list of 72870 Experts worldwide ranked by ideXlab platform
Yasser Omar - One of the best experts on this subject based on the ideXlab platform.
-
Continuous-time quantum-walk Spatial Search on the Bollobás scale-free network
Physical Review A, 2020Co-Authors: Tomo Osada, Yasser Omar, Bruno Coelho Coutinho, Kaoru Sanaka, William J. Munro, Kae NemotoAbstract:The scale-free property emerges in various real-world networks and is an essential property that characterizes the dynamics or features of such networks. In this work, we investigate the effect of this scale-free property on a quantum information processing task of finding a marked node in the network, known as the quantum Spatial Search. We analyze the quantum Spatial Search algorithm using a continuous-time quantum walk on the Bollob\'as network, and we evaluate the time $T$ to localize the quantum walker on the marked node starting from an unbiased initial state. Our main finding is that $T$ is determined by the global structure around the marked node, while some local information of the marked node, such as the degree, does not identify $T$. We discuss this by examining the correlation between $T$ and some centrality measures of the network, and we show that the closeness centrality of the marked node is highly correlated with $T$. We also characterize the distribution of $T$ by marking different nodes in the network, which displays a multimode log-normal distribution. Especially on the Bollob\'as network, $T$ is a few orders of magnitude shorter depending on whether the marked node is adjacent to the largest degree hub node. However, as $T$ depends on the property of the marked node, one requires some amount of prior knowledge about such a property of the marked node in order to identify the optimal time to measure the quantum walker and achieve a fast Search. These results indicate that the existence of the hub node in the scale-free network plays a crucial role in the quantum Spatial Search.
-
Optimal Quantum Spatial Search on Random Temporal Networks.
Physical review letters, 2017Co-Authors: Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio, Yasser OmarAbstract:To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the Spatial Search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdos-Renyi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when Search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal Search on them. From this first study of quantum Spatial Search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.
-
Spatial Search by Quantum Walk is Optimal for Almost all Graphs.
Physical review letters, 2016Co-Authors: Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser OmarAbstract:The problem of finding a marked node in a graph can be solved by the Spatial Search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdos-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, Search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum Spatial Search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that Search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on Search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.
-
Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
Scientific reports, 2015Co-Authors: Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Hartmut Neven, Yasser OmarAbstract:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the Spatial quantum Search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal Spatial Search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
-
systematic dimensionality reduction for quantum walks optimal Spatial Search and transport on non regular graphs
Scientific Reports, 2015Co-Authors: Leonardo Novo, Shantanav Chakraborty, Yasser Omar, Masoud Mohseni, Hartmut NevenAbstract:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the Spatial quantum Search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal Spatial Search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
Leonardo Novo - One of the best experts on this subject based on the ideXlab platform.
-
Optimality of Spatial Search via continuous-time quantum walks
Physical Review A, 2020Co-Authors: Shantanav Chakraborty, Leonardo Novo, Jérémie RolandAbstract:One of the most important algorithmic applications of quantum walks is to solve Spatial Search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum Search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum Search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum Search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum Search in this regime, as well as provide examples of graphs where quantum Search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum Search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
-
Optimal Quantum Spatial Search on Random Temporal Networks.
Physical review letters, 2017Co-Authors: Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio, Yasser OmarAbstract:To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the Spatial Search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdos-Renyi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when Search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal Search on them. From this first study of quantum Spatial Search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.
-
Spatial Search by Quantum Walk is Optimal for Almost all Graphs.
Physical review letters, 2016Co-Authors: Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser OmarAbstract:The problem of finding a marked node in a graph can be solved by the Spatial Search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdos-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, Search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum Spatial Search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that Search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on Search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.
-
Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
Scientific reports, 2015Co-Authors: Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Hartmut Neven, Yasser OmarAbstract:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the Spatial quantum Search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal Spatial Search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
-
systematic dimensionality reduction for quantum walks optimal Spatial Search and transport on non regular graphs
Scientific Reports, 2015Co-Authors: Leonardo Novo, Shantanav Chakraborty, Yasser Omar, Masoud Mohseni, Hartmut NevenAbstract:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the Spatial quantum Search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal Spatial Search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
Shantanav Chakraborty - One of the best experts on this subject based on the ideXlab platform.
-
Optimality of Spatial Search via continuous-time quantum walks
Physical Review A, 2020Co-Authors: Shantanav Chakraborty, Leonardo Novo, Jérémie RolandAbstract:One of the most important algorithmic applications of quantum walks is to solve Spatial Search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum Search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum Search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum Search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum Search in this regime, as well as provide examples of graphs where quantum Search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum Search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
-
Optimal Quantum Spatial Search on Random Temporal Networks.
Physical review letters, 2017Co-Authors: Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio, Yasser OmarAbstract:To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the Spatial Search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdos-Renyi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when Search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal Search on them. From this first study of quantum Spatial Search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.
-
Spatial Search by Quantum Walk is Optimal for Almost all Graphs.
Physical review letters, 2016Co-Authors: Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser OmarAbstract:The problem of finding a marked node in a graph can be solved by the Spatial Search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdos-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, Search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum Spatial Search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that Search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on Search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.
-
Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
Scientific reports, 2015Co-Authors: Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Hartmut Neven, Yasser OmarAbstract:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the Spatial quantum Search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal Spatial Search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
-
systematic dimensionality reduction for quantum walks optimal Spatial Search and transport on non regular graphs
Scientific Reports, 2015Co-Authors: Leonardo Novo, Shantanav Chakraborty, Yasser Omar, Masoud Mohseni, Hartmut NevenAbstract:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the Spatial quantum Search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal Spatial Search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
Adam Glos - One of the best experts on this subject based on the ideXlab platform.
-
Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs
arXiv: Quantum Physics, 2020Co-Authors: Ryszard Kukulski, Adam GlosAbstract:This comment is to correct the proof of optimality of quantum Spatial Search for Erdős-Renyi graphs presented in `Spatial Search by Quantum Walk is Optimal for Almost all Graphs' (this https URL). The authors claim that if $p\geq \frac{\log^{3/2}(n)}{n}$, then the CTQW-based Search is optimal for almost all graphs. Below we point the issues found in the main paper, and propose corrections, which in fact improve the result to $p=\omega(\log(n)/n)$ in case of transition rate $\gamma = 1/\lambda_1$. In the case of the proof for simplified transition rate $1/(np)$ we pointed a possible issue with applying perturbation theory.
-
Impact of global and local interaction on quantum Spatial Search on chimera graph.
International Journal of Quantum Information, 2019Co-Authors: Adam Glos, Tomasz JanuszekAbstract:In the paper, we investigated the influence of local and global interaction on the efficiency of continuous-time quantum Spatial Search. To do so, we analyzed numerically chimera graph, which is defined as 2D grid with each node replaced by complete bipartite graph. Our investigation provides a numerical evidence that with a large number of local interactions the quantum Spatial Search is optimal, contrary to the case with limited number of such interactions. The result suggests that relatively large number of local interactions with the marked vertex is necessary for optimal Search, which in turn would imply that poorly connected vertices are hard to be found.
-
Impact of the malicious input data modification on the efficiency of quantum Spatial Search
Quantum Information Processing, 2019Co-Authors: Adam Glos, Jarosław Adam MiszczakAbstract:In this paper, we demonstrate that the efficiency of quantum Spatial Search can be significantly altered by malicious manipulation of the input data in the client–server model. We achieve this by exploiting exceptional configuration effect on Szegedy Spatial Search and proposing a framework suitable for analysing efficiency of attacks on quantum Search algorithms. We provide the analysis of proposed attacks for different models of random graphs. The obtained results demonstrate that quantum algorithms in general are not secure against input data alteration.
-
Vertices cannot be hidden from quantum Spatial Search for almost all random graphs
Quantum Information Processing, 2018Co-Authors: Adam Glos, Ryszard Kukulski, Aleksandra Krawiec, Zbigniew PuchałaAbstract:In this paper, we show that all nodes can be found optimally for almost all random Erdős–Renyi $$\mathcal G(n,p)$$ graphs using continuous-time quantum Spatial Search procedure. This works for both adjacency and Laplacian matrices, though under different conditions. The first one requires $$p=\omega (\log ^8(n)/n)$$ , while the second requires $$p\ge (1+\varepsilon )\log (n)/n$$ , where $$\varepsilon >0$$ . The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the $$\Vert \cdot \Vert _\infty $$ norm. At the same time for $$p
-
Vertices cannot be hidden from quantum Spatial Search for almost all random graphs
Quantum Information Processing, 2018Co-Authors: Adam Glos, Ryszard Kukulski, Aleksandra Krawiec, Zbigniew PuchałaAbstract:In this paper, we show that all nodes can be found optimally for almost all random Erdős–Rényi $$\mathcal G(n,p)$$ G ( n , p ) graphs using continuous-time quantum Spatial Search procedure. This works for both adjacency and Laplacian matrices, though under different conditions. The first one requires $$p=\omega (\log ^8(n)/n)$$ p = ω ( log 8 ( n ) / n ) , while the second requires $$p\ge (1+\varepsilon )\log (n)/n$$ p ≥ ( 1 + ε ) log ( n ) / n , where $$\varepsilon >0$$ ε > 0 . The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the $$\Vert \cdot \Vert _\infty $$ ‖ · ‖ ∞ norm. At the same time for $$p
Shohei Watabe - One of the best experts on this subject based on the ideXlab platform.
-
scaling hypothesis of a Spatial Search on fractal lattices using a quantum walk
Physical Review A, 2020Co-Authors: Rei Sato, Tetsuro Nikuni, Shohei WatabeAbstract:We investigate a quantum Spatial Search problem on fractal lattices, such as Sierpinski carpets and Menger sponges. In earlier numerical studies of the Sierpinski gasket, the Sierpinski tetrahedron, and the Sierpinski carpet, conjectures have been proposed for the scaling of a quantum Spatial Search problem finding a specific target, which is given in terms of the characteristic quantities of a fractal geometry. We find that our simulation results for extended Sierpinski carpets and Menger sponges support the conjecture for the ${\it optimal}$ number of the oracle calls, where the exponent is given by $1/2$ for $d_{\rm s} > 2$ and the inverse of the spectral dimension $d_{\rm s}$ for $d_{\rm s} < 2$. We also propose a scaling hypothesis for the ${\it effective}$ number of the oracle calls defined by the ratio of the ${\it optimal}$ number of oracle calls to a square root of the maximum finding probability. The form of the scaling hypothesis for extended Sierpinski carpets is very similar but slightly different from the earlier conjecture for the Sierpinski gasket, the Sierpinski tetrahedron, and the conventional Sierpinski carpet.
-
scaling hypothesis of a Spatial Search on fractal lattices using a quantum walk
Physical Review A, 2020Co-Authors: Rei Sato, Tetsuro Nikuni, Shohei WatabeAbstract:A quantum Spatial Search problem on fractal lattices, such as Sierpinski carpets and Menger sponges, is studied numerically. The results confirmed various conjectures on the relationship between the number of oracle calls needed for a Search with respect to the number of sites and Spatial dimensions.
-
Spatial Search on Sierpinski carpet using quantum walk
Journal of the Physical Society of Japan, 2018Co-Authors: Shu Tamegai, Shohei Watabe, Tetsuro NikuniAbstract:We investigate a quantum Spatial Search problem on a fractal lattice. A recent study for the Sierpinski gasket and tetrahedron made a conjecture that the dynamics of the Search on a fractal lattice is determined by spectral dimension. We tackle this problem for the Sierpinski carpet, and our simulation result supports the conjecture. We also propose a scaling hypothesis of oracle calls for the quantum amplitude amplification.
