3 citations · 5 across the 6 of their papers we have counts for
7 papers
Nearest neighbor synthesis of CNOT circuits on general quantum architectures
Xinyu Chen, Mingqiang Zhu, Xueyun Cheng +3
NISQ devices have inherent limitations in terms of connectivity and hardware noise. The synthesis of CNOT circuits considers the physical constraints and transforms quantum algorit…
Universal approach to deterministic spatial search via alternating quantum walks
Qingwen Wang, Ying Jiang, Shiguang Feng +1
Spatial search is an important problem in quantum computation, which aims to find a marked vertex on a graph. We propose a novel approach for designing deterministic quantum search…
Quantum and classical query complexities for determining connectedness of matroids
Xiaowei Huang, Shiguang Feng, Lvzhou Li
Connectivity is a fundamental structural property of matroids, and has been studied algorithmically over 50 years. In 1974, Cunningham proposed a deterministic algorithm consuming…
The Complexity and Expressive Power of Second-Order Extended Logic
Shiguang Feng, Xishun Zhao
We study the expressive powers of SO-HORN, SO-HORN and SO-HORN on all finite structures. We show that SO-HORN, SO-HORN, FO(LFP) coincide with each o…
The Complexity of Quantum Circuit Mapping with Fixed Parameters
Pengcheng Zhu, Shenggen Zheng, Lihua Wei +3
A quantum circuit must be preprocessed before implementing on NISQ devices due to the connectivity constraint. Quantum circuit mapping (QCM) transforms the circuit into an equivale…
Capturing the polynomial hierarchy by second-order revised Krom logic
Kexu Wang, Shiguang Feng, Xishun Zhao
We study the expressive power and complexity of second-order revised Krom logic (SO-KROM). On ordered finite structures, we show that its existential fragment -KROM$^r…