aromanro / qcsim

Quantum computing simulator

Welcome to the Computational Physics Blog Repositories!

qcsim's Issues

Add a N qubits controlled gate using ancilla qubits and cnot and ccnot gates

A not necessarily optimal one is easy to implement and a good example.
The allowed controlled gates should be only the 1 & 2 qubits.

Add something on VQE

Description on wikipedia: https://en.wikipedia.org/wiki/Variational_quantum_eigensolver

It's something I plan to do, in a similar way as described here: https://arxiv.org/abs/2008.10647
Probably it will take a while since I'm busy currently with some other stuff.

Use cuda to improve speed for registers with many qubits

The project is built with omp turned on and when it used the big matrices obtained by tensor product it benefited from it. Currently those big matrices are avoided, the tensor product matrix and its product with the state vector are optimized by taking advantage of the structure of the matrix.
The code for applying a quantum gate now does a single loop over the basis states. This could be parallelized using open mp, for a big register. I tried a quick hack but unfortunately for small registers there is a noticeable slowing down due of the omp overhead. I might try to avoid it in the future, for now the omp pragmas stay commented out there.

Nevertheless, for big registers cuda could be used (I would favor something that works on some other hardware, to not be tied to nvidia, such open cl or even compute shaders, but cuda is more performant and when performance is needed...), that could improve the speed quite a bit.

Add implementation with sparse matrices

As the matrices increase exponentially with the number of qubits an implementation using sparse matrices would be beneficial.
Unfortunately, for obvious reasons one cannot access matrix elements as easily as in normal matrices type. The Eigen implementation is quite different, so for now I postpone this.

Use AVX2 to speed up?

It might be worth investigate it.
Currently it benefits from AVX2 because eigen has avx2 optimizations (so on my computer execution time for tests/examples drops from > 50 sec to aprox 35 sec with avx2 turned on), but maybe some stuff from QubitRegisterCalculator could also be improved.

qiksit aer has avx2 optimizations, so it might be possible.

Compilation errors

I tried running the example code found in the documentation:

#include <iostream>

#include "QCSim/QubitRegister.h"

int main()
{
    QC::QubitRegister reg(3);
    QC::Gates::PauliXGate x;
    reg.ApplyGate(x, 0);
    unsigned int m = reg.Measure();

    std::cout << "Result should be 1, it's: " << m << std::endl;

    return 0;
}

And I keep getting a bunch of similar errors:

In file included from ./QCSim/QubitRegister.h:3:
In file included from ./QCSim/QubitRegisterCalculator.h:23:
./QCSim/QuantumGate.h:177:20: error: missing 'typename' prior to dependent type name 'BaseClass::BaseClass'
                        using OpClass = BaseClass::BaseClass;
                                        ^~~~~~~~~~~~~~~~~~~~
                                        typename 
./QCSim/QuantumGate.h:198:20: error: missing 'typename' prior to dependent type name 'BaseClass::BaseClass'
                        using OpClass = BaseClass::BaseClass;
                                        ^~~~~~~~~~~~~~~~~~~~
                                        typename 
./QCSim/QuantumGate.h:217:20: error: missing 'typename' prior to dependent type name 'BaseClass::BaseClass'
                        using OpClass = BaseClass::BaseClass;
                                        ^~~~~~~~~~~~~~~~~~~~
                                        typename 

Could you please provide an example on how to compile the example code and what the requirements are regarding the C++ standard and compilation options?

Separate out the phase estimation from Shor's algorithm

Maybe also order finding based on phase estimation.

The separation should be useful since phase estimation may be used for other algorithms as well.

Improve the simulation for 'subalgorithms'

There are situations when a 'subalgorithm' is executed repeatedly (an example: Suzuki-Trotter expansion in quantum simulations).
In such case obtaining the operators for gates and multiplying them with the register is very slow.

Instead, the whole operator matrix for a step could be obtained once then applied multiple times on the register.

Add more ways to test the quantum simulation of the evolution of a 1D Gaussian packet in time

Currently it's tested using FFT, that puts the results very close to the QFT-using ones (fidelity = 1).
I have implemented several other ways of simulation to be used as a comparison, one of them also could be used for tests.

Replace some functions/oracles (implemented with big matrices) with some built out of gates

Improve operator matrices for quantum gates

Currently the operator matrices that act on the register are generated out of the gate matrices each time. This might be improved, although they can be quite big.

Optimization for one/two/three qubit(s) gates

Instead of generating big matrices (tensor products) out of the gates matrices, to multiply the register contents, there are some simple optimizations that can be done, for example for one qubit gates the register can be updated in O(N) time with a sum of two products only.

Add 'uncomputation'

Can be useful for various quantum algorithms.
Just add a pair ComputeStart/ComputeEnd (record all gates applied in between, including those supplied as matrices) and Uncompute to the quantum register (and forwarded calls to the register into the quantum algorithm class).
https://en.wikipedia.org/wiki/Uncomputation

Add VQE

Variational Quantum Eigensolver.

Add a 'subalgorithm' that decomposes a controlled-controlled three-qubits gate in two qubits gates

There are cases when one wants to avoid using three-qubit gates, for example for distributed quantum computing situations or even for testing for bugs in the three qubits implementations (I actually had such bug recently, in the optimization code).
It can be done using Sleator-Weinfurter (info here: https://quantumcomputing.stackexchange.com/questions/3943/how-do-you-implement-the-toffoli-gate-using-only-single-qubit-and-cnot-gates), using 5 two-qubit gates, two cnots, three controlled-V and one controlled-V^dag, where V*V^dag = U, U being from the original controller-controlled-U gate.

Execute improvement - avoid repeating the execution of the same circuit for many measurements

Many algorithms are probabilistic and need repeating the measurement many times, which requires reinitialization of the register and executing again the algorithm... but there is a shortcut in simulation (unlike the real case, where you cannot copy a quantum state: No Cloning Theorem): the register state can be saved and then after the measurement (with the collapse, of course) it can be initialized back to the saved value.

This would allow avoiding repeating the algorithm many times, doing instead only repeated measurements.

In fact, the register already has a RepeatedMeasure implementation, this enhancement would just need a RepeatedExecute, similar with the Execute function, but with a RepeatedMeasure at the end instead of the single Measure.

Not a big deal to implement, but I'll postpone it for a while, there are more interesting things to do :)

Add something on optimization

At least something basic on QAOA (Quantum Approximate Optimization Algorithm)

Add something related with quantum pseudo-telepathy

Since I started a section on 'quantum games', a 'game' on this topic would be a nice addition (for example a GHZ game or the magic square game).

Add stochastic gradient descent

Looks like the project might end up with some other things that might benefit from stochastic gradient descent methods, instead of using the regular gradient descent.

I already have some implemented in the machine learning project https://github.com/aromanro/MachineLearning and in the dft notebook in https://github.com/aromanro/PythonCompphys, although the former is machine learning - specific and the later is python, so here I'll have to implement them again. Not a big deal, though, I might do that sometime.

Allow p > 2 for the gradient descent for the Ising Model (QAOA)

Currently only p=1 and p=2 are allowed, instead of having beta1, beta2, gamma1, gamma2 parameters, vectors could pe used to allow bigger values of p.
What's there is good enough as an example, but it could be enhanced sometime.

Add some example(s) on adiabatic quantum computation

An article on it: Quantum Computation by Adiabatic Evolution https://arxiv.org/abs/quant-ph/0001106