| KEYWORD |
Adopting Quantum Computing for Solving NP-Hard Problems on Graphs and Related Data Structures
keywords GRAPH, QUANTUM COMPUTING, SOCIAL NETWORK ANALYSIS
Reference persons BARTOLOMEO MONTRUCCHIO, STEFANO QUER
Research Groups DAUIN - GR-13 - METODI FORMALI - FM, GRAphics and INtelligent Systems - GRAINS
Thesis type EXPERIMENTAL AND THEORETICAL, NUMERICAL AND PROGRAMMING
Description The advent of quantum computing presents a striking opportunity to solve complex computational problems intractable for classical computers. NP-hard problems, particularly those involving graphs and related data structures (such as social networks), are of significant interest due to their applications in various fields, including optimization, logistics, cryptography, and network analysis. This research project aims to explore the potential of quantum computing to address NP-hard problems on graphs, leveraging quantum algorithms to achieve solutions computationally infeasible with traditional methods.
Quantum computing harnesses the principles of quantum mechanics to process information in fundamentally different ways than classical computing. Quantum bits (qubits) can exist in superpositions of states, enabling quantum computers to explore many possible solutions simultaneously. Quantum entanglement and quantum interference further enhance computational capabilities, providing potential exponential speedups for certain classes of problems.
NP-hard problems, including many graph-related problems, are characterized by their computational complexity. Solving these problems requires a time that grows exponentially with the input size, making classical computations inapplicable on large instances. Graphs have many practical applications, such as the ones in social networks where it may be necessary to identify influential nodes, community structures, and communication patterns.
Some examples of these problems are:
• Traveling Salesman Problem: Find the shortest possible route that visits each vertex once and returns to the origin vertex.
• Graph Coloring: Assign colors to vertices so that no two adjacent vertices share the same color to minimize the number of colors used.
• Clique Detection: Identify the most significant subset of vertices that forms a complete (i.e., fully connected) subgraph.
Quantum algorithms offer the potential to handle these analyses more efficiently, leading to deeper insights and more robust models.
Main steps and objectives:
• Literature Review: Conduct a thorough review of existing quantum algorithms applicable to NP-hard problems, such as Grover's search algorithm and the Quantum Approximate Optimization Algorithm.
• Develop Quantum Algorithms: Design and implement quantum algorithms tailored explicitly to graphs and adapt existing quantum methods for the same target.
• Optimization and Scalability: Optimize these algorithms for performance and scalability on current quantum hardware, addressing limitations in qubit count and error rates.
• Graph Data Structures: Extend the application of quantum algorithms to related data structures, focusing on social networks to uncover patterns and insights that are not easily detectable using classical methods.
• Comparative Analysis: Conduct a comparative analysis of quantum and classical approaches, evaluating the efficiency, accuracy, and practicality of quantum solutions in real-world scenarios.
Required skills To ensure this project's success, the candidate must possess skills covering aspects of quantum computing, classical algorithms, graph theory, and social network analysis.
Notes Expected outcomes:
• Innovative Quantum Algorithms: Create new or improved quantum algorithms capable of solving NP-hard problems on graphs more efficiently than classical methods.
• Performance Metrics: Propose comprehensive performance metrics and benchmarks illustrating the benefits and limitations of quantum computing for these problems.
• Enhanced Social Network Analysis: Demonstrate the potential of quantum computing to provide novel insights and more effective solutions for analyzing social networks.
Deadline 28/10/2024
PROPONI LA TUA CANDIDATURA