Invention:
This invention is a new classical algorithm used to classify if two graphs are vertex-minor equivalent or not, an NP complete problem which improves on prior results using currently published well-known classical algorithms. The inventors also introduce a new classical algorithm based on graph spectra that outperforms other classical algorithms and demonstrate that, on reasonable assumptions of loss and squeezing parameters, this quantum algorithm performs better than classical algorithms. Furthermore, the innovative approach of combining classical and quantum methods presents new possibilities for tackling complex computational problems in graph theory.
Background:
This hybrid quantum-classical algorithm solves the well-known NP-complete problem of determining if two given graphs are a vertex minor of one another. The inventors found a way to map a graph into GBS that allows trading between the one-shot classification accuracy and the amount of squeezing needed at the input, a hard-to-produce quantum-optical resource. This mapping to GBS not only optimizes the computational resources but also opens doors for new research avenues in quantum computing and graph theory.
Classification of vertex-minor graphs has been primarily tackled using traditional classical algorithms, which often prove inefficient and time-consuming for large and complex graph structures. The existing methodologies lack the flexibility to adapt to the various challenges of graph theory, leading to limitations in both research and practical applications.
Applications:
- Quantum computing
- Graph theory and analytics
- Complex network analysis
- Optimization in various industrial applications
Advantages:
- Greater efficiency
- Faster processing
- Enhanced flexibility in handling complex problems
- Potential cost reduction in computational resources
- Innovative integration of classical and quantum techniques
