Quantum trend-detection algorithm

[0001] None

[0002] The field of the invention relates to a method and system for identifying trends in data.

[0003] The amount of data and information obtained on networks has increased substantially in the past few years. Examples of these networks include, but are not limited to, social media networks in which participants exchange information with each other, networks for the Internet of Things with sensors for measuring interrelated physical parameters, or financial networks for financial instruments, such as currency markets or stock exchanges, in which trades in one type of financial instruments affect the pricing and trade in other types of financial instruments.

[0004] Organizations have developed various methods to monitor this information and data and to use the data and the information to draw and act on conclusions from the data. For example, an organisation monitoring a social network may wish to monitor promotion of brands on the networks by influencers and “ordinary” participants in the social network using trend indicators. Banks and other financial organisations may wish to model economies to determine whether economic intervention is necessary to re-adjust an economy. Manufacturing industries may wish to use their sensor data to optimise production based on trends in pricing of raw materials and/or pricing of manufactured goods.

[0005] There are numerous examples of such systems in which parameters representing the data or the information can be continuously measured. These parameters are not static, and the values of the parameters are also dependent on the values of other ones of the parameters in the system. Calculation of trends within such a system is highly complex and resource intensive. It is well-known that an increase in the number of measured parameters increases the understanding of the operation of the system. This increase, however, results in an exponential increase in the amount of processing time. The limitation of current computing systems means that the number of parameters measured needs to be limited. The limitation of the number of measured parameters will often lead to a resulting loss in the insights into the system that can be extracted from the measurements of such parameters.

[0006] There are a number of prior art documents illustrating methods for analysing trends in data. For example, international patent application No WO2018/118982 (Estia, Inc.) teaches a method for analyzing time series data associated with networks, e.g., social networks, and subsequently publishing information that is associated with a category within the network. The method described in the WO982 publication involves a social media network and teaches receiving a first set of data points by a processor. The data points indicate a number of items published on a network during a time period. The items are associated with a category. A model is created and trained using a training set to describe a time series of the first set of data points. The model is employed to determine a predicted number of items that are published on the network during a subsequent time period, associated with the category. The category can be for example a brand of a product or a service or a more generic type of service. The information that is associated with the category is subsequently published by the processor within the network, based on the predicted number of items, by the processor. The information targets set of users to receive the subsequently published information relating to the category within the network. The model is created using techniques, such as a least means square algorithm, a normalized least mean square algorithm, or a recursive least squares algorithm.

[0007] A mathematical model to describe an online social network is taught in Chinese Patent Application No. CN 112016036 A (Harbin Univ).

[0008] US Patent Application No US 2021/0089953 (Microsoft) teaches a so-called quantum AI prediction system for predicting data bits in a time-sequential sequence of data points. The prediction system comprises a quantum prediction circuit adapted to receive an input vector representing a subset of the time-sequential sequence, encode the input vector as a corresponding qubit register, apply a trained quantum circuit to the qubit register; and measure one or more qubits output from the quantum prediction circuit to infer a next data point in the time-sequential sequence following the subset of the time-sequential sequence represented by the input vector.

[0009] The AI quantum predictor of the US '953 patent application is trained via a supervised learning technique to use pattern recognition to predict a “next” data point in a time-sequential sequence of points, even in cases where the point does not yet exist in the real world. The time-sequential data sequence may be any sequence of data points collected in a time-sequential manner including, for example, data points representing weather patterns (e.g., temperature trends), economics data, human decision making, etc.

[0010] There is a need therefore to develop a method and system which is able to process the parameters relating to the data and obtain insights, such as trends, in a time-efficient manner, requiring fewer computing resources, to enable operators of the systems to take action.

[0011] This document teaches a computer-implemented method and system for identifying trends in a network of elements. The method comprises obtaining a plurality of properties for the elements in the network, creating a multi-dimensional configuration space from the measured plurality of properties and storing the multi-dimensional configuration space in data storage. A cost function which is representative of the trends in the network is then built and the cost function is passed to a quantum processor for solving to identify a minimum in the cost function. The identified minimum is processed extract in a central processing unit the trends from the identified minimum. The cost function has one or more components which are representative of interaction between different elements in the network.

[0012] The use of the quantum processor enables the calculation of the minima in the cost function to be carried out much faster than using conventional computers and enables more factors to be considered. In one aspect, the quantum processor is a quantum annealing processor.

[0013] The solving of the cost function comprises a step of creating a tensor network and iteratively updating coefficients of tensors in the tensor network. The iterative updating concludes when all of the coefficients of the tensors have been updated at least once, after a predefined number of iterations, or after reaching a convergence criterion.

[0014] The elements of the network can be participating users in a social media network, economic parameters in a financial system, or sensors in an industrial network.

[0015] The system for identifying trends in a network of elements comprises a plurality of input/output devices for obtaining a plurality of properties for the elements in the network, a data storage unit for storing a multi-dimensional configuration space from the plurality of properties), a central processing unit for building a cost function representative of the trends in the network, and a quantum processor for receiving the cost function from the central processing unit and solving the cost function to identify a minimum in the cost function.

[0019] The invention will now be described with reference to the drawings. It will be understood that the embodiments and aspects of the invention described herein are only examples and do not limit the protective scope of the claims in any way. The invention is defined by the claims and their equivalents. It will be understood that features of one aspect or embodiment of the invention can be combined with a feature of a different aspect or aspects and/or embodiments of the invention.

[0020] FIG. 1 shows an overview of a computing system 10 for implementing the method of this document. The computing system 10 is a hybrid quantum and classical system and comprises, in an example, a central processing unit 20 which is connected to a data storage unit 25 (i.e., one or more memory devices), and input/output devices 30. A graphics processing unit 35 for processing vector calculations and a field programmable gate array (FGPA) 40 for control logic are connected to the central processing unit 20. A quantum processor 50 (also termed quantum accelerator) is connected to the central processing unit 20.

[0021] In one implementation of the computing system 10, the quantum processor 50 can be a quantum annealing system, such as one supplied by D-Wave, but this is not limiting of the invention. The computing system 10 is connected to a computer network 60, such as the Internet. It will be appreciated that the computing system 10 of FIG. 1 is merely exemplary and other units or elements may be present in the computing system 10. It will also be appreciated that there may be many input/output (I/O) devices 30 located at multiple locations and that there may be a plurality of data storage units 25 also located at multiple locations. The many I/O devices and data storage units 25 are connected by the computer network 60.

[0022] The computer network 60 is accessed by a large number of users 70 through, for example, their personal computers, smartphones and/or tablets.

[0023] FIG. 2 shows a flow diagram of the implementation of the method of this application. The application will be described with respect to a method of determining trends in a social network 65 which is part of or can be accessed from the computer network 60. One non-limiting example of the social network 65 is a social media network, such as but not limited to Twitter, Facebook, Instagram, etc., in which a large number of the individuals 70 participate using their input devices 66.

[0024] The method starts at step 200 and, in an initial step 203, a plurality of values relating to the participating individuals 70 is gathered. A multi-dimensional configuration space 75 is defined for the participating individuals 70. In this example, the participating individuals 70 form the points of the configuration space 75. The multi-dimensional configuration space 75 includes a plurality of properties for the points. This configuration space 75 is stored in one or more of the data storage units 25 and indeed multiple copies of the configuration space 75 may be stored in different ones of the data storage units 25 or spread across different data storage units 25. Values relating to the participating individuals 70 are already obtained in step 203 and placed in this configuration space 75 with differing values for differing properties of the individuals 70 according to their activities in the social network 65.

[0025] The configuration space 75 has a plurality of different axes, whereby the different axes corresponding to different properties of the individuals 70 in the social network 65. Extreme points of these axes correspond to opposite trends. For the sake of simplicity, let us consider for the time being a simple binary case, say, “black-white” or “democrat-republican”. These exemplary binary values represent the properties of the individuals. The individuals 70 (denoted by i in the following equations) have their own (personal) ideological configuration space, and their ideological preferences define the point on this configuration space 75. This “state” of the personal ideological configuration space is influenced by many factors, such as likes and dislikes of statements in the social networks 65 by other ones of individuals 70 (denoted by j in the following equations) in the social networks 65. The state of the personal ideological configuration space can also be influenced by external factors. Such external factors include, but are not limited to political scandals, wars, and economic crises.

[0026] This configuration space 75 can be modelled by a cost function. Let us assign a two-dimensional vector {right arrow over (S_i)} to the I users 70 participating in the social network 65. The two-dimensional vector {right arrow over (S_i)} has a unit length which is given by the Equation 1:
{right arrow over (S_i)}=cos θ_i·+sin θ_i·
in which θ_i∈[0, 2π] and , are two orthonormal vectors. The vector is normalized to one (i.e., {right arrow over (S_i)}=1), and the angle θ_i parametrizes the position of the participating i users 70 in a single-axis ideological space.

[0027] It is now possible to build a cost function in step 210 which to be is minimized by a configuration that globally satisfies as much as possible all constraints of the equation in the social network 65 and provides information about trends in the network 60. The cost function is built in the central processing unit 20.

[0028] The first term of the cost function takes into account the external influence environment of the participating users 70. There can be positive influence on the users 70, i.e., ideological alignment, as well as negative influence, i.e., ideological disalignment. This positive and/or negative influence is modelled via two-variable terms tending to align/anti-align vectors. Let us term P_i and N_i as the sets of respectively the positive influencers and the negative influences on the individual i. This first element of the cost function C₁ is then given by Equation 2:

[0029] $C_1=-\sum _{i,j\in P_i}\overrightarrow{S_l}·\overrightarrow{s_j}+\sum _{i,j\in N_i}\overrightarrow{S_l}·\overrightarrow{s_j}$

[0030] This first term of the cost function C₁ will be internally correlated since the different sets P_i and N_i partially overlap amongst different ones of the participating individuals i as many of the participating individuals will be influenced both positively and negatively by other ones of the participating individuals j.

[0031] In a further aspect of the disclosures, it is possible to include in Equation 2 further terms in the cost function to enable the polarization of specific trends. Examples include so-called “a priori trends” for one of the users i. These are trends that are not influenced by the other ones of the participating users j in the social network 65 but are due to other individual polarising factors. These other individual factors include, but are not limited to, the i user's past experiences and opinions on other subjects uninfluenced by the other participating users j. The cost function C₂ for the priori trends is given by Equation 3:

[0032] $C_2=-\sum _i\overrightarrow{h_l}·\overrightarrow{S_l}$
in which {right arrow over (h_i)} represents the polarising factors. It will be appreciated that for those individuals with a fixed trend, the vector {right arrow over (S_i)} is not a variable but has a fixed set of parameters in the configuration space 75.

[0033] More generally all the information present in the social network 65 can be codified in the cost function of Equation 4:
C=C₁+C₂+C₃
in which C₃ represents any further external factors affecting the trends.

[0034] There is now a need to identify the configuration minimising this cost function C. The factors of the individual elements of the cost function which will correspond to the most reasonable trends in the network.

[0035] The calculation of the cost function is a linear algebra problem and, with a conventional processor, such as the central processing unit 20, the graphics processing unit 35 and/or the FPGA 40 (or a combination of them) is challenging because this is an NP problem (nondeterministic polynomial problem) in which the calculation time for the linear algebra problem is an exponential function of the number of variables that need to be calculated.

[0036] In other words, for a small number of dimensions it would be possible to calculate the minimum of the cost result within a reasonable amount of time. However, conventional computers will require significant amounts of time for larger numbers and cannot do this calculation in “real time” which is required for a trend analysis. It is therefore necessary to solve the linear algebra algorithms using quantum linear algebra algorithms, such as variational quantum single value decompositions, QM/MM, quantum-ED (exact diagonalization) or quantum principal components analysis.

[0037] Having created the configuration space in 205 and the cost function in step 210, the next step 215 is to create an initial tensor network in the central processing unit 20 and stored in the data storage unit 25 using the central processing unit 20. The tensor network is a representation of a vector in the multidimensional configuration space 75 which is spanned by all possible configurations of the variables relating to the users 70. A matrix product state can be used to represent the tensor network.

[0038] An initial tensor (labelled t) is selected in step 220 from the tensor network created in the previous step 215. The selection 220 of the initial tensor t is arbitrary. It may the first one of labelled tensors. For instance, in a one-dimensional tensor network, in which the tensors are arranged linearly along a line, the selection could be from one boundary or end of the line to the other boundary.

[0039] The coefficients of the tensor t then need to be updated in step 227 such as way such that the value of the cost function C (Equation 4) established in step 210 is minimised. An updating of the coefficients of the tensor t is done by passing the cost function in step 222 to the quantum processor 50 and carrying out the linear algebra operations in step 225 in the quantum processor 50 to identify a minimum, as discussed above.

[0040] The linear algebra operations are carried out using a density matrix renormalization group (DMRG) algorithm to find the lowest energy eigenstate of the Hamiltonian representing the tensor network. The operation in step 225 proceeds by minimizing the expectation value of the Hamiltonian. The expectation value is computed from the matrix product state representing the tensor network.

[0041] The linear algebra operations need to be repeated many thousands of times in order to update in step 227 the coefficients of the tensor. After a specified number of operations, at step 230 a check is made—called a sweep, in which a check is carried out to see whether all of the coefficients in the tensors of the tensor network have been updated sequentially, for example, one or twice. If this sweep criterion is not fulfilled, then the tensor t still needs to be updated and proceeds back to step 235 to carry out further linear algebra operations.

[0042] Once the sweep criteria are checked in step 230, a check is carried out in step 235 on the tensor t to see whether an overall criterion has been fulfilled. This overall criterion is typically whether the system has reached a pre-defined number of iterations in step 225 or whether certain ones of the tensor parameters have reached a predefined convergence. If this overall criterion is not fulfilled in step 235 then the method continues updating the coefficients in step 230.

[0043] Finally in a following step 240 a check is carried out to see if the method has reached global predefined convergence criteria. The global convergence criteria are chosen so that the current result of the tensor t should be close to a near-optimal solution of the optimization problem for the cost function. Depending on the result of this step 240, then the computing system 10 can change in step 245 precision parameters of the method. These precision parameters could be bond dimensions of the tensor network, unit cell of the tensor network, number of iterations in the previous steps, Trotter-step in imaginary-time evolution, error tolerance in the linear algebra subroutines, etc. In most cases, only those parameters of the tensor network are modified. The steps of the method from step 225 are repeated with the modified precision parameters.

[0044] If the criteria check in step 240 is successful, then the method continues and provides an output that corresponds to a proposed configuration with the solution of the variables of the cost function C. These variables correspond to the trends in the social network 65.

[0045] Another approach to identifying trends in data will now be explained.

[0046] In this approach, the cost function C is discretized so that the formulation only includes binary variables. in this case the values of cos θ_i and sin θ_i are written as follows:

[0047] $\cos {\theta }_i=\sum _{a=0}^n{x}_{i,a}{2}^{-a}$ $\mathrm{and}$ $\sin {\theta }_i==\sum _{a=0}^n{y}_{i,a}{2}^{-a}$
in which x_i,a and y_i,a are the classical bit variables for i, and a=1, 2 . . . , n.

[0048] To fulfil the constraint that (cos θ_i)²+(sin θ_i)²=1, it is necessary to add the penalty term:

[0049] $C_i=\left({\left(\sum _{a=1}^n{x}_{i,a}{2}^{-a}\right)}^2+{\left(\sum _{a=1}^n{y}_{i,a}{2}^{-a}\right)}^2-1\right)$

[0050] To fulfil the constraint that (cos θ_i)²+(sin θ_i)²=1, it is necessary to add the penalty term:

[0051] $C_i=\left({\left(\sum _{a=1}^n{x}_{i,a}{2}^{-a}\right)}^2+{\left(\sum _{a=1}^n{y}_{i,a}{2}^{-a}\right)}^2-1\right)$
which is minimized whet the constrain is satisfied so that C_i≈0.

[0052] The final cost function is a higher order unconstrained binary optimization problem (HUBO) given by:

[0053] $C^{\prime }=C\left(x_{i,a},y_{i,a}\right)+\gamma \sum _i{C}_i$

• • [0054] in which γ>1.

[0055] This above cost function can be optimized using Noisy Intermediate-Scale Quantum (NISQ) devices as the quantum processor. This optimization is done for instance by implementing a Variational Quantum Eigensolver (VQE) algorithm, which minimizes the function via (say) gradient descent using a quantum circuit ansatz that can contain different amounts and structure of quantum entanglement as well as variational parameters. This option can be implemented using a variety of quantum hardware architectures, such as superconducting qubits, trapped ions, and neutral atoms. Additionally, other optimization quantum algorithms would be possible, such as the Quantum Approximate Optimization Algorithm (QAOA), as well as quantum annealing on current superconducting quantum annealing devices.

Other Applications

[0056] The method listed above can be used in other applications, such as financial methods, including trends in stock markets or electricity demands, or identifying trends in sensor readings. For example, predictive maintenance of machines in an operating plant by can be calculated using the method outlined in this application. In a further aspect, it would be possible to use the method to predict patient outcomes and potential health crises.

[0057] The foregoing description of the preferred embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. The embodiment was chosen and described in order to explain the principles of the invention and its practical application to enable one skilled in the art to utilize the invention in various embodiments as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents. The entirety of each of the aforementioned documents is incorporated by reference herein.

• • [0058] 10 Computing system
  • [0059] 20 Central processing unit
  • [0060] 25 Data storage
  • [0061] 30 Input/output devices
  • [0062] 35 Graphics processing unit
  • [0063] 40 Field programmable gate array
  • [0064] 50 Quantum processor
  • [0065] 55 Input devices
  • [0066] 60 Computer network
  • [0067] 65 Social Network
  • [0068] 70 Individuals
  • [0069] 75 Configuration space