Quantum computing is increasingly recognized as a promising approach for tackling computationally intractable problems. However, achieving the scalability necessary for real-world applications requires substantial advancements in the quantum software stack. In this work, we introduce a compiler toolchain based on a Multi-Level Intermediate Representation (MLIR) that automatically synthesizes quantum circuits from Hardware Description Language (HDL) specifications of classical functions into quantum assembly languages. Many quantum algorithms rely on combinatorial circuits as subroutines, which traditionally require extensive resources in terms of quantum gates and qubits and are often manually optimized. Our toolchain integrates a sequence of optimization passes that combine classical compiler techniques with quantum-specific improvements, resulting in an average qubit reduction of 30% and an average gate-count reduction of 20% in widely adopted benchmark circuits, including those used in cryptographic applications.

Quantum walk-based search algorithms have demonstrated an asymptotic quadratic speedup compared to classical search methods. Formulating a generic search problem as a (quantum) search over a graph makes the efficiency of the algorithm to be closely dependent on the properties of the graph itself. In this work, we present a complete implementation of a quantum walk search procedure on Johnson graphs, speeding up the solution of the Subset Sum Problem, a well-known computational problem with applications in resource allocation, scheduling, and cryptanalysis. We provide a detailed design of each sub-circuit, quantifying their costs in terms of gate count, circuit depth, and qubit width, and exhibit all figures of merit as a function of the problem parameters. Our approach includes two distinct implementations: one that minimizes qubit usage and another focused on optimizing circuit depth. We compare our solutions against the unstructured Grover based quantum search algorithm, demonstrating a reduction of the cost on terms of T-count and T-depth, for practically solvable instances. The proposed design serves as a foundational building block for the development of efficient quantum search algorithms that can be modeled on Johnson graphs, bridging the gap with existing theoretical complexity analyses.

Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.

Quantum circuit synthesis translates a classical Boolean function into an equivalent quantum circuit. The syn-thesis is solvable by playing the reversible pebble game on the logic network of the function. However, optimal solutions are im-practical for large networks, affecting the number of qubits and gates of the final quantum circuit. In this work, we improve the solution of the reversible pebble game by leveraging dominance relations on the directed acyclic graph of the classical function, reducing qubits needed for syntheses. The proposed algorithm exposes a tunable tradeoff between the available number of qubits and the circuit size expressed as T-count and T-depth. We experimentally validate our methodology on cryptographic and arithmetic benchmarks, reporting reductions between 37% and 83 % in qubit number with respect to Bennet syntheses algorithms and complete the majority of our syntheses in less than a second, improving on the current running times of state of the art approaches.