Quantum machine learning algorithm for knowledge graphs

1. A computer-implemented method of performing an inference task on a knowledge graph comprising semantic triples of entities, wherein entity types are subject, object and predicate, and wherein each semantic triple comprises one of each entity type, using a quantum computing device, wherein a first entity of a first type and a second entity of a second type are given and the inference task is to infer a third entity of a third type, comprising at least the steps of:

providing a query comprising the first entity and the second entity;

modelling the knowledge graph as a partially observed tensor {circumflex over (χ)} in a classical, non-transitory computer-readable memory structure;

providing a cutoff threshold, τ;

creating, from the partially observed tensor {circumflex over (χ)}, a density operator in a quantum random access memory, qRAM, on the quantum computing device;

preparing a unitary operator, U, based on the created density operator, comprising states on a clock register, C;

creating a first entity state |χ s (1) indicating the first entity on an input data register of the qRAM, wherein the first entity state is entangled with a maximally entangled clock register;

applying the prepared unitary operator to at least the first entity state;

performing thereafter a quantum phase estimation on the clock register, C;

performing thereafter a computation on the clock register, C, to recover singular values;

creating an auxiliary qubit in an auxiliary register, R, which is entangled with the first entity state resulting from the creating;

wherein the auxiliary register, R, has a first eigenstate |1 R and a second eigenstate |0 R ;

performing, on a result of the computation to recover the singular values, a singular value projection conditioned on the state of the auxiliary register, R, such that eigenstates whose squared singular values are to one side of the squared cutoff threshold, τ 2 , are entangled with the first eigenstate |1 R of the auxiliary register, R, and such that eigenstates whose squared values are to another side of the squared cutoff threshold, τ 2 , or equal to the squared cutoff threshold, τ 2 , are entangled with the second eigenstate |0 R of the auxiliary register, R;

measuring the auxiliary register, R, and post-selecting one of the two eigenstates |0 R ;

tracing out the clock register, C;

measuring the result thereof in a canonical basis of the input data register, wherein the canonical basis comprises tensor products of a basis connected to the second entity type and of a basis connected to the third entity type;

post-selecting the second entity in the basis connected to the second entity type to infer the third entity.

2. The method of claim 1 ,

wherein the partially observed tensor {circumflex over (χ)} is obtained such that, for each entry of the partially observed tensor {circumflex over (χ)}, the entry is, with a probability p:

directly proportional to a corresponding entry of a complete tensor χ modelling a complete knowledge graph; and

equal to 0 with a probability of 1−p,

with p being smaller than 1.

3. The method of claim 2 ,

wherein the cutoff threshold τ is chosen as smaller or equal to a quantity which is indirectly proportional to the probability p.

4. The method of claim 2 ,

wherein the probability p is chosen to be larger to or equal a maximum value out of a set of values.

5. The method of claim 4 ,

wherein the set of values comprises at least a value of 0.22.

6. The method of any of claim 4 ,

wherein the partially observed tensor {circumflex over (χ)} is expressable as a sum of the complete tensor χ and a noise tensor N, and wherein a desired value {tilde over (∈)}>0 is defined such that the Frobenius norm ∥⋅∥ F of a rank-r-approximation r of the noise tensor Υ is bounded such that ∥Υ r ∥ F ≤{tilde over (∈)}∥A∥ F , and wherein the set of values comprises at least one value that is proportional to r and indirectly proportional to {tilde over (∈)} to the n-th power, with n integer and n≥1.

7. The method of claim 6 ,

wherein the set of values comprises at least one value that is proportional to r and that is indirectly proportional to the square of {tilde over (∈)}.

8. The method of claim 6 ,

wherein the set of values comprises at least one value that is proportional to a square root of r and that is indirectly proportional to {tilde over (∈)}.

9. The method of claim 6 ,

wherein the set of values comprises at least one value that is independent of r and that is indirectly proportional to the square of {tilde over (∈)}.

10. A computing system comprising a classical computing device and a quantum computing device, wherein the computing system is configured to perform the method according to claim 1 .