Methods, systems, and apparatus for improving recommendation systems. In one aspect, a method includes obtaining training data including data sets, wherein each data set includes a value that corresponds to the 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 based on calculated information gain values for the input features; creating a path from the root node by iteratively: calculating a cumulative information gain value for unassigned input features; identifying a maximal cumulative information gain value for the unassigned input features and assigning the unassigned input feature corresponding to the maximal cumulative information gain value to a current leaf node in the path creating a new leaf node.