|
Linear circuit synthesis using weighted Steiner trees (pp721-733)
Nir Gavrielov, Alexander Ivrii, and
Shelly Garion
doi:
https://doi.org/10.26421/QIC24.9-10-1
Abstracts:
CNOT
circuits are a common building block of general quantum circuits. The
problem of synthesizing and optimizing such circuits has received a lot
of attention in the quantum computing literature. This problem is
especially challenging for quantum devices with restricted connectivity,
where two-qubit
gates can only be placed between adjacent
qubits.
The state-of-the-art algorithms for optimizing the number of
CNOT
gates are heuristic algorithms that are based on Gaussian elimination
and that use Steiner trees to connect between different subsets of
qubits.
In this article, we suggest considering
\emph{weighted}
Steiner trees, and we present a simple low-cost heuristic to compute
weights. The simulated evaluation shows that the suggested heuristic is
almost always beneficial and reduces the number of
CNOT
gates by up to 10%.
Key Words:
linear circuit synthesis,
Steiner trees, quantum circuit compilation, quantum information |
