3 citations · 7 across the 10 of their papers we have counts for
11 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…
VisualEnv: visual Gym environments with Blender
Andrea Scorsoglio, Roberto Furfaro
In this paper VisualEnv, a new tool for creating visual environment for reinforcement learning is introduced. It is the product of an integration of an open-source modelling and re…
Path Checking for MTL and TPTL over Data Words
Shiguang Feng, Markus Lohrey, Karin Quaas
Metric temporal logic (MTL) and timed propositional temporal logic (TPTL) are quantitative extensions of linear temporal logic, which are prominent and widely used in the verificat…
Satisfiability of ECTL* with tree constraints
Claudia Carapelle, Shiguang Feng, Alexander Kartzow +1
Recently, we have shown that satisfiability for with constraints over is decidable using a new technique. This approach reduces the satisfiability pr…
The expressive power of revised Datalog on problems with closure properties
Shiguang Feng
In this paper, we study the expressive power of revised Datalog on the problems that are closed under substructures. We show that revised Datalog cannot define all the problems tha…
On the Expressiveness of TPTL and MTL over ω-Data Words
Claudia Carapelle, Shiguang Feng, Oliver Fernández Gil +1
Metric Temporal Logic (MTL) and Timed Propositional Temporal Logic (TPTL) are prominent extensions of Linear Temporal Logic to specify properties about data languages. In this pape…