US-12626175-B2 - Spectral clustering of graphs on fault tolerant and noisy quantum devices

US12626175B2US 12626175 B2US12626175 B2US 12626175B2US-12626175-B2

Abstract

A method for node cluster assignment in a graph includes initializing a plurality of wavefunctions, each one of the plurality of wavefunctions corresponding to nodes of the graph, constructing a plurality of quantum circuits, each corresponding to a graph Laplacian of the graph, evolving the plurality of wavefunctions at the plurality of quantum circuits, each one of the plurality of wavefunctions being evolved to a different time than other ones of the plurality of wavefunctions, measuring evolved states of the plurality of wavefunctions to generate a time-evolved wavefunction vector, and identifying a cluster assignment of a node of the graph based on the time-evolved wavefunction vector.

Inventors

Tuhin Sahai
Hari Kiran Krovi

Assignees

RAYTHEON COMPANY
RAYTHEON BBN TECHNOLOGIES CORP.

Dates

Publication Date: 20260512
Application Date: 20220617

Claims (12)

1 . A method for node cluster assignment in a graph, the method comprising: initializing a plurality of wavefunctions, each one of the plurality of wavefunctions corresponding to nodes of the graph; constructing a plurality of quantum circuits, each corresponding to a graph Laplacian of the graph; evolving the plurality of wavefunctions at the plurality of quantum circuits, each one of the plurality of wavefunctions being evolved to a different time than other ones of the plurality of wavefunctions; measuring evolved states of the plurality of wavefunctions to generate a time-evolved wavefunction vector; and identifying a cluster assignment of a node of the graph based on a spectrum of the time-evolved wavefunction vector.
2 . The method of claim 1 , wherein the graph comprises N nodes, N being an integer greater than 1, and wherein each one of the plurality of wavefunctions comprises a vector of N elements, each one of the elements being a function of time.
3 . The method of claim 2 , wherein the initializing the plurality of wavefunctions comprises: initializing each one of the plurality of wavefunctions to a same vector of random-valued elements.
4 . The method of claim 1 , wherein the plurality of quantum circuits are identical.
5 . The method of claim 1 , wherein the constructing the plurality of quantum circuits comprises: creating, for one of the plurality of quantum circuits, a plurality of quantum gates configured to perform coherent quantum operations corresponding to the graph Laplacian on quantum data.
6 . The method of claim 5 , wherein the quantum data comprises a plurality of qubits.
7 . The method of claim 1 , wherein the plurality of wavefunctions comprises M wavefunctions, M being an integer greater than 1, and wherein the evolving the plurality of wavefunctions at the plurality of quantum circuits comprises: evolving a j-th wavefunction of the plurality of wavefunctions for j time steps, j being an integer greater than 1 and less than M.
8 . The method of claim 1 , wherein the measuring the evolved states of the plurality of wavefunctions comprises: performing quantum state tomography on the plurality of quantum circuits to detect values of the plurality of wavefunctions and to generate the time-evolved wavefunction vector.
9 . The method of claim 8 , wherein the time-evolved wavefunction vector is expressed as [ψ(Δ t ),ψ(2Δ t ) . . . ψ( T max)] where ψ(t) represents a value of one of the plurality of wavefunctions at time t, Δt represents a time step of the evolution, and Tmax represents a maximum evolution time.
10 . The method of claim 1 , wherein the identifying the cluster assignment of the node of the graph comprises: estimating eigenvalues and one or more scaled components of eigenvectors of the graph Laplacian based on the time-evolved wavefunction vector; and determining a number of clusters and the cluster assignment of the node based on the eigenvalues and the one or more scaled components of the eigenvectors of the graph Laplacian.
11 . The method of claim 10 , wherein the estimating the eigenvalues and the one or more scaled components of the eigenvectors of the graph Laplacian comprises: performing a Fourier transform of the time-evolved wavefunction vector to generate a frequency domain wavefunction; identifying frequencies of peaks of the frequency domain wavefunction; estimating the eigenvalues as corresponding to the frequencies of the peaks; and calculating the one or more scaled components of the eigenvectors based on coefficients of the frequencies of the peaks.
12 . The method of claim 10 , wherein the determining the cluster assignment of the node of the graph comprises: identifying a number of clusters of the graph based on the eigenvalues of the graph Laplacian; and assigning the node to one of the clusters based on the one or more scaled components of the eigenvectors of the graph Laplacian.

Description

FIELD Embodiments of the present invention relate to the field of graph clustering. BACKGROUND Algorithms for graph analysis have a wide variety of applications such as routing, pattern recognition, database searches, network layout, and internet page ranking. Although some of the problems in these area can be solved efficiently on present day computing devices, several graph analysis problems are computationally intractable. For example, the problem of partitioning graphs into equal size clusters while minimizing the weights of cut edges arises in a range of settings such as social anthropology, gene networks, protein sequences, sensor networks, computer graphics, and internet routing algorithms. To avoid unbalanced cuts, size restrictions are typically placed on the clusters; instead of minimizing inter-connection strength, if one minimizes the ratio of the inter-connection strength to the size of individual clusters, the problem becomes NP-complete. In fact, the approximation problem is also NP-complete. The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known to a person of ordinary skill in the art. SUMMARY Aspects of some embodiments of the present invention are directed to a system and method for node cluster assignment using fault tolerant and noisy quantum devices. In some embodiments, quantum devices corresponding to a graph Laplacian of a graph are constructed and used to evolve a wavefunction corresponding to the graph Laplacian over time to determine the time-evolution of the wavefunction. The method and system according to embodiments of the present disclosure then perform spectral clustering based on the evolved wavefunction to determine the appropriate cluster for each node of the graph. According to embodiments of the present invention, there is provided a method for node cluster assignment in a graph, the method including: initializing a plurality of wavefunctions, each one of the plurality of wavefunctions corresponding to nodes of the graph; constructing a plurality of quantum circuits, each corresponding to a graph Laplacian of the graph; evolving the plurality of wavefunctions at the plurality of quantum circuits, each one of the plurality of wavefunctions being evolved to a different time than other ones of the plurality of wavefunctions; measuring evolved states of the plurality of wavefunctions to generate a time-evolved wavefunction vector; and identifying a cluster assignment of a node of the graph based on the time-evolved wavefunction vector. In some embodiments, the graph includes N nodes, N being an integer greater than 1, and each one of the plurality of wavefunctions includes a vector of N elements, each one of the elements being a function of time. In some embodiments, the initializing the plurality of wavefunctions includes: initializing each one of the plurality of wavefunctions to a same vector of random-valued elements. In some embodiments, the plurality of quantum circuits are identical. In some embodiments, the constructing the plurality of quantum circuits includes: creating, for one of the plurality of quantum circuits, a plurality of quantum gates configured to perform coherent quantum operations corresponding to the graph Laplacian on quantum data. In some embodiments, the quantum data includes a plurality of qubits. In some embodiments, the plurality of wavefunctions includes M wavefunctions, M being an integer greater than 1, and the evolving the plurality of wavefunctions at the plurality of quantum circuits includes: evolving a jth wavefunction of the plurality of wavefunctions for j time steps, j being an integer greater than 1 and less than M. In some embodiments, the measuring the evolved states of the plurality of wavefunctions includes: performing quantum state tomography on the plurality of quantum circuits to detect values of the plurality of the wavefunctions and to generate the time-evolved wavefunction vector. In some embodiments, the time-evolved wavefunction vector is expressed as [ψ(Δt), ψ(2Δt) . . . ψ(Tmax)] where ψ(t) represents a value of one of the plurality of wavefunctions at time t, Δt represents a time step of the evolution, and Tmax represents a maximum evolution time. In some embodiments, the identifying the cluster assignment of the node of the graph includes: estimating eigenvalues and one or more scaled components of eigenvectors of the graph Laplacian based on the time-evolved wavefunction vector; and determining the cluster assignment of the node based on the eigenvalues and the one or more scaled components of the eigenvectors of the graph Laplacian. In some embodiments, the estimating the eigenvalues and the one or more scaled components of the eigenvectors of the graph Laplacian includes: performing a Fourier transform of the time-evolved wavefunction vector