Applications of graph theory to quantum computation

David Arcos Gutiérrez

[ANGLÈS] A theoretical base on quantum physics, quantum computing and mathematical models is the starting point for the development of the applications collection Quantum Graph Tool. It consists on four applications for the iOS operating system related to quantum computing and graph theory. To be more precise, the two main applications are interactive simulators of Grover’s quantum algorithm (to search in ordered lists) and Shor’s quantum algorithm (to factorize integer numbers). These applications aim to divulge quantum computing using mobile devices (iPad) and, in addition, they are tools to study new computing methods based on quantum mechanics’ properties. With the same objective, besides the applications, cumulative computing is introduced as a new computing method to solve problems in graph theory.

Sebastian Dörn

Yehui Tang, Junchi Yan, Edwin R. Hancock

Quantum computing (QC) is a new computational paradigm whose foundations relate to quantum physics. Notable progress has been made, driving the birth of a series of quantum-based algorithms that take advantage of quantum computational power. In this paper, we provide a targeted survey of the development of QC for graph-related tasks. We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions that can not be produced by classical systems efficiently for some problems related to graphs. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques designed for various tasks. Inspired by these powerful methods, we note that advanced quantum algorithms have been proposed for characterizing the graph structures. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research. We further discuss the challenges of using quantum algorithms in graph learning, and future directions towards more flexible and versatile quantum graph learning solvers.

Ankur Raina

Bharati R. Kale, Rani Desurkar, Jotiba P. Kitturkar +1 more

Farzaneh Shayeganfar, Ali Ramazani, Veera Sundararaghavan +1 more

Graph and network theory play a fundamental role in quantum computer sciences, including quantum information and computation. Random graphs and complex network theory are pivotal in predicting novel quantum phenomena, where entangled links are represented by edges. Quantum algorithms have been developed to enhance solutions for various network problems, giving rise to quantum graph computing and quantum graph learning (QGL). In this review, we explore graph theory and graph learning methods as powerful tools for quantum computers to generate efficient solutions to problems beyond the reach of classical systems. We delve into the development of quantum complex network theory and its applications in quantum computation, materials discovery, and research. We also discuss quantum machine learning (QML) methodologies for effective image classification using qubits, quantum gates, and quantum circuits. Additionally, the paper addresses the challenges of QGL and algorithms, emphasizing the steps needed to develop flexible QGL solvers. This review presents a comprehensive overview of the fields of QGL and QML, highlights recent advancements, and identifies opportunities for future research.