Implement the Variational Quantum Linear Solver (VQLS)

[nelimee]

The VQLS algorithm Variational Quantum Linear Solver aims at solving linear systems of equations using a variational approach.

I think adding VQLS to Qiskit would be beneficial as it would enrich the library with another variational algorithm. Moreover, linear systems of equations are a fundamental problem in a lot of areas and having such an algorithm implemented in Qiskit might attract some new users interested in this kind of problems (just like HHL).

What is the expected behavior?

Being able to import and use the VQLS algorithm into Qiskit.

from qiskit.aqua.algorithms.linear_solvers import VQLS
from qiskit.circuit.library import EfficientSU2
from qiskit.aqua.components.optimizers import COBYLA

from qiskit import BasicAer

qubit_number = 10

# Inspired from VQE signature found in 
# https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.VQE.html#qiskit.aqua.algorithms.VQE
vqls_instance = VQLS(
    decomposition={
        "circuits": get_decomposition(qubit_number),    # User-defined
        "coefficients": get_coefficients(qubit_number), # User-defined
    }, 
    var_form=EfficientSU2(qubit_number, reps=1), 
    optimizer=COBYLA()
)

result = vqls_instance.run(BasicAer.get_backend("statevector_simulator"))
print(result)

Implementation steps

Implementing the VQLS algorithm in Qiskit boils down to implementing at least one of the two cost functions introduced by Variational Quantum Linear Solver:

• The global cost function
• The local cost function

Both cost functions requires to estimate "expectation values" of unitary matrices, i.e. <0| U |0> with U being a unitary matrix implemented as a quantum circuit. This is done in Variational Quantum Linear Solver with the Hadamard Test. In addition, the authors of Variational Quantum Linear Solver also introduce the Hadamard-Overlap test, a specialised version of the Hadamard Test that solves a restricted problem (only works for some specific U, not for any U) by generating a shallower circuit, at the expense of using more qubits.

Implementing the Hadamard Test algorithm is required if we want to keep VQLS as generic as possible. Without an Hadamard Test implementation, the VQLS implementation would be limited to corner cases explained in Methodology for replacing indirect measurements with direct measurements. Implementing the Hadamard-Overlap test is optional, but allows to improve the shallowness of some of the generated quantum circuits, which is of particular interest for NISQ devices. Implementing the global cost function may not be a priority, as Barren plateaus in quantum neural network training landscapes showed that it will inevitably suffer from vanishing gradients.

So we are left with a minimal implementation:

• Hadamard Test
• VQLS local cost function

With possible improvements once

• Hadamard-Overlap Test

is implemented.

Side note

I wanted to start the discussion about implementing VQLS before implementing anything in Qiskit and wait for feedback. As such, I did not start to write any code for VQLS on Qiskit yet and i will not start until I have positive feedback from maintainers/regular contributors. But even if I did not start with Qiskit, I already have a working VQLS implementation written with another quantum computing framework. The Qiskit implementation might benefit from this experience.

[pbark]

Hi @nelimee , we are happy to see the contribution of Variational Quantum Linear Solver in qiskit aqua. We are currently working on refactoring and adding in the linear solvers so this would be a great addition. I think that a design proposal and a more concrete discussion would be of benefit here. I know that @anedumla and @stefan-woerner are working on this so you can have a follow up discussion on this. Thanks for the interest in contributing to qiskit aqua!

[anedumla]

Hi @nelimee , the HHL refactoring is taking place in my github within this new package: https://github.com/anedumla/qiskit-aqua/tree/hhlrefactoring/qiskit/aqua/algorithms/linear_solvers_new . What is clear is that the abstract class for all solvers will be LinearSolver and all solvers will contain a .solve() method, however we are still drafting everything else (including what should go inside LinearSolverResult). We would indeed be very happy to add your contribution to the package but it is up to you whether to wait until these two classes have been defined or still add your code and then refactor it in the future.

[nelimee]

Hi @pbark and @anedumla, Thanks for the answer. I will first have a look at the hhlrefactoring branch of @anedumla and familiarise myself with the package. I will come back to you on this issue during the week and try to give you an interface V1 for the VQLS so that we can iterate on this. @anedumla if you feel the need, I would also be happy to help with the refactoring. I am not sure this issue is the best place to talk about it, but feel free to ping me whenever and wherever you want about the refactoring. If you agree, I might also be able to give you a V1 interface for the LinearSolver and LinearSolverResult in a few days. Tell me if you are interested.

[anedumla]

@nelimee I would be happy to take the discussion offline but cannot find how to contact you, you can ping me on Slack (Almudena Carrera Vazquez).

[woodsp-ibm]

@nelimee Is this something that you are still interested in doing? If its still being looked at I will transfer this issue over to the qiskit-terra repository where @anedumla is working on including the refactored linear solver code.

[nelimee]

@woodsp-ibm Yes it is still something I am interested doing! I tried to follow a little bit @anedumla work but got carried away by other things since. You can transfer the issue if you think this is the right thing to do.

[woodsp-ibm]

For HHL/linear solvers rework see #5698

[nelimee]

Not sure about the procedure here, so before doing anything I prefer to ask. In your opinion, should I wait for #5698 to be merged and then fork and start working on VQLS implementation, or should I directly fork anedumla/hhlrefactoring and then start developing from there?

[stefan-woerner]

@nelimee Thanks for reaching out! Best wait for #5698 being merged. We are almost there so you can already look into it and let us know in case you have any questions.

[Mostafa-Atallah2020]

Hi, @nelimee are you still working on this ??

[nelimee]

I am not working on this anymore, and I do not have any code to share so you can consider that nothing has been done.

[Mostafa-Atallah2020]

Hi @stefan-woerner, @anedumla , @pbark I am asking to work on this issue.

[anedumla]

Hi @Mostafa-Atallah2020, recently we decided to deprecate the linear systems package from Qiskit for the time being. If somebody wants to implement VQLS it should also be separately from Qiskit, so I think we should close this issue.

[woodsp-ibm]

As Almudena mentioned the linear solvers package here was deprecated last release and will soon be removed. The code that was in Terra is now maintained elsewhere https://github.com/anedumla/quantum_linear_solvers As mentioned if you want to proceed I think its best to have this separate from Qiskit Terra at present. Now if you are interested I think its possible, if you create such an algorithm, to have it as part of the Qiskit Ecosystem, see https://qiskit.org/ecosystem/ Given the decision to deprecate and remove Iinear solvers I will close this issue.