Strong simulation of multi-Pauli measurements using minimal stabilizer state decompositions
-------------------------------------------------------------------------------------------

See the draft at [https://arxiv.org/abs/2012.11739] for an introduction and description of this code.

PREREQUISITES:

You will need the Lapacke library to run strongsim[1-12]_rellerr.c (in particular, the lapacke.h header).
For instance, in Debian, you can obtain this by running:
$ sudo apt install liblapacke-dev

BUILD:

1. We start with the code that scales quadratically with stabilizer rank because it calculates expectation values to zero relative error. Build code for stabilizer rank tensor multiple you'd like to use. Here we choose k=6.
$ cp strongsim6.c strongsim.c
$ make strongsim

2. Now we build the code that scales linearly with stabilizer rank because it calculates expectation values to non-zero relative error. Build code for stabilizer rank tensor multiple you'd like to use. Here we choose k=6.
$ cp strongsim6_relerr.c strongsim_relerr.c
$ make strongsim_relerr

3. This produces libraries (*.so) of core functions like SHRINK, INNERPRODUCT, EXTEND, etc. since you might want to use them in other code. This means we need to put them somewhere the linker can find them. Follow 3a) for a temporary and easy method that will only be valid for the current shell session and follow 3b) for a persistent method that requires root access.
3a) Update LD_LIBRARY_PATH to see the library:
$ export LD_LIBRARY_PATH=$PWD:$LD_LIBRARY_PATH
or
3b) If you have root privileges put the *so library /usr/local/lib or whatever library directory in your path. Then, use ldconfig to write the path in the config file:
$ sudo cp ./*so /usr/local/lib
$ sudo echo "/usr/local/lib" >> /etc/ld.so.conf
$ sudo ldconfig

4. Build code for generating random commuting Pauli inputs (necessary for the strongsim[1-12]_relerr.c code since it requires a Hermitian observable to get away with using the square root number of stabilizer states).
$ make randominputcommutingHermitianPauli2

5. Build code for generating random (non-commuting) Pauli inputs (good enough for the strongsim[1-12].c code).
$ make randominputPauli

6. Build Hilbert vector space code to check our results.
$ make multipauli


TEST CODE:
1. Run test diagonositic for strongsim.c (zero relative error).
$ bash ./test.bash

2. Run test diagonositic for strongsim_relerr.c (non-zero relative error).
$ bash ./test2.bash



Details of source code files:

strongsim[1-12]_relerror.c takes one argument of the number of stabilizer states to sample and then takes stdin arguments for the number of qubits, t-gate magic states and then the Paulis

strongsim[1-12]_relerror.c scale linearly with the stabilizer rank and calculate up to finite relative error while strongsim[1-12].c scale quadratically with the stabilizer rank and calculate up to zero relative error.

strongsim*c need Pauli measurement inputs (with the associated phases) which can be randomly generated with randominputPauli.c and the output from strongsim*c can be verified with multipauli.c

strongsim[1-12]_relerror.c need commuting Pauli measurement inputs (with the associated phasese) which can be randomly generated with randominputcommutingHermitianPauli2.c and can be verified with multipauli.c

randominputcommutingHermitianPauli.c uses a brute-force random sampling of the commuting Paulis whereas *2.c uses random Clifford operations on initially separable Paulis to generate the commuting Paulis. *2.c is the only practically viable method for more than 30 Paulis on a desktop computer.

NOTE: current strongsim*c only support the same number of T gates as number of qubits!

Pd.txt is a tabulated list of P(d) values for strongsim[1-12]_relerror.c.