# ZX DFS
This project leverages state-space search algorithms to optimize quantum circuits with ZX calculus. The code in this repository was utilized to conduct the experiments presented in the publication  "Exhaustive Search for Quantum Circuit Optimization using ZX Calculus (OLA 2025)". Specifically, the code included has the following features:

- Implementation of the Depth-First Search (DFS) and Iterative Deepening Depth-First Search (IDDFS) for state-space exploration formed by the rules of ZX Calculus.
- Various metrics, such as The T-gate and edge count
- Different pruning conditions to reduce the state-space.
- A Qiskit transpiler pass to ensure the applicability of our results
- Benchmarking of up to 100 standard quantum circuits with multiple optimization algorithms

This project relies heavily on:

- [PyZX](https://github.com/zxcalc/pyzx) 
- [Qiskit](https://github.com/Qiskit/qiskit)
- [Circuits](https://github.com/njross/optimizer)

## Development environment
This project was developed in Python 3.12 using Poetry and Nix for dependency management. A flake.nix is provided, that allows the export of a Docker image.

### Nix shells
With nix installed, the development shell is accessible with a simple:
```bash
nix develop
```
This will take some time, as it compiles a CPU optimized Python version. **If you do not have a Skylake CPU or do not want to compile, follow the next steps**

1. Change the CPU architecture or comment out the gcc.*.
```nix
hostPlatform = {
  gcc.arch = "MY-CPU-ARCH";
  gcc.tune = "MY-CPU-TUNE";
};

```
2. If you want to avoid compilation, comment out the Python overlays as shown below.
```nix
#overlays = [
#  (self: super: {
#    python311 = super.python31.override {
#      enableOptimizations = true;
#      reproducibleBuild = false;
#    }; # allow more optimized python
#  })
#  (self: super: {
#    python312 = super.python312.override {
#      enableOptimizations = true;
#      reproducibleBuild = false;
#    }; # allow more optimized python
#  })
#];
```
### Docker image
The flake.nix contains a derivation to build a layered Docker-image. To build the image, run:
```bash
nix build .#docker-run.x86_64-linux
cp -fv result zx_dfs.tar.gz
```

## Usage
There are different ways to interact with the library:

1. Makefile to replicate our results
2. Pre-made python scripts with a CLI
3. Qiskit transpiler pass
4. Customize the instance classes

## Makefile
To replicate our experiments for all 100 quantum circuits run:
```bash
make run-all
```
If you are only interested in the 20 quantum circuits with the lowest overall gate count (more performant) run:
```bash
make run-small
```
### Pre-made bin scripts
The folder /bin contains different python scripts to run the optimization algorithms on quantum circuits that are provided in QASM file(s). 
```bash
python run_benchmark_dfs.py -ff qc_1.qasm qc_2.qasm # DFS
python run_benchmark_iddfs.py -ff qc_1.qasm qc_2.qasm # IDDFS
python run_benchmark_full.py -ff qc_1.qasm qc_2.qasm # Full reduce (PyZX main optimization algorithm)
```

### Qiskit Compiler Pass
The class QiskitCompilerPass is derived from Qiskit's TransformationPass and can integrate with the PassManager. It is constructed with an optimization algorithm class that can take the usual parameters.

```python
import os  # allow imports
import sys

parent_dir = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
for module_folder in ["algorithms", "benchmark", "zx_dfs", "statistics", "bin"]:
    sys.path.append(f"{parent_dir}/{module_folder}")
else:
    sys.path.append(f"{parent_dir}")

from qiskit.transpiler import PassManager

from qiskit import QuantumCircuit
from zx_dfs.dfs import DFS
from zx_dfs.idfs import IDFS
from zx_dfs.qiskit_compiler_pass import QiskitCompilerPass

qc = QuantumCircuit.from_qasm_file("path/to/circuit.qasm")

test = QiskitCompilerPass(DFS())  # setup compiler pass with optimization function

# add optimization pass to passmanager
pm = PassManager([test])
pm.run()

```

## Supplementary Material
The full results of our experiments are included in the [results.pdf](results.pdf) file.
