LIVIVO - The Search Portal for Life Sciences

zur deutschen Oberfläche wechseln
Back to previous search Search history
Advanced search

Your last searches

  1. AU="Feng, Shiguang"
  2. AU="De Falco, Antonio"
  3. AU="Plenter, R J"
  4. AU="Malarz, Janusz"

Search results

Result 1 - 8 of total 8

Search options

  1. Article ; Online: A Method Based on Timing Weight Priority and Distance Optimization for Quantum Circuit Transformation.

    Qian, Yang / Guan, Zhijin / Zheng, Shenggen / Feng, Shiguang

    Entropy (Basel, Switzerland)

    2023  Volume 25, Issue 3

    Abstract: In order to implement a quantum circuit on an NISQ device, it must be transformed into a functionally equivalent circuit that satisfies the device's connectivity constraints. However, NISQ devices are inherently noisy, and minimizing the number of SWAP ... ...

    Abstract In order to implement a quantum circuit on an NISQ device, it must be transformed into a functionally equivalent circuit that satisfies the device's connectivity constraints. However, NISQ devices are inherently noisy, and minimizing the number of SWAP gates added to the circuit is crucial for reducing computation errors. To achieve this, we propose a subgraph isomorphism algorithm based on the timing weight priority of quantum gates, which provides a better initial mapping for a specific two-dimensional quantum architecture. Additionally, we introduce a heuristic swap sequence selection optimization algorithm that uses a distance optimization measurement function to select the ideal sequence and reduce the number of SWAP gates, thereby optimizing the circuit transformation. Our experiments demonstrate that our proposed algorithm is effective for most benchmark quantum circuits, with a maximum optimization rate of up to 43.51% and an average optimization rate of 13.51%, outperforming existing related methods.
    Language English
    Publishing date 2023-03-07
    Publishing country Switzerland
    Document type Journal Article
    ZDB-ID 2014734-X
    ISSN 1099-4300 ; 1099-4300
    ISSN (online) 1099-4300
    ISSN 1099-4300
    DOI 10.3390/e25030465
    Database MEDical Literature Analysis and Retrieval System OnLINE

    More links

    Kategorien

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

  2. Article ; Online: Suppression of Crosstalk in Quantum Circuit Based on Instruction Exchange Rules and Duration.

    Guan, Zhijin / Liu, Renjie / Cheng, Xueyun / Feng, Shiguang / Zhu, Pengcheng

    Entropy (Basel, Switzerland)

    2023  Volume 25, Issue 6

    Abstract: Crosstalk is the primary source of noise in quantum computing equipment. The parallel execution of multiple instructions in quantum computation causes crosstalk, which causes coupling between signal lines and mutual inductance and capacitance between ... ...

    Abstract Crosstalk is the primary source of noise in quantum computing equipment. The parallel execution of multiple instructions in quantum computation causes crosstalk, which causes coupling between signal lines and mutual inductance and capacitance between signal lines, destroying the quantum state and causing the program to fail to execute correctly. Overcoming crosstalk is a critical prerequisite for quantum error correction and large-scale fault-tolerant quantum computing. This paper provides an approach for suppressing crosstalk in quantum computers based on multiple instruction exchange rules and duration. Firstly, for the majority of the quantum gates that can be executed on quantum computing devices, a multiple instruction exchange rule is proposed. The multiple instruction exchange rule reorders quantum gates in quantum circuits and separates double quantum gates with high crosstalk on quantum circuits. Then, time stakes are inserted based on the duration of different quantum gates, and quantum gates with high crosstalk are carefully separated in the process of quantum circuit execution by quantum computing equipment to reduce the influence of crosstalk on circuit fidelity. Several benchmark experiments verify the proposed method's effectiveness. In comparison to previous techniques, the proposed method improves fidelity by 15.97% on average.
    Language English
    Publishing date 2023-05-26
    Publishing country Switzerland
    Document type Journal Article
    ZDB-ID 2014734-X
    ISSN 1099-4300 ; 1099-4300
    ISSN (online) 1099-4300
    ISSN 1099-4300
    DOI 10.3390/e25060855
    Database MEDical Literature Analysis and Retrieval System OnLINE

    More links

    Kategorien

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

  3. Article ; Online: Heuristic Reordering Strategy for Quantum Circuit Mapping on LNN Architectures.

    He, Jinfeng / Xu, Hai / Feng, Shiguang / Du, Mingzhu

    publication RETRACTED

    Computational intelligence and neuroscience

    2022  Volume 2022, Page(s) 1765955

    Abstract: Because of the connection constraints of quantum devices, the quantum gate cannot operate directly on nonadjacent qubits. Quantum circuit mapping transforms a logical quantum circuit to a circuit that satisfies the connection constraints by adding SWAP ... ...

    Abstract Because of the connection constraints of quantum devices, the quantum gate cannot operate directly on nonadjacent qubits. Quantum circuit mapping transforms a logical quantum circuit to a circuit that satisfies the connection constraints by adding SWAP gates for nonadjacent qubits. Global and local heuristic reordering strategies are proposed in this paper for quantum circuit mapping over linear nearest neighbor (LNN) architectures, which are one-dimensional topology structures, to reduce the number of SWAP gates added. Experiment results show that the average improvements of the two methods are 13.19% and 15.46%, respectively. In this paper, we consider the quantum circuit mapping problem for linear nearest neighbor (LNN) architectures. We propose a global heuristic qubit reordering optimization algorithm and a local heuristic qubit reordering optimization algorithm. Compared with the other algorithm results, the average improvements of the two methods for quantum cost are 13.19% and 15.46%, respectively. The two methods apply to the realization of quantum circuit neighboring over one-dimensional quantum architectures and can be extended to algorithms that work for other quantum architectures of different topologies.
    Language English
    Publishing date 2022-05-05
    Publishing country United States
    Document type Journal Article ; Retracted Publication
    ZDB-ID 2388208-6
    ISSN 1687-5273 ; 1687-5273
    ISSN (online) 1687-5273
    ISSN 1687-5273
    DOI 10.1155/2022/1765955
    Database MEDical Literature Analysis and Retrieval System OnLINE

    More links

    Kategorien

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

  4. Book ; Online: Quantum and classical query complexities for determining connectedness of matroids

    Huang, Xiaowei / Feng, Shiguang / Li, Lvzhou

    2023  

    Abstract: Connectivity is a fundamental structural property of matroids, and has been studied algorithmically over 50 years. In 1974, Cunningham proposed a deterministic algorithm consuming $O(n^{2})$ queries to the independence oracle to determine whether a ... ...

    Abstract Connectivity is a fundamental structural property of matroids, and has been studied algorithmically over 50 years. In 1974, Cunningham proposed a deterministic algorithm consuming $O(n^{2})$ queries to the independence oracle to determine whether a matroid is connected. Since then, no algorithm, not even a random one, has worked better. To the best of our knowledge, the classical query complexity lower bound and the quantum complexity for this problem have not been considered. Thus, in this paper we are devoted to addressing these issues, and our contributions are threefold as follows: (i) First, we prove that the randomized query complexity of determining whether a matroid is connected is $\Omega(n^2)$ and thus the algorithm proposed by Cunningham is optimal in classical computing. (ii) Second, we present a quantum algorithm with $O(n^{3/2})$ queries, which exhibits provable quantum speedups over classical ones. (iii) Third, we prove that any quantum algorithm requires $\Omega(n)$ queries, which indicates that quantum algorithms can achieve at most a quadratic speedup over classical ones. Therefore, we have a relatively comprehensive understanding of the potential of quantum computing in determining the connectedness of matroids.\
    Keywords Quantum Physics ; Computer Science - Computational Complexity
    Subject code 005
    Publishing date 2023-06-21
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  5. Book ; Online: Capturing the polynomial hierarchy by second-order revised Krom logic

    Wang, Kexu / Feng, Shiguang / Zhao, Xishun

    2022  

    Abstract: We study the expressive power and complexity of second-order revised Krom logic (SO-KROM$^{r}$). On ordered finite structures, we show that its existential fragment $\Sigma^1_1$-KROM$^r$ equals $\Sigma^1_1$-KROM, and captures NL. On all finite structures, ...

    Abstract We study the expressive power and complexity of second-order revised Krom logic (SO-KROM$^{r}$). On ordered finite structures, we show that its existential fragment $\Sigma^1_1$-KROM$^r$ equals $\Sigma^1_1$-KROM, and captures NL. On all finite structures, for $k\geq 1$, we show that $\Sigma^1_{k}$ equals $\Sigma^1_{k+1}$-KROM$^r$ if $k$ is even, and $\Pi^1_{k}$ equals $\Pi^1_{k+1}$-KROM$^r$ if $k$ is odd. The result gives an alternative logic to capture the polynomial hierarchy. We also introduce an extended version of second-order Krom logic (SO-EKROM). On ordered finite structures, we prove that SO-EKROM collapses to $\Pi^{1}_{2}$-EKROM and equals $\Pi^1_1$. Both SO-EKROM and $\Pi^{1}_{2}$-EKROM capture co-NP on ordered finite structures.
    Keywords Computer Science - Logic in Computer Science ; Computer Science - Computational Complexity
    Publishing date 2022-07-19
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  6. Book ; Online: The Complexity of Quantum Circuit Mapping with Fixed Parameters

    Zhu, Pengcheng / Zheng, Shenggen / Wei, Lihua / Cheng, Xueyun / Guan, Zhijin / Feng, Shiguang

    2022  

    Abstract: 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 equivalent one that is compliant with the NISQ device's architecture constraint by ...

    Abstract 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 equivalent one that is compliant with the NISQ device's architecture constraint by adding SWAP gates. The QCM problem asks the minimal number of auxiliary SWAP gates, and is NP-complete. The complexity of QCM with fixed parameters is studied in the paper. We give an exact algorithm for QCM, and show that the algorithm runs in polynomial time if the NISQ device's architecture is fixed. If the number of qubits of the quantum circuit is fixed, we show that the QCM problem is NL-complete by a reduction from the undirected shortest path problem. Moreover, the fixed-parameter complexity of QCM is W[1]-hard when parameterized by the number of qubits of the quantum circuit. We prove the result by a reduction from the clique problem. If taking the depth of the quantum circuits and the coupling graphs as parameters, we show that the QCM problem is still NP-complete over shallow quantum circuits, and planar, bipartite and degree bounded coupling graphs.
    Keywords Quantum Physics ; Computer Science - Computational Complexity
    Subject code 511
    Publishing date 2022-07-18
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  7. Book ; Online: Path Checking for MTL and TPTL over Data Words

    Feng, Shiguang / Lohrey, Markus / Quaas, Karin

    2014  

    Abstract: 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 verification of real-timed systems. It was recently shown that the path checking ... ...

    Abstract 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 verification of real-timed systems. It was recently shown that the path checking problem for MTL, when evaluated over finite timed words, is in the parallel complexity class NC. In this paper, we derive precise complexity results for the path-checking problem for MTL and TPTL when evaluated over infinite data words over the non-negative integers. Such words may be seen as the behaviours of one-counter machines. For this setting, we give a complete analysis of the complexity of the path-checking problem depending on the number of register variables and the encoding of constraint numbers (unary or binary). As the two main results, we prove that the path-checking problem for MTL is P-complete, whereas the path-checking problem for TPTL is PSPACE-complete. The results yield the precise complexity of model checking deterministic one-counter machines against formulae of MTL and TPTL.
    Keywords Computer Science - Logic in Computer Science
    Subject code 511
    Publishing date 2014-12-11
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  8. Book ; Online ; Thesis: The Expressive Power, Satisfiability and Path Checking Problems of MTL and TPTL over Non-Monotonic Data Words

    Feng, Shiguang [Verfasser] / Lohrey, Markus [Akademischer Betreuer] / Lohrey, Markus [Gutachter] / Droste, Manfred [Akademischer Betreuer] / Droste, Manfred [Gutachter] / Lange, Martin [Gutachter]

    2016  

    Author's details Shiguang Feng ; Gutachter: Markus Lohrey, Manfred Droste, Martin Lange ; Markus Lohrey, Manfred Droste
    Keywords Naturwissenschaften ; Science
    Subject code sg500
    Language English
    Publisher Universitätsbibliothek Leipzig
    Publishing place Leipzig
    Document type Book ; Online ; Thesis
    Database Digital theses on the web

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top