Comparison of Exponentially Decreasing Vs. Polynomially Decreasing Objective Functions for Making Quantum Circuits Nearest Neighbour Compliant

Leo Rogers*, John McAllister

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many proposed architectures for quantum computing involve arranging qubits in a lattice, and then using swap gates to move the quantum states between qubits to enable any pair of qubits to interact with each other. Since swap gates perform no useful computation, they can be viewed as an overhead whose number should be minimised in efficient quantum programs. The location of the swap gates in a quantum circuit are chosen by minimising an objective function characterising the structure of the quantum circuit. Those which currently offer the lowest swap cost reduce the significance of each gate to the objective function relative to its position in the circuit. The criterion that describes how quickly the significance must decrease. In this paper, we show that to satisfy this criterion, it is necessary and sufficient for the decay to be exponential. However, when applying this new objective function, there is no significant improvement over the old function, with most of the benchmark circuits having less than 5% improvement. Only three circuits had more than 10% improvement in swap cost, and these circuits were all less than 100 gates long. The three longest circuits in the benchmark suite had less than 1% change in swap cost. There is also a significant penalty in run time, in one case reaching 265.48%.

Original languageEnglish
Title of host publicationEmbedded Computer Systems
Subtitle of host publicationArchitectures, Modeling, and Simulation - 19th International Conference, SAMOS 2019, Proceedings
EditorsDionisios N. Pnevmatikatos, Maxime Pelcat, Matthias Jung
PublisherSpringer-Verlag
Pages348-357
Number of pages10
ISBN (Print)9783030275617
DOIs
Publication statusPublished - 08 Aug 2019
Event19th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS 2019 - Samos, Greece
Duration: 07 Jul 201911 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11733 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS 2019
CountryGreece
CitySamos
Period07/07/201911/07/2019

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Comparison of Exponentially Decreasing Vs. Polynomially Decreasing Objective Functions for Making Quantum Circuits Nearest Neighbour Compliant'. Together they form a unique fingerprint.

  • Cite this

    Rogers, L., & McAllister, J. (2019). Comparison of Exponentially Decreasing Vs. Polynomially Decreasing Objective Functions for Making Quantum Circuits Nearest Neighbour Compliant. In D. N. Pnevmatikatos, M. Pelcat, & M. Jung (Eds.), Embedded Computer Systems: Architectures, Modeling, and Simulation - 19th International Conference, SAMOS 2019, Proceedings (pp. 348-357). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11733 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-27562-4_25