[Story] Investigate Manifold Convex Class Model and Convex Optimization

[gcattan]

The work is twofold:

1. Investigate [1] which is an approach to transform SPD classes in a convex model.
2. Investigate [2], which a quantum approach to convex optimization.

[1] K. Zhao, A. Wiliem, S. Chen, and B. C. Lovell, ‘Convex Class Model on Symmetric
Positive Definite Manifolds’, ArXiv180605343 Cs, May 2019, Accessed: Sep. 24, 2021.
[Online]. Available: http://arxiv.org/abs/1806.05343

[2] J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf, ‘Convex optimization using
quantum oracles’, Quantum, vol. 4, p. 220, Jan. 2020, doi: 10.22331/q-2020-01-13-220

Quantum convex optimization example:
https://qiskit.org/documentation/tutorials/optimization/5_admm_optimizer.html
https://medium.com/qiskit/towards-quantum-advantage-for-optimization-with-qiskit-9a564339ef26

cvxpy examples:
https://www.cvxpy.org/examples/basic/sdp.html
https://math.stackexchange.com/questions/4109504/solving-the-multi-dimensional-scaling-problem-in-cvxpy

[qbarthelemy]

[1] looks like the MDM published by Barachant in 2012.

[gcattan]

Yes, looks like you also got a special thank :)

[gcattan]

[1] looks like the MDM published by Barachant in 2012.

Yes, you are right. One practical impediment I see is to transform the actual implementation using constraint programming, as at first sight, Qiskit is taking a convex model as an input for quantum optimization.

One aspect which seems not discussed in the above paper is also the determination of the class prototypes.
In pyRiemann some of the mean_ algorithms are iterative. May be worth trying to express them using constraint programming and investigate if there are some outcomes when running on a quantum simulator. But these are only intuitive suggestions opened to discussion.

[gcattan]

Technical update:

• Seems that cvxpy cannot be used directly. It is required to use docplex or qiskit's QuadraticProgram.
  Here an example of implementation:
  https://medium.com/qiskit/towards-quantum-advantage-for-optimization-with-qiskit-9a564339ef26

• The version of docplex compatible with qiskit aqua is 2.19.202
  New version of Docplex breaks QuadraticProgram qiskit-community/qiskit-optimization#21

[gcattan]

Here is a template on how could look like an implementation of mean_ (MDM still in the box) using constraint programming (not tested, probably need some improvement):

def fro_mean_convex(covmats, sample_weight=None):
    n_trials, n_channels, _ = covmats.shape
    channels=range(n_channels)
    trials=range(n_trials)

    prob = Model()

    ContinuousVarType.one_letter_symbol = lambda _: 'C'
    X_mean = prob.continuous_var_matrix(keys1=channels, keys2=channels,
                                        name='fro_mean', lb=-prob.infinity) 

    def _fro_dist(A, B):
        return prob.sum_squares(A[r, c] - B[r,c] for r in channels for c in channels)

    objectives = prob.sum(_fro_dist(covmats[i], X_mean) for i in trials)
    
    prob.set_objective("min", objectives)

    qp = QuadraticProgram()
    qp.from_docplex(prob)
    
    result = CobylaOptimizer().solve(qp)

    return np.reshape(result.x, (n_channels, n_channels))

The problem is that Qiskit only supports problems with unconstrained binary variables (see ADMM documentation):

A naive approach to work around this problem could be to round covariance matrices to some precision and convert the resulting integers to binary.

Here is the official response from Qiskit when I asked:

If you want to deal with continuous variables quantumly, you need to encode it with qubits. Because the number of qubits is very limited, you need to encode it by yourself, for example, in a form coeff * integer_var.

However, it might be possible to directly optimize problems with continuous variables on quantum (CV QAOA algorithm).

I contacted the first author from this paper who pointed me to this resource:

https://docs.google.com/presentation/d/1_OiNA9QG9vzJFBwPAxuPzjm6DDXKRRw2LGwS_XI6OGM/edit#slide=id.p1

[sylvchev]

Super interesting! Do you think it is possible to adapt the Guillaume Verdon's approach? It is not clear for me how we could do that.

[gcattan]

I am not sure either how to start. Probably need to look at the QAOA implementation of Qiskit again, before doing a POC for CV-QAOA. But Guillaume Verdon seems confident we can implement it on Qiskit, and I understood he is working on implementation with TensorFlow quantum.
That said I am also contacting the author of the integer-to-binary converter to confirm the naive approach.

[gcattan]

#26
#27
#28
#29
#30
#32

[gcattan]

Closing this task as completed.
The implementation is covered by the NCH and NaiveQAOAOptimizer/QAOACVOptimizer in the docplex module.