Classiq
Quantum Walks for Search and Graph Analysis - Classiq and Quantum Coalition “Implementation Challenge”
Greetings!! We (@ManjulaGandhi, @sgayathridevi, @Sasika2003, and @Abinaya-29751) aim to implement Quantum Walks for Search and Graph Analysis, based on the approach outlined in the research paper "Spatial Search by Quantum Walk" (A.M. Childs, J. Goldstone, 2003). Specifically, we will construct quantum circuits to leverage quantum walks for efficient search and traversal in large graphs, with applications in network analysis, database searching, and AI-driven optimization.
The attached proposal contains a detailed plan and implementation approach. Please refer to it. Quantum Walks for Search and Graph Analysis.pdf
Would love to hear feedback and explore possible collaborations for implementation on Classiq’s platform. Looking forward to your insights!
Sounds good @Abinaya-29751 ! this is a canonical technique in quantum computation that is currently absent in our library.
Are you planning to treat a specific use-case of this approach?
Thank you for your response! Since this technique is currently absent in the library, I would love to understand how you envision its implementation. Are there any references or guidelines that could help me get started?
Regarding specific use cases, we plan to focus on three primary applications:
Network Analysis – Implementing quantum centrality measures to identify important nodes in social and transportation networks, aiding influence modeling and infrastructure optimization.
Database Search – Developing quantum-enhanced search algorithms for large structured datasets, demonstrating a quadratic speedup in practical data retrieval scenarios.
Combinatorial Optimization – Applying quantum walks to tackle routing problems (such as simplified TSP instances), relevant for logistics and supply chain management.
For our initial implementation, we plan to prioritize the Database Search Application , as it most directly demonstrates the quantum advantage described in the Childs & Goldstone paper and provides a clear benchmark against classical algorithms.
We would appreciate guidance on which of these use cases would be most valuable to prioritize for the Classiq platform, along with any suggestions for setting up appropriate test scenarios. Looking forward to your insights!
Hi @Abinaya-29751 , I think that data search on some simple graph should be a good initial example. If you can treat some well-known example from the literature that would be wonderful (I do not have one in mind right now). The main guidelines I have is to try to build the algorithm in a high-level description (as much as this specific approach allows). You can take a look at our Grover's algorithm examples, or the Deutsch-Jozsa algorithm example. You can see that the algorithm is defined in a modular way once, and then is called with different oracles.
Feel free to reach out to the community for any questions! Good luck!
(Please note that we accept high-quality implementations to our repository and will be glad to accept a contribution that meets our standards).
Thank you for your guidance! I appreciate the suggestion to start with data search on a simple graph as an initial example. I’ll look into well-known examples from the literature and align the implementation with Classiq’s modular approach, as seen in the Grover’s algorithm and Deutsch-Jozsa examples.
I’ll also ensure the implementation follows best practices for high-level abstraction while maintaining flexibility for different oracle definitions. If I encounter any challenges, I’ll reach out to the community for support.
I’ll begin drafting the initial design and will share an update soon. Please let me know if there are any specific preferences or constraints I should keep in mind during implementation.
Looking forward to contributing a high-quality implementation that meets Classiq’s standards!
Hi @TomerGoldfriend @orsa-classiq @NadavClassiq
I have implemented two versions of the Quantum Walks for Search and Graph Analysis:
Generalized Version: This version only sets up registers to store the nodes of a graph without encoding specific edges or transitions.
4-Node Specific Version: This explicitly encodes the graph structure and transitions for a fixed 4-node graph.
Could you provide feedback on which approach aligns better with Classiq’s framework? Would you recommend further generalization, or should we focus on optimizing for specific graph structures? Additionally, what improvements can be made to enhance efficiency or adaptability?
@Abinaya-29751 the if the specific version uses the generalized version then this is perfect. It will be good to eventually have an end-to-end example for a specific graphs. Did you submit a PR?
Hi @TomerGoldfriend
As of now we have done this for a 4 qubit graph by searching for a specific node. We need to generalize this code but while trying in classiq platform by creating new model we were not able to synthesize the general code because we got the error that the size of the graph must be explicitly specified. We are working to sort that error.
Below I have attached the documentation for 4-Node Specific Version: This explicitly encodes the graph structure and transitions for a fixed 4-node graph.
https://platform.classiq.io/circuit/2vA4wse5SGyM2jR52EmrnISFd9k
Quantum Graph Search Algorithm Documentation.docx
We did not submitted the PR yet.
@Abinaya-29751 did you open a PR? Are you still facing an error when trying to implement a general example? Feel free to reach out to the community for support.
We haven't done the PR We have done coding part in classic studio while running the circuit we are getting "Classic Internal Server Error". We have asked about this in Slack but they also dont know how to solve it. Can you help us to solve this error.
We have asked about this in Slack but they also dont know how to solve it. Can you help us to solve this error. @Abinaya-29751 please tag me on slack in your question thread.
