Quantum recommendation system

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.

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.

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.