10          Discrete optimization in Quantum unsupervised learning

This topic is about unsupervised learning on quantum computer without entanglement.

10.    

10.1   Label availability for unsupervised learning

One difference between supervised and unsupervised learning is that in supervised learning you always have labels, while in unsupervised learning, you don’t have labels.

10.2   Gram Matrix

Computing Gram matrix has O(N2) computational complexity.

10.3   Max cut

Max cut takes exponentially many steps to find in the number of graph nodes.

10.4   Assignment 10_Discrete_Optimization_and_Unsupervised_Learning

In the past I thought for Maxcut problem, one node of the graph requires one qubit (say a dozen of Maxcut nodes needs an IBM 14-qubit Melbourne machine).  Obviously, that can be improved.  See https://en.wikipedia.org/wiki/Exploratory_data_analysis

The following code is so important since (1) this is what CDL bootcamp application requires to resolve Maxcut problem for a dozen graph nodes (change p=1 to p=12, but that will take a while to get the results because we will be in queue to use IBM 14-qubit Melbourne quantum computer), (2) the threshold is an important idea in analyzing data cluster for “best match” scenario (say, to separate the data into two groups by “threshold hyperplane” as in the kernel methods).  Applications include Netflix movie-goer analysis of favoriting romance or action movie, and best way to match software apps and resources in cloud center.

when change p=1 to p=12, the output is different:

energy: -3.9999998441118567

maxcut objective: -7.999999844111857

solution: [0. 0. 1. 1.]

solution objective: 8.0