Posts with tag “Computational Complexity”

On the complexity of CNOT-based circuit synthesis

A thesis that focuses on the study of the complexity of the CNOT-based optimal circuit synthesis problem under directed topological constraints. The problem is proved to be NP-hard to approximate by means of a prior known result about the variant with ancillae qubits.