License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License
- Reference by Douglas & Wang,
- Reference by Fujiwara.
Number of qubits n, number of steps t and coin operator C can be chosen.
q0 is the coin operator, qubits [1, n-1] are used for encoding the nodes in the line.
The multi-controlled Toffoli gate mct integrated in Qiskit is used, needing O(n) auxiliary qubits, and using O(n) basic gates. Since a step of the QW needs O(n) such operations, the use of gates grows as O(n^2).
Total gate count of one QW step vs. number of qubits (coin + nodes).
Other implementations of the mct gate use O(n^2) gates without auxiliary qubits, making the total gate count grow as O(n^3).
Total gate count grows as O(n^2) with no need of auxiliary qubits.