Linear-depth quantum system for topological data analysis

Patent metadata

Field	Value
Publication number	US-2024028939-A1
Application number	US-202217863524-A
Country	US
Kind code	A1
Filing date	Jul 13, 2022
Priority date	Jul 13, 2022
Publication date	Jan 25, 2024
Grant date	—

Abstract

A quantum computer-implemented system, method, and computer program product for quantum topological domain analysis (QTDA). The QTDA method achieves an improved exponential speedup and depth complexity of O(n log(1/(δ∈))) where n is the number of data points, ∈ is the error tolerance, δ is the smallest nonzero eigenvalue of the restricted Laplacian, and achieves quantum advantage on general classical data. The QTDA system and method efficiently realizes a combinatorial Laplacian as a sum of Pauli operators; performs a quantum rejection sampling and projection approach to build the relevant simplicial complex repeatedly and restrict the superposition to the simplices of a desired order in the complex; and estimates Betti numbers using a stochastic trace/rank estimation method that does not require Quantum Phase Estimation. The quantum circuit and QTDA method exhibits computational time and depth complexities for Betti number estimation up to an error tolerance ∈.

First claim

What is claimed is:

1 . A system for topological domain analysis comprising:
a controller configured to generate command signals; quantum hardware including a plurality of qubits encoding an input dataset comprising a plurality of data points, a topology of the dataset is represented by a simplicial complex; an interface connected to the controller and the quantum hardware, the interface being configured to control the quantum hardware based on the command signals to implement a first quantum circuit configured to simulate a boundary map operator that creates a mapping of boundaries of a given graph having at least nodes and edges formed using said input dataset, the quantum circuit having linear depth relative to number of nodes in the given graph; the interface being configured to further control the quantum hardware to implement a second quantum circuit configured to simulate a combinatorial Laplacian of simplices of a specific order in the simplicial complex based on the simplicial complex and boundary map operator; and a hardware processor configured to estimate Betti numbers by computing a stochastic rank estimation of the combinatorial Laplacian and obtain one or more features of said input dataset based on a Betti number estimate.

2 . The system of claim 1 , wherein a number of quantum gates in the quantum hardware has a linear relationship with the number of vertices in the given graph.

3 . The system of claim 1 , wherein the boundary operator is represented in terms of a sum of Pauli spin operators, and wherein fermionic creation and annihilation operators are mapped to the Pauli spin operators.

4 . The system as claimed in claim 1 , further comprising:
further quantum hardware for generating a first projector onto all simplices using quantum sampling and control-based projection, said combinatorial Laplacian of simplices simulated by an interleaving of the first projector with said boundary operator, said system further comprising: a further controller configured to generate a command signal; a further interface connected to the controller and the further quantum hardware, the further interface being configured to control the further quantum hardware based on the command signal received from the further controller to perform pairwise checking for every pair of data points in a dataset to identify a property relating to the data points.

5 . The system of claim 4 , wherein:
the plurality of datapoints of said dataset comprises n data points; the further quantum hardware is configured to:
perform n−1 iterations of pairwise checking; and
perform pairwise checking on n/2 pairs of data points in each iteration of pairwise checking.

6 . The system of claim 5 , wherein for each iteration of pairwise checking, the n/2 pairs of data points that undergo the pairwise checking is selected using a cyclic shift technique, and the n/2 pairs of data points are checked in parallel.

7 . The system of claim 4 , further comprising:
another quantum hardware for generating a second projector onto all k-simplices of the simplicial complex using quantum sampling and control-based projection, wherein said another quantum hardware comprises: a plurality of qubits including a first set of qubits and a second set of qubits, wherein the first set of qubits represents elements of an input vector having mixed states with different Hamming weights, and the second set of qubits represent a count of nonzero elements in the input vector; the further interface being configured to control the another quantum hardware to:
sample the input vector;
entangle the first set of qubits to the second set of qubits; and
generate an output vector based on the entanglement of the first set of qubits to the second set of qubits, wherein the output vector includes one or more states having a specific Hamming weight.

8 . The system as claimed in claim 7 , wherein:
the input vector corresponds to a dataset comprising a plurality of data points, and a topology of the dataset is represented by a simplicial complex; the simplicial complex comprises n vertices; the first set of qubits comprises n qubits; the second set of qubits comprises log(n) qubits; and wherein the output vector projects simplices of an order k on the simplicial complex based on the entanglement of the first set of qubits and the second set of qubits.

9 . The system as claimed in claim 1 , wherein said further interface is further configured to control the further quantum hardware based on the command signal received from the controller to:
generate a random state vector represented by the plurality of qubits, wherein the random state vector comprises a specific number of independent entries; use the random state vector to determine moments of a matrix corresponding to a Laplacian of simplices of a specific order in a simplicial complex; and the further controller being further configured to output the moments of the matrix to the hardware processor to estimate a trace of the matrix using the moments.

10 . The system of claim 9 , wherein the estimation of Betti numbers of the simplicial complex is based on the estimated trace.

11 . The system of claim 10 , wherein the third quantum circuit is further configured to:
determine a quantum state that represents an application of the Laplacian to the random state vector; and determine a norm of the quantum state to determine the moments.

12 . The system of claim 9 , wherein estimation of the trace comprises averaging the moments over a number of samples used for generating the random state vector.

13 . The system of claim 1 , wherein said further interface is further configured to control the further quantum hardware based on the command signal received from the controller to:
determine a plurality of moments of a matrix using a random state vector represented by the plurality of qubits, the matrix corresponding to a combinatorial Laplacian of simplices of a specific order in a simplicial complex; and the further controller being further configured to output the plurality of moments of the matrix to the hardware processor to estimate a trace of a matrix function based on one or more selected moments among the plurality of moments, wherein the matrix function is a function of the matrix.

14 . The system of claim 13 , wherein the trace of the matrix function is based on a set of polynomials determined based on the plurality of moments, the set of polynomials being a set of Chebyshev polynomials.

15 . A method for topological domain analysis using a quantum computing system, said method comprising:
receiving, by a controller of a quantum system, an instruction; generating, by the controller of the quantum system, a command signal based on the instruction; converting, by an interface of the quantum system, the command signal into a quantum operation; and based on the quantum operation, controlling quantum hardware including a plurality of qubits encoding an input dataset comprising a plurality of data points, a topology of the dataset is represented by a simplicial complex, said controlling quantum hardware configuring a first quantum circuit to simulate a boundary map operator that creates a mapping of boundaries of a given graph having at least nodes and edges formed using said input dataset, the first quantum circuit having linear depth relative to number of nodes in the given graph; and further controlling the quantum hardware to implement a second quantum circuit configured to simulate a combinatorial Laplacian of simplices of a specific order in the simplicial complex

Assignees

• IBM

Inventors

• Akhalwaya Ismail Yunus
• Ubaru Shashanka
• Clarkson Kenneth Lee
• Squillante Mark S
• Kalantzis Vasileios
• Horesh Lior

Classifications

• G06N10/40 Primary

  Physical realisations or architectures of quantum processors or components for manipulating qubits, e.g. qubit coupling or qubit control · CPC title

• G06N10/20

  Models of quantum computing, e.g. quantum circuits or universal quantum computers · CPC title

• G06N10/60 Primary

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · CPC title

• G06N3/08

  Learning methods · CPC title