Reducing the Number of Qubits in Quantum Information Set Decoding

This code is licensed under the GNU Affero General Public License (see LICENSE.md).
The sub-folder compressed_prange/quantum_util is licensed under the MIT license.

This code can be used to run, test and benchmark various quantum circuits
defined throughout the paper. We use the Qiskit framework,
Python3 and Sympy.

The quantum circuits that we define are subclasses of Qiskit's
QuantumCircuit class.

We only tested our circuits on small instances. The gate counts of larger
instances are obtained via detailed formulas, which are deduced in a bottom-up
way by adding the costs of the various sub-circuits. These costs are those
returned by the class methods .all_counts() (returning a triple: depth,
number of qubits, gate counts, where the number of qubits always includes the
circuit inputs, outputs and ancillas).

Requirements

• Python3 version 3.10 or above

Python packages:

• Qiskit version 1.0 or above
• numpy version 1.22 or above
• sympy version 1.2.1 or above
• tabulate version 0.8.10
• argparse version 1.4.0

You can install all of them with:

pip3 install qiskit numpy sympy tabulate argparse

Older versions might work but the code hasn't been tested on them.

List of files

The files:

• compressed_prange/quantum_util/basic_arithmetic.py
• compressed_prange/quantum_util/util.py
• compressed_prange/quantum_util/modular_multi_product.py

were taken from "Reducing the number of qubits in quantum factoring"
(Chevignard, Fouque, Schrottenloher, 2024). The original version of
this code is available here.

The script files are:

• estimations.py : script that provides numerical cost estimates
• test_circuits.py : script that tests our circuit classes, checks that
  they run correctly and that our cost formulas are correctly estimated
• asymptotic.py : script that outputs analytical formulas for the costs

The source files are:

• compressed_prange/abstract_functions.py : definition of abstract functions that
  are helpful to switch between numbers and complexity formulas
• compressed_prange/berlekamp_massey.py : quantum circuits for the berlekamp-Massey
  algorithm (corresponds to Section 4.2 in the paper)
• compressed_prange/classical_algorithm.py : classical implementation of
  Wiedemann's inversion algorithm, for testing.
• compressed_prange/inversion_circuit.py : quantum circuit for Wiedemann's inversion
  (corresponds to Section 4 in the paper)
• compressed_prange/karatsuba_multiplication.py : quantum circuit for Karatsuba multiplication
  of binary polynomials and circulant matrix multiplication
• compressed_prange/list_operations.py : quantum circuits for basic operations on lists
  (see Section 3.4 in the paper)
• compressed_prange/multiplication.py : quantum circuits for matrix-vexctor multiplication
  using a constant matrix, using three different methods (see Section 5 in the paper)
• compressed_prange/sorting.py : quantum circuits for reversible sorting networks

Testing circuits

Run:

python3 test_circuits.py

to instantiate most of our quantum circuits on small instances, test that they return correct
outputs on various random inputs, and check that the theoretical cost estimates
output by the function .all_counts of each class matches or exceeds the actual cost of
the small circuit instances. Failed tests should raise an assertion error. The
contents of each test are coded in the method .test() of each class.

Cost estimates

Run:

python3 estimations.py --table previous
python3 estimations.py --table new --mult spaceopt
python3 estimations.py --table new --mult toffoliopt
python3 estimations.py --table new --mult karatsuba

in order to obtain all sub-sections of Table 1 in order. The script has three
options:

• --table : a choice between asymptotic, previous and new. Default is new.

  • asymptotic will print a (large) table comparing the costs, computed with
    .all_counts(), with the simplified asymptotic formulas given in the paper
  • previous will output a table of circuit costs taken from Table 3 in 'Improving the
    Efficiency of Quantum Circuits for Information Set Decoding' (Perriello,
    Barenghi, Pelosi, ACM Trans. Quant. Comp. 2023).
  • new will print our results (obtained with .all_counts())

• --prec : choice of precision (number of digits after comma) for the displayed numbers,
  which are in log_2. Default is 1.

• --mult : choice of multiplication circuit. Default is spaceopt

  • spaceopt will use the space-optimized circuit (Section 5.1)
  • toffoliopt will use the Toffoli-optimized circuit (Section 5.2)
  • karatsuba will use Karatsuba-based multiplication for circulant matrices (Section 5.3)

This may take some time, but should not take more than a few minutes.

Asymptotic formulas

Run:

python3 asymptotic.sage.py spaceopt --simplify
python3 asymptotic.sage.py toffoliopt --simplify 

to obtain simplified asymptotic formulas for the costs (depth and gate counts)
of the inversion circuit. These formulas assume that k = O(n). The higher-order
terms will correspond to the formulas given in Section 5 of the paper for the
space-optimized and Toffoli-optimized circuits, respectively. Some lower-order
terms which we also gave in the paper will be missing.

Karatsuba-based multiplication is not supported at the moment. The resulting
formulas would be too complicated to simplify automatically, because of the
constant parameter 'limit' used in the KaratsubaMultiplier class.

Without the option --simplify, the formulas will not be simplified.