Abstract
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.