Quantum recommendation system

1. A computer-implemented method comprising:

training a quantum decision tree, comprising:

obtaining training data comprising data sets, wherein each data set comprises a value that corresponds to a target feature and multiple values that each correspond to a respective input feature of a set of input features;

assigning an input feature from the set of input features to a root node of a quantum decision tree, comprising:

for each input feature in the set of input features: calculating an information gain value for the input feature using values that correspond to the input feature; and

identifying, from the calculated information gain values, a maximal information gain value and assigning the input feature corresponding to the maximal information gain value to the root node;

creating a path from the root node, wherein creating the path comprises:

iteratively:

calculating a cumulative information gain value for unassigned input features based on i) multiple information gain values for respective input features that have been assigned to previous nodes on the path, and ii) probabilities that the unassigned input features are assigned to a current leaf node given the assigned input features to previous nodes on the path;

performing Monte Carlo simulations to generate respective modified cumulative information gain values; and

identifying, from the calculated cumulative information gain values, a maximal cumulative information gain value for the unassigned input features and assigning an unassigned input feature corresponding to the maximal cumulative information gain value to the current leaf node in the path creating a new leaf node, comprising identifying, from the modified cumulative information gain values, a maximal modified cumulative information gain value and assigning the input feature corresponding to the maximal modified cumulative information gain value to the current leaf node in the path;

receiving input data comprising data representing a user selected item and multiple values that each correspond to a respective input feature of the set of input features;

searching the trained quantum decision tree using a Grover algorithm to identify a path that matches the input data, wherein the path that matches the input data comprises one or more data items; and

providing the one or more data items as new items to recommend to the user.

2. The method of claim 1 , wherein the Monte Carlo simulations sample from a binomial distribution.

3. The method of claim 1 , wherein performing the Monte Carlo simulation comprises performing the Monte Carlo simulation using a quantum computer.

4. The method of claim 1 , further comprising storing the calculated cumulative information gain values identified as maximal, together with an identification of a corresponding path node i and input feature k in one or more lists.

5. The method of claim 1 , wherein calculating a cumulative information gain value for the unassigned input feature based on i) multiple information gain values for respective input features that have been assigned to previous nodes on the path, and ii) probabilities that the unassigned input feature is assigned to the current leaf node given the assigned input features to previous nodes on the path, comprises calculating

S

i

,

k

=

∑

j

=

0

i

(

1

-

GI

j

)

⁢

P

j

,

k

∑

j

=

0

i

(

1

-

GI

j

)

where i represents the current leaf node in the path for the iteration, k represents the unassigned input feature, j is an index representing previous nodes on the path, GI j represents an information gain value calculated using input feature values that correspond to the input feature assigned to node j, and P j,k represents a probability that the unassigned input feature k is assigned to the current leaf node given the assignment of input feature j.

6. The method of claim 1 , wherein the quantum decision tree is constructed to perform a machine learning task, wherein the machine learning task comprises a classification task or a regression task.

7. A computer-implemented method comprising:

receiving input data comprising data representing a user selected item and multiple values corresponding to respective input features;

searching a list containing data items representing respective paths in a trained quantum decision tree, wherein each path in the quantum decision tree is associated with one or more likelihoods that a target feature takes each of the multiple values, to identify one or more data items in the list that represents a path that matches the input data,

wherein searching the list comprises applying a Grover algorithm on a quantum computer using a generalized n-controlled-Pauli-Z (CNZ) quantum logic gate to search the list, wherein implementing the Grover algorithm on a quantum computer using a generalized CNZ quantum logic gate comprises:

initializing each of multiple qubits in a quantum register in a zero state;

after initializing each of the multiple qubits in the quantum register in the zero state, performing an oracle step on a subset of the multiple qubits;

after performing the oracle step on the subset of the multiple qubits, performing a Hadamard gate on each qubit in the quantum register;

after performing the Hadamard gate on each qubit in the quantum register, performing a Pauli-X gate on each qubit in the quantum register;

after performing a Pauli-X gate on each qubit in the quantum register, performing the generalized CNZ quantum logic gate;

after performing the generalized CNZ quantum logic gate, performing a Pauli-X gate on each qubit in the quantum register; and

after performing the Pauli-X gate on each qubit in the quantum register, performing a Hadamard gate on each qubit in the quantum register;

determining a predicted value of the target feature using one or more likelihoods associated with paths represented by the identified one or more data items; and

providing the one or more data items in the list as new items to recommend to the user.

8. The method of claim 7 , wherein using the generalized CNZ quantum logic gate comprises, for a quantum register comprising two qubits:

performing a controlled-X gate on a second qubit, wherein a first qubit acts as a control for the controlled-X gate;

performing a phase rotation with an angle of −π/16 on the second qubit;

performing a controlled-X gate on the second qubit, wherein the first qubit acts as a control for the controlled-X gate; and

performing a phase rotation with an angle of π/16 on the second qubit.

9. The method of claim 8 , wherein using the generalized CNZ quantum logic gate comprises, for a quantum register comprising three or more qubits, repeatedly performing, a number of times equal to twice the number of qubits i minus 1:

performing a controlled-X gate on an i-th qubit, wherein an i−1-th qubit acts as a control for the controlled-X gate;

performing a phase rotation with an angle of −π/16 on the i-th qubit;

performing a controlled-X gate on the i-th qubit, wherein the i−1-th qubit acts as a control for the controlled-X gate; and

performing a phase rotation with an angle of π/16 on the i-th qubit.

10. The method of claim 7 , further comprising, before performing the generalized CNZ quantum logic gate, performing a phase rotation with an angle of π/16 on a first qubit in the quantum register.

11. The method of claim 7 , wherein the trained quantum decision tree is constructed to perform a machine learning task, the machine learning task comprising a multiclass classification task, and wherein determining a predicted value of the target feature using one or more likelihoods associated with paths represented by the identified one or more data items comprises selecting a predicted value of the target feature that corresponds to a largest likelihood.

12. The method of claim 7 , wherein the trained quantum decision tree is constructed to perform a machine learning task, the machine learning task comprising a regression task, and wherein determining a predicted value of the target feature using one or more likelihoods associated with paths represented by the identified one or more data items comprises selecting the predicted value of the target feature as equal to a likelihood associated with the path that matches the input data.

13. The method of claim 7 , wherein the input data is incomplete.

14. A system comprising:

a classical processor;

a quantum computing device in data communication with the classical processor;

wherein the classical processor and quantum computing device are configured to perform operations comprising:

training a quantum decision tree, comprising:

obtaining training data comprising data sets, wherein each data set comprises a value that corresponds to a target feature and multiple values that each correspond to a respective input feature of a set of input features;

assigning an input feature from the set of input features to a root node of the quantum decision tree, comprising:

for each input feature in the set of input features: calculating an information gain value for the input feature using values that correspond to the input feature; and

identifying, from the calculated information gain values, a maximal information gain value and assigning the input feature corresponding to the maximal information gain value to the root node;

creating a path from the root node, wherein creating the path comprises:

iteratively:

calculating a cumulative information gain value for unassigned input features based on i) multiple information gain values for respective input features that have been assigned to previous nodes on the path, and ii) probabilities that the unassigned input features are assigned to a current leaf node given the assigned input features to previous nodes on the path;

performing Monte Carlo simulations to generate respective modified cumulative information gain values; and

identifying, from the calculated cumulative information gain values, a maximal cumulative information gain value for the unassigned input features and assigning an unassigned input feature corresponding to the maximal cumulative information gain value to the current leaf node in the path creating a new leaf node, comprising identifying, from the modified cumulative information gain values, a maximal modified cumulative information gain value and assigning the input feature corresponding to the maximal modified cumulative information gain value to the current leaf node in the path;

receiving input data comprising data representing a user selected item and multiple values that each correspond to a respective input feature of the set of input features;

searching the trained quantum decision tree using a Grover algorithm to identify a path that matches the input data, wherein the path that matches the input data comprises one or more data items; and

providing the one or more data items as new items to recommend to the user.

15. A system comprising:

a classical processor;

a quantum computing device in data communication with the classical processor;

wherein the classical processor and quantum computing device are configured to perform operations comprising:

receiving input data comprising data representing a user selected item and multiple values corresponding to respective input features;

searching a list containing data items representing respective paths in a trained quantum decision tree, wherein each path in the quantum decision tree is associated with one or more likelihoods that a target feature takes each of the multiple values, to identify one or more data items in the list that represents a path that matches the input data, wherein searching the list comprises applying a Grover algorithm on the quantum computing device using a generalized n-controlled-Pauli-Z (CNZ) quantum logic gate to search the list, wherein implementing the Grover algorithm on a quantum computer using a generalized CNZ quantum logic gate comprises:

initializing each of multiple qubits in a quantum register in a zero state;

after initializing each of the multiple qubits in the quantum register in the zero state, performing an oracle step on a subset of the multiple qubits;

after performing the oracle step on the subset of the multiple qubits, performing a Hadamard gate on each qubit in the quantum register;

after performing the Hadamard gate on each qubit in the quantum register, performing a Pauli-X gate on each qubit in the quantum register;

after performing a Pauli-X gate on each qubit in the quantum register, performing the generalized CNZ quantum logic gate;

after performing the generalized CNZ quantum logic gate, performing a Pauli-X gate on each qubit in the quantum register; and

after performing the Pauli-X gate on each qubit in the quantum register, performing a Hadamard gate on each qubit in the quantum register;

determining a predicted value of the target feature using one or more likelihoods associated with paths represented by the identified one or more data items; and

providing the one or more data items in the list as new items to recommend to the user.

16. The system of claim 15 , wherein using the generalized CNZ quantum logic gate comprises, for a quantum register comprising two qubits:

performing a controlled-X gate on a second qubit, wherein a first qubit acts as a control for the controlled-X gate;

performing a phase rotation with an angle of −π/16 on the second qubit;

performing a controlled-X gate on the second qubit, wherein the first qubit acts as a control for the controlled-X gate; and

performing a phase rotation with an angle of π/16 on the second qubit.

17. The system of claim 16 , wherein using the generalized CNZ quantum logic gate comprises, for a quantum register comprising three or more qubits, repeatedly performing, a number of times equal to twice the number of qubits i minus 1:

performing a controlled-X gate on an i-th qubit, wherein an i−1-th qubit acts as a control for the controlled-X gate;

performing a phase rotation with an angle of −π/16 on the i-th qubit;

performing a controlled-X gate on the i-th qubit, wherein the i−1-th qubit acts as a control for the controlled-X gate; and

performing a phase rotation with an angle of π/16 on the i-th qubit.