W-State as a OHE Scheme for Efficient Path Selection on Quantum Random Walks

Random walks are a promising area, where quantum computing could provide a speed advantage over classical computing. All random walks require a means to randomly select the direction of the path as it leaves each node. Previous quantum random walk approaches have used a “coin toss” approach, by taking advantage of the inherent randomness generated by a Hadamard gate applied to a qubit(s), to randomly select which edge to traverse. Inspired by AI's common use of one-hot encoding (OHE) and noting that W-State entanglement effectively generates a random OHE value, we designed and tested a OHE-based alternative for randomly selecting the next graph edge to travel. Though the “coin toss” approach has the advantage of requiring fewer qubits as the graphs increase in degree, our experiments confirmed that the approach had poor outcomes, at even slight graph size increases. In contrast, the OHE scheme was more successful at generating correct results when run on quantum hardware, indicating the trade-off of more qubits to obtain a usable outcome could be warranted. Neither would lead us to expect results adequate to perform large quantum random walks, but, provide guidance that the OHE approach is likely a step forward in that direction.