6 papers
From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
Chenghua Liu, Boning Meng
In a landmark JACM paper recognized with the 2021 G{ö}del Prize, Cai and Chen established a complete complexity dichotomy for counting CSPs over arbitrary finite domains with algeb…
Quantum Uncomputation of Clean and Dirty Ancilla Qubits
Chenke Liu, Li Zhou, Boning Meng
Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been…
Bona: Automatic Management of Dirty Ancilla Borrowing in Quantum Circuits
Xiaoquan Xu, Chenke Liu, Boning Meng +2
The management of ancilla qubits has become a critical technique for reducing quantum circuit width. Dirty ancillas, which may be borrowed from any temporarily idle qubit regardles…
The Counting General Dominating Set Framework
Jiayi Zheng, Boning Meng
We introduce a new framework of counting problems called #GDS that encompasses #-Set, a class of domination-type problems that includes counting dominating sets and count…
Dichotomies for \#CSP on graphs that forbid a clique as a minor
Boning Meng, Yicheng Pan
We prove complexity dichotomies for \#CSP problems (not necessarily symmetric) with Boolean domain and complex range on several typical minor-closed graph classes. These dichotomie…
Matchgate signatures under variable permutations
Boning Meng, Yicheng Pan
In this article, we give a sufficient and necessary condition for determining whether a matchgate signature retains its property under a certain variable permutation, which can be…