Variational Quantum Linear Solver

Theory

The Variational Quantum Linear Solver (VQLS) is a a hybrid quantum-classical technique designed to address the Quantum Linear Systems Problem (QLSP). It aims to find linear system solutions using quantum computing techniques.
The classical problem is formulated as follows:
Given a matrix A and vector b, find x such that
A.x=b
The corresponding quantum algorithm can be summarized as follows:
Given:
◼
  • Problem vector: A quantum state
    |b〉
    such that
    |b〉=U|0〉
    • ◼
  • Problem matrix:
    n
    2
    ×
    n
    2
    dimensional matrix
    A
    such that
    A=
    L-1
    ∑
    0
    c
    l
    A
    l
    , where
    c
    l
    ϵ
    and
    A
    l
    are unitary gates
    • We want to prepare:
    ◼
  • A quantum state
    |x〉
    such that
    |ψ〉=A|x〉
    and
    |ψ〉
    
    ψ
    
    ψ
    
    ->|b〉

    • Precedents

    We have this relevant first implementation of a variational quantum circuit that solves linear systems by Bravo-Prieto, you can check the paper in the following link.

    Bravo-Prieto VQLS

    ◼
  • First implementation of a variational quantum circuit for solving linear systems
    • https://quantum-journal.org/papers/q-2023-11-22-1188/pdf
    ◼
  • Requires multiple circuits (
    Gates
    A
    i
    and
    CZ
    j
    permute
    :
    • ◼
  • In general the algorithm performs the calculation in a real quantum computer by obtaining multiple expected values from multiple circuit variations.
    • ◼
  • he diagram displayed is an example from one of those circuits, Gate A and the Control Z gate permute between different qubits to obtain the different expected values:
    • Out[]=
    ◼
  • He also used a local cost function in order to avoid getting stuck in local minimum values:
    • C
    L
    =
    1
    2
    -
    1
    2n
    n-1
    ∑
    j=0
    ∑
    l,l'
    c
    l
    *
    c
    l'
    μ
    l,l',j
    ∑
    l,l'
    c
    l
    *
    c
    l'
    μ
    l,l',-1
    where
    μ
    l,l',j
    =〈0|
    †
    V
    †
    A
    l'
    U
    Z
    J
    †
    U
    A
    l
    V|0〉
    ,
    Z
    -1
    ->
    and
    C
    G
    ->0<->
    C
    L
    ->0
    .
    You can check more about this implementation on my community post: https://community.wolfram.com/groups/-/m/t/3180154

    Multiplexer-based VQLS

    We propose a Multiplexer–Based Variational Quantum Linear Solver (MB-VQLS). The primary distinctions between MB–VQLS and a conventional VQLS lie in two key aspects:
    ◼
  • The controlled implementation of the matrix
    A
    through a multiplexer
    • ◼
  • Quantum fidelity cost function:
    • f(ω)=1-
    b
    
    ψ(ω)
    
    2
    ◼
  • The solution to the linear system is encoded directly in the amplitudes of the resultant quantum state.
    • Further steps will show that we can avoid some
    |b〉
    and
    A
    restrictions using their normalization terms. This would help us find solutions for any system.

    A.x
    Operation Circuit Representation

    Considering an
    n
    ×
    n
    A matrix and an
    n
    -element vector
    x
    , we look to compute the operation
    A.x
    with a quantum circuit using
    A
    as a controlled operation.
    To start, let’s define a complex vector x using RandomComplex, and a random real matrix A called “a”:
    In[]:=
    x=RandomComplex[{-1-1*I,+1+1*I},4]
    Out[]=
    {-0.126112-0.770322,0.302431-0.0695352,0.0386691-0.00105955,0.0950529-0.0692226}
    We will begin the implementation by encoding the matrix A into the quantum circuit:
    In[]:=
    a=RandomReal[{-1,1},{4,4}];​​a//MatrixForm
    Out[]//MatrixForm=
    0.25529
    0.831537
    0.774413
    0.967247
    0.345805
    0.29044
    0.424374
    -0.428653
    -0.406224
    0.260866
    -0.687513
    0.829075
    -0.901911
    0.438124
    -0.841926
    -0.108815
    We proceed to generate a quantum operator
    A
    and decompose it in Pauli matrices such that
    A=
    c
    j
    A
    j
    :
    In[]:=
    A=QuantumOperator[a];
    In[]:=
    pauliDecompose=A["PauliDecompose"]
    Out[]=
    XX0.187644+0.,XY0.+0.426412,XZ0.0896794+0.,XI0.0944149+0.,YX0.+0.508167,YY0.154976+0.,YZ0.+0.511854,YI0.+0.078465,ZX0.297548+0.,ZY0.-0.296318,ZZ0.135887+0.,ZI0.335515+0.,IX0.291123+0.,IY0.+0.539183,IZ-0.153462+0.,II-0.0626495+0.
    In order to implement the controlled
    A
    gates, we will turn the Pauli matrices as targets into a multiplexer, and the controlled qubits would be evaluated by a
    
    c
    
    state:
    In[]:=
    multiplexer=QuantumCircuitOperator["Multiplexer"@@Keys[pauliDecompose]];
    In[]:=
    multiplexer["Diagram"]
    Out[]=
    In[]:=
    ancillary=QuantumState[Sqrt@Values[pauliDecompose],"Label"->"
    c
    "];
    In[]:=
    QuantumCircuitOperator[​​ancillary,​​multiplexer,​​
    †
    ancillary["Conjugate"]
    ​​]["Diagram"]
    Out[]=
    Finally, we would let our vector
    x
    be evaluated by the multiplexer in our circuit:
    In[]:=
    productCircuit=QuantumCircuitOperator[​​ancillary,​​QuantumState[x,"Label"->"x"]->{5,6},​​multiplexer,​​
    †
    ancillary["Conjugate"]
    ​​];
    In[]:=
    productCircuit["Diagram",ImageSize->Full]
    Out[]=
    Evaluate our circuit and check the amplitudes of the resultant state:
    In[]:=
    productCircuit[]
    Out[]=
    QuantumState
    Pure state
    Qudits: 2
    Type: Vector
    Dimension: 4
    
    The result corresponds to the equivalent classical operation:

    Quantum Linear Solver Implementation

    Now that we learned how to compute the product of a matrix and vector using a quantum circuit, we have a better understanding of how to implement our new variational quantum linear solver.

    Initial problem setup

    As we previously discussed, we need to save the normalization terms, since we will be working with the normalized matrix and vector:

    Multiplexer implementation

    Next, implement the multiplexer:
    We obtain the first section of the variational circuit for the VQLS:

    General symbolic ansatz

    Finally, we implement the circuit and the correspondent state:
    Wolfram Quantum Framework quantum states (and measurements) keep the parameters defined in previously used circuits, so it would be optimum to work with the resultant state:

    Optimization

    In other words, this cost function does not ensure that the amplitudes of both states are identical, but rather that they are proportional by a global phase:
    Implement the cost functions previously defined, rememer to use the normalized vector b:
    Now, let’s optimize the cost function using FindMinimum, with our initial guess as the starting point:
    As we can see, FindMinimum is having some difficulty finding the minimal value, so we might switch to NMinimize, which will return a value for the cost function that is very close to zero:
    As we can notice, the values are quite close! However, as mentioned earlier, while the probability distributions match, the amplitudes do not necessarily align:
    We can verify our result:

    Optimization using quantum natural gradient descent

    As explained in a previous example, we can optimize using QuantumNaturalGradientDescent, calculating their correspondent Fubini–Study metric tensor.
    The result is quite remarkable: the Quantum Natural Gradient Descent outperforms regular gradient descent and reaches the minimum value in only two steps!
    We can verify that the minimization approaches to 0:
    As you may have noticed, the probabilities match, but with less precision in this case. However, the amplitudes are completely different, and they even have different signs!
    Now, during the process of obtaining the global phase, we observe that the values are not exactly the same. In this case, when we use the mean value of the global phase, we can check that the deviation is small enough for the desired precision.
    We can verify our result approximation:
    After repeating all the same steps from the previous example, we get a final result that is close to the true result but with slightly less precision. What’s remarkable about this solution is that we achieved it in only two steps! Of course, the results depend heavily on the learning rate eta, so it’s important to fine-tune it to ensure that the optimization is done efficiently.