Rei Sato
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Rei Sato has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Kazuhiro Saito
KDDI Research, Inc.,Fujimino-shi, Saitama,Japan
6 shared publications - Shohei Watabe
Shibaura Institute of Technology
3 shared publications - Tetsuro Nikuni
Department of Physics, Tokyo University of Science, Shinjuku, Tokyo 162-8601, Japan
3 shared publications - Mori Kurokawa
KDDI Research, Inc
2 shared publications - Pulak Ranjan Giri
KDDI Research, Inc., Fujimino-shi, Saitama, Japan
2 shared publications - Shuichiro Haruta
Division KDDI Research, Inc 2-1-15 Ohara Fujimino-shi 356-8502 Saitama Japan
2 shared publications
Latest Publications
- 6 April 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Quantum Walk-Based Hash Function: Scalable Readout for Proof of Quantum Work
We investigate quantum walk-based hash functions, which are generated from the count distribution generated by a quantum walker on graphs. The method is expected to be one of the promising approaches for generating robust hash functions; however, the quantum computation in small systems is susceptible to spoofing via classical imitation. To address this issue, it is necessary to perform calculations in a quantum space size that classical algorithms are difficult to simulate. In such cases, simply increasing the quantum space size leads to an increase in the number of quantum circuit measurements, thereby increasing the time required to generate the ideal measurement distribution. Based on these facts, we propose a quantum hybrid algorithm combining a quantum walk with a shot-based random projection architecture. This method compresses the output into a fixed-length 256-bit hash by weighting and binarizing the measurement counts of each node. We investigate the proposed method through the numerical simulations of quantum walks on the Hanoi Network (HN4) with $N=4096$. The results demonstrate no hash collisions and an avalanche effect of approximately 49%, which is close to the ideal value of 50%. Additionally, we achieved the consensus robustness of up to 94%, compared to the ideal value of 100%. These results suggest the feasibility of a scalable quantum hash function for Proof of Quantum Work (PoQ) on quantum devices.- 6 April 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Quantum Walk-Based Hash Function: Scalable Readout for Proof of Quantum Work
We investigate quantum walk-based hash functions, which are generated from the count distribution generated by a quantum walker on graphs. The method is expected to be one of the promising approaches for generating robust hash functions; however, the quantum computation in small systems is susceptible to spoofing via classical imitation. To address this issue, it is necessary to perform calculations in a quantum space size that classical algorithms are difficult to simulate. In such cases, simply increasing the quantum space size leads to an increase in the number of quantum circuit measurements, thereby increasing the time required to generate the ideal measurement distribution. Based on these facts, we propose a quantum hybrid algorithm combining a quantum walk with a shot-based random projection architecture. This method compresses the output into a fixed-length 256-bit hash by weighting and binarizing the measurement counts of each node. We investigate the proposed method through the numerical simulations of quantum walks on the Hanoi Network (HN4) with $N=4096$. The results demonstrate no hash collisions and an avalanche effect of approximately 49%, which is close to the ideal value of 50%. Additionally, we achieved the consensus robustness of up to 94%, compared to the ideal value of 100%. These results suggest the feasibility of a scalable quantum hash function for Proof of Quantum Work (PoQ) on quantum devices.- Open Access
Quantum walk search based edge detection of images
Quantum walk has emerged as an essential tool for searching marked vertices on various graphs. Recent advances in the discrete-time quantum walk search algorithm have enabled it to effectively handle multiple marked vertices, expanding its range of applications further. In this article, we propose a novel application of this advanced quantum walk search algorithm for the edge detection of images\textemdash a critical task in digital image processing. Given the probabilistic nature of quantum computing, obtaining measurement result with a high success probability is essential alongside faster computation time. Our quantum walk search algorithm demonstrates a high success probability in detecting the image edges compared to the existing quantum edge detection methods and outperforms classical edge detection methods with a quadratically faster speed. A small Qiskit circuit implementation of our method using a one-dimensional quantum walk search has been executed in Qiskit's $qasm\_simulator$ and $ibm\_sydney(fake)$ device.Open AccessQuantum walk search based edge detection of images
Quantum walk has emerged as an essential tool for searching marked vertices on various graphs. Recent advances in the discrete-time quantum walk search algorithm have enabled it to effectively handle multiple marked vertices, expanding its range of applications further. In this article, we propose a novel application of this advanced quantum walk search algorithm for the edge detection of images\textemdash a critical task in digital image processing. Given the probabilistic nature of quantum computing, obtaining measurement result with a high success probability is essential alongside faster computation time. Our quantum walk search algorithm demonstrates a high success probability in detecting the image edges compared to the existing quantum edge detection methods and outperforms classical edge detection methods with a quadratically faster speed. A small Qiskit circuit implementation of our method using a one-dimensional quantum walk search has been executed in Qiskit's $qasm\_simulator$ and $ibm\_sydney(fake)$ device. - Open Access
- 6 March 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-12
Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the problem's constraints—is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher-order unconstrained binary optimization (HOBO) representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.
- 6 March 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-12
Open AccessTwo-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the problem's constraints—is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher-order unconstrained binary optimization (HOBO) representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.
- Open Access
- 8 November 2024
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 6 (4)
Universal scaling hypothesis of quantum spatial search in complex networks
Since quantum spatial searches on networks have a strong network dependence, the question arises whether the universal perspective exists in this quantum algorithm for various networks. Here, we propose a universal scaling hypothesis of the quantum spatial search on complex networks such as small-world and scale-free networks. The average path length, a key quantity in the complex network science, is useful to expose this universal feature, where the collapse plot can be generated for the optimal time, the maximal finding probability, and the optimal hopping parameter. Based on the path integral method, we also clarify that the probability amplitude in the continuous-time quantum walk can be determined by the path length distribution. Published by the American Physical Society 2024
- 8 November 2024
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 6 (4)
Open AccessUniversal scaling hypothesis of quantum spatial search in complex networks
Since quantum spatial searches on networks have a strong network dependence, the question arises whether the universal perspective exists in this quantum algorithm for various networks. Here, we propose a universal scaling hypothesis of the quantum spatial search on complex networks such as small-world and scale-free networks. The average path length, a key quantity in the complex network science, is useful to expose this universal feature, where the collapse plot can be generated for the optimal time, the maximal finding probability, and the optimal hopping parameter. Based on the path integral method, we also clarify that the probability amplitude in the continuous-time quantum walk can be determined by the path length distribution. Published by the American Physical Society 2024
- 15 September 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 02, 376-377
Circuit Implementation of Discrete-Time Quantum Walks on Complex Networks
In this paper, we propose a circuit design for implementing quantum walks on complex networks. Quantum walks are powerful tools for various graph-based applications such as spatial search, community detection, and node classification. Although many quantum-walk-based graph algorithms have been extensively studied, specific quantum circuits for implementing these algorithms have not yet been provided. To address this issue, we present a circuit design for implementing the discrete-time quantum walk on complex networks. We investigate the functionality of our circuit using the small-sized Watts-and-Strogatz model as the complex network model, comparing it with theoretical calculations. This work offers a new approach to constructing quantum circuits for implementing quantum walks on arbitrary complex networks.
- 15 September 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 02, 376-377
Circuit Implementation of Discrete-Time Quantum Walks on Complex Networks
In this paper, we propose a circuit design for implementing quantum walks on complex networks. Quantum walks are powerful tools for various graph-based applications such as spatial search, community detection, and node classification. Although many quantum-walk-based graph algorithms have been extensively studied, specific quantum circuits for implementing these algorithms have not yet been provided. To address this issue, we present a circuit design for implementing the discrete-time quantum walk on complex networks. We investigate the functionality of our circuit using the small-sized Watts-and-Strogatz model as the complex network model, comparing it with theoretical calculations. This work offers a new approach to constructing quantum circuits for implementing quantum walks on arbitrary complex networks.
- Open Access
QWalkVec: Node Embedding by Quantum Walk
In this paper, we propose QWalkVec, a quantum walk-based node embedding method. A quantum walk is a quantum version of a random walk that demonstrates a faster propagation than a random walk on a graph. We focus on the fact that the effect of the depth-first search process is dominant when a quantum walk with a superposition state is applied to graphs. Simply using a quantum walk with its superposition state leads to insufficient performance since balancing the depth-first and breadth-first search processes is essential in node classification tasks. To overcome this disadvantage, we formulate novel coin operators that determine the movement of a quantum walker to its neighboring nodes. They enable QWalkVec to integrate the depth-first search and breadth-first search processes by prioritizing node sampling. We evaluate the effectiveness of QWalkVec in node classification tasks conducted on four small-sized real datasets. As a result, we demonstrate that the performance of QWalkVec is superior to that of the existing methods on several datasets. Our code will be available at \url{https://github.com/ReiSato18/QWalkVec}.
Open AccessQWalkVec: Node Embedding by Quantum Walk
In this paper, we propose QWalkVec, a quantum walk-based node embedding method. A quantum walk is a quantum version of a random walk that demonstrates a faster propagation than a random walk on a graph. We focus on the fact that the effect of the depth-first search process is dominant when a quantum walk with a superposition state is applied to graphs. Simply using a quantum walk with its superposition state leads to insufficient performance since balancing the depth-first and breadth-first search processes is essential in node classification tasks. To overcome this disadvantage, we formulate novel coin operators that determine the movement of a quantum walker to its neighboring nodes. They enable QWalkVec to integrate the depth-first search and breadth-first search processes by prioritizing node sampling. We evaluate the effectiveness of QWalkVec in node classification tasks conducted on four small-sized real datasets. As a result, we demonstrate that the performance of QWalkVec is superior to that of the existing methods on several datasets. Our code will be available at \url{https://github.com/ReiSato18/QWalkVec}.
- 10 February 2020
- Published by American Physical Society (APS) in Physical Review A
- Vol. 101 (2) , 022312
Scaling hypothesis of a spatial search on fractal lattices using a quantum walk
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 optimal number of oracle calls, where the exponent is given by for and the inverse of the spectral dimension for . We also propose a scaling hypothesis for the effective number of oracle calls defined by the ratio of the 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.- 10 February 2020
- Published by American Physical Society (APS) in Physical Review A
- Vol. 101 (2) , 022312
Scaling hypothesis of a spatial search on fractal lattices using a quantum walk
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 optimal number of oracle calls, where the exponent is given by for and the inverse of the spectral dimension for . We also propose a scaling hypothesis for the effective number of oracle calls defined by the ratio of the 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.- Open Access
Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
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.Open AccessScaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
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.