research-article

Harmony-search algorithm for 2D nearest neighbor quantum circuits realization

Authors:

Mohammad Gh. Alfailakawi,

Suha HamdanAuthors Info & Claims

Expert Systems with Applications: An International Journal, Volume 61, Issue C

Pages 16 - 27

https://doi.org/10.1016/j.eswa.2016.04.038

Published: 01 November 2016 Publication History

Abstract

The emerging field of quantum computing is addressed in this work.A Harmony Search (HS) based algorithm is proposed to efficiently realize quantum circuits on two dimension grids.The objective is to minimize the number of SWAP gates for two dimension nearest neighbor architecture.A local optimization heuristic is embedded with HS algorithm to further improve the solution quality.Experimental results on real benchmarks demonstrate the scalability and effectiveness of the proposed technique. Motivated by its promising applications, quantum computing is an emerging area of research. This paper addresses the NP-complete problem of finding Nearest Neighbor (NN) realization of quantum circuits on a 2-Dimensional grid. In certain quantum technologies, only physically adjacent qubits are allowed to interact with each other hence the need for NN requirement. Circuits with distant qubits are made NN-compliant by introducing swap gates, hence increasing cost. In this work, we present a Harmony Search (HS) based intelligent metaheuristic algorithm to efficiently realize low cost NN circuits utilizing input line reordering. The distinct feature of the proposed technique is that initial qubits placement is found using HS based metaheuristic followed by an efficient, problem-specific local heuristic to perform swap gate insertion. The effectiveness of the proposed algorithm is demonstrated by comparing its performance to a number of recent published approaches. Solutions found by the proposed technique show reduction in the number of swaps needed in the range of 4% - 36% on average when compared to state-of-the-art techniques. Compared to other approaches, the implemented algorithm is scalable and was able to find optimized circuits within 4 seconds in the worst case.

References

[1]

I. Ahmad, M.G. Mohammad, A.A. Salman, S.A. Hamdan, Broadcast scheduling in packet radio networks using harmony search algorithm, Expert Systems with Applications, 39 (2012) 1526-1535.

Digital Library

[2]

M. AlFailakawi, L. AlTerkawi, I. Ahmad, S. Hamdan, Line ordering of reversible circuits for linear nearest neighbor realization, Quantum Information Processing, 12 (2013) 3319-3339.

Digital Library

[3]

M. Arabzadeh, M. Saeedi, Rcviewer+ (2nd), 2013.

[4]

D. Bacon, W. van Dam, Recent progress in quantum algorithms, Communications of the ACM, 53 (2010) 84-93.

Digital Library

[5]

A. Blais, J. Gambetta, A. Wallraff, D.I. Schuster, S.M. Girvin, M.H. Devoret, R.J. Schoelkopf, Quantum-information processing with circuit quantum electrodynamics, Physical Review A, 75 (2007) 032329.

[6]

D. Cheung, D. Maslov, S. Severini, Translation techniques between quantum circuit architectures, 2007.

[7]

B. Choi, R. Van Meter, A ¿ ( N ) -depth quantum adder on the 2d ntc quantum computer architecture, Journal on Emerging Technologies in Computing Systems, 8 (2012) 24:1-24:22.

Digital Library

[8]

R. Dash, P. Dash, Efficient stock price prediction using a self evolving recurrent neuro-fuzzy inference system optimized through a modified differential harmony search technique, Expert Systems with Applications, 52 (2016) 75-90.

Digital Library

[9]

Dwave, Dwave: The quantum computing company, 2016.

[10]

A.G. Fowler, S.J. Devitt, L.C.L. Hollenberg, Implementation of shor's algorithm on a linear nearest neighbour qubit array, Quantum Information and Computation, 4 (2004) 237-251.

Digital Library

[11]

A.G. Fowler, C.D. Hill, L.C.L. Hollenberg, Quantum error correction on linear nearest neighbor qubit arrays, 2004.

[12]

A.G. Fowler, A.M. Stephens, P. Groszkowski, High-threshold universal quantum computation on the surface code, Physical Review A, 80 (2009).

[13]

Z.W. Geem, Novel derivative of harmony search algorithm for discrete design variables, Applied Mathematics and Computation, 199 (2008) 223-230.

[14]

Z.W. Geem, Music-inspired harmony search algorithm: Theory and applications, Springer, 2009.

Digital Library

[15]

Z.W. Geem, J. Kim, G. Loganathan, A new heuristic optimization algorithm, Simulation, 76 (2001) 60-68.

[16]

B. Giles, P. Selinger, Exact synthesis of multiqubit clifford+ t circuits, Physical Review A, 87 (2013) 032332.

[17]

L. Grover, Quantum computers can search arbitrarily large databases by a single query, Physical Review Letters, 79 (1997) 4709-4712.

[18]

H. Haffner, W. Hansel, C.F. Roos, J. Benhelm, D. Chek-al kar, M. Chwalla, R. Blatt, Scalable multiparticle entanglement of trapped ions, Nature, 438 (2005) 643-646.

[19]

H. Häffner, W. Hänsel, C.F. Roos, J. Benhelm, D.C. al kar, M. Chwalla, R. Blatt, Scalable multiparticle entanglement of trapped ions, Nature, 438 (2005) 643-646.

[20]

Y. Hirata, M. Nakanishi, S. Yamashita, Y. Nakashima, An efficient conversion of quantum circuits to a linear nearest neighbor architecture, Quantum Information & Computing, 11 (2011) 142-166.

Digital Library

[21]

L. Hollenberg, A. Greentree, A. Fowler, C. Wellard, Two-dimensional architectures for donor-based quantum computing, Physical Review B, 74 (2006) 045311.

[22]

I. Kassal, J.D. Whitfield, A. Perdomo-Ortiz, M.-H. Yung, A. Aspuru-Guzik, Simulating Chemistry Using Quantum Computers, Annual Review of Physical Chemistry, 62 (2011) 185-207.

[23]

V. Kliuchnikov, D. Maslov, M. Mosca, Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and t gates, Quantum Information and Computation, 13 (2013) 607-630.

Digital Library

[24]

A. Kole, K. Datta, I. Sengupta, A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using n -gate lookahead, IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 6 (2016) 62-72.

[25]

X. Kong, L. Gao, H. Ouyang, S. Li, A simplified binary harmony search algorithm for large scale 0-1 knapsack problems, Expert Systems with Applications, 42 (2015) 5337-5355.

Digital Library

[26]

M. Kumph, M. Brownnutt, R. Blatt, Two-dimensional arrays of radio-frequency ion traps with addressable interactions, New Journal of Physics, 13 (2011) 073043.

[27]

S.A. Kutin, Shor's algorithm on a nearest-neighbor machine, in: Asian conference on quantum information science (aqis), 2007.

[28]

Y. Li, X. Li, J.N. Gupta, Solving the multi-objective flowline manufacturing cell scheduling problem by hybrid harmony search, Expert Systems with Applications, 42 (2015) 1409-1417.

Digital Library

[29]

C.-C. Lin, S. Sur-Kolay, N.K. Jha, Paqcs: Physical design-aware fault-tolerant quantum circuit synthesis, Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 23 (2015) 1221-1234.

[30]

A. Lye, R. Wille, R. Drechsler, Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits, 2015.

[31]

F. Magniez, M. Santha, M. Szegedy, Quantum algorithms for the triangle problem, 2005.

[32]

D. Manjarres, I. Landa-Torres, S. Gil-Lopez, J.D. Ser, M. Bilbao, S. Salcedo-Sanz, Z. Geem, A survey on applications of the harmony search algorithm, Engineering Applications of Artificial Intelligence, 26 (2013) 1818-1831.

Digital Library

[33]

I.L. Markov, M. Saeedi, Constant-optimized quantum circuits for modular multiplication and exponentiation, Quantum Information and Computation, 12 (2012) 361-394.

Digital Library

[34]

I.L. Markov, M. Saeedi, Faster quantum number factoring via circuit synthesis, Physical Review A, 87 (2013) 012310.

[35]

D. Maslov, Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures, Physical Review A, 76 (2007) 052310.

[36]

D. Maslov, G. Dueck, D. Miller, C. Negrevergne, Quantum circuit simplification and level compaction, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 27 (2008) 436-444.

Digital Library

[37]

D. Maslov, S.M. Falconer, M. Mosca, Quantum circuit placement, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27 (2008) 752-763.

Digital Library

[38]

A. Matsuo, S. Yamashita, Changing the gate order for optimal lnn conversion, 2012.

[39]

D.M. Miller, M. Soeken, R. Drechsler, Mapping ncv circuits to optimized clifford+t circuits, in: Lecture Notes in Computer Science, 8507, Springer International Publishing, 2014, pp. 163-175.

[40]

N.H. Nickerson, Y. Li, S.C. Benjamin, Topological quantum computing with a very noisy network and local error rates approaching one percent, Nature communications, 4 (2013) 1756.

[41]

M.A. Nielsen, I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2002.

Digital Library

[42]

P. Niemann, S. Basu, A. Chakrabarti, N.K. Jha, R. Wille, Synthesis of quantum circuits for dedicated physical machine descriptions, Springer, 2015.

[43]

P. Pham, K.M. Svore, A 2d nearest-neighbor quantum architecture for factoring in polylogarithmic depth, Quantum Information and Computation, 13 (2013) 937-962.

Digital Library

[44]

I. Polian, A.G. Fowler, Design automation challenges for scalable quantum architectures, ACM, New York, NY, USA, 2015.

[45]

R. Wille, O. Keszöcze, M. Walter, P. Rohrs, A. Chattopadhya, R. Drechsler, Look-ahead schemes for nearest neighbor optimization of 1d and 2d quantum circuits, 2016.

[46]

D.J. Rosenbaum, Optimal quantum circuits for nearest-neighbor architectures, 2013.

[47]

M. Saeedi, I.L. Markov, Synthesis and optimization of reversible circuits - a survey, ACM Computing Surveys, 45 (2013).

Digital Library

[48]

M. Saeedi, R. Wille, R. Drechsler, Synthesis of quantum circuits for linear nearest neighbor architectures, Quantum Information Processing, 10 (2011) 355-377.

Digital Library

[49]

A. Shafaei, M. Saeedi, M. Pedram, Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures., 2013.

[50]

A. Shafaei, M. Saeedi, M. Pedram, Qubit placement to minimize communication overhead in 2d quantum architectures, 2014.

[51]

P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26 (1997) 1484-1509.

Digital Library

[52]

R.R. Shrivastwa, K. Datta, I. Sengupta, Fast qubit placement in 2d architecture using nearest neighbor realization, 2015.

[53]

T. Simonite, IBM shows off a quantum computing chip, 2015.

[54]

J.M. Taylor, J.R. Petta, A.C. Johnson, A. Yacoby, C.M. Marcus, M.D. Lukin, Relaxation, dephasing, and quantum control of electron spins in double quantum dots, Physical Review B, 76 (2007) 035315.

[55]

R. Wille, D. Grosse, L. Teuber, G.W. Dueck, R. Drechsler, Revlib: An online resource for reversible functions and reversible circuits, 2008.

[56]

R. Wille, A. Lye, R. Drechsler, Exact reordering of circuit lines for nearest neighbor quantum architectures, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33 (2014) 1818-1831.

Cited By

Mulderij JAardal KChiscop IPhillipson F(2023)A Polynomial Size Model with Implicit SWAP Gate Counting for Exact Qubit ReorderingComputational Science – ICCS 202310.1007/978-3-031-36030-5_7(72-89)Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36030-5_7
Chang KLee C(2022)Mapping Nearest Neighbor Compliant Quantum Circuits Onto a 2-D Hexagonal ArchitectureIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.312786841:10(3373-3386)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TCAD.2021.3127868
Chhangte LChakrabarty A(2022)Near-optimal circuit mapping with reduced search paths on IBM quantum architecturesMicroprocessors & Microsystems10.1016/j.micpro.2022.10463794:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.micpro.2022.104637
Show More Cited By

Recommendations

Mapping from multiple-control Toffoli circuits to linear nearest neighbor quantum circuits

In recent years, quantum computing research has been attracting more and more attention, but few studies on the limited interaction distance between quantum bits (qubit) are deeply carried out. This paper presents a mapping method for transforming ...
Line ordering of reversible circuits for linear nearest neighbor realization

Real quantum computing technologies have different restrictions and constraints which need to be considered during circuit synthesis. In certain technologies, only physically adjacent qubits can interact, which restricts their realizations to only ...
Quantum Boolean Circuits are 1-Testable

Recently, a systematic procedure was proposed to derive a minimum input quantum circuit for any given classical logic with the generalized quantum Toffoli gate, which is universal in Boolean logic. Since quantum Boolean circuits are reversible, we can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Expert Systems with Applications: An International Journal

Expert Systems with Applications: An International Journal Volume 61, Issue C

November 2016

395 pages

ISSN:0957-4174

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 November 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mulderij JAardal KChiscop IPhillipson F(2023)A Polynomial Size Model with Implicit SWAP Gate Counting for Exact Qubit ReorderingComputational Science – ICCS 202310.1007/978-3-031-36030-5_7(72-89)Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36030-5_7
Chang KLee C(2022)Mapping Nearest Neighbor Compliant Quantum Circuits Onto a 2-D Hexagonal ArchitectureIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.312786841:10(3373-3386)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TCAD.2021.3127868
Chhangte LChakrabarty A(2022)Near-optimal circuit mapping with reduced search paths on IBM quantum architecturesMicroprocessors & Microsystems10.1016/j.micpro.2022.10463794:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.micpro.2022.104637
Barán BCarballude AVillagra M(2021)A Multiobjective Approach for Nearest Neighbor Optimization of N-Dimensional Quantum CircuitsSN Computer Science10.1007/s42979-020-00398-32:1Online publication date: 6-Jan-2021
https://dl.acm.org/doi/10.1007/s42979-020-00398-3
van Houte RMulderij JAttema TChiscop IPhillipson F(2020)Mathematical formulation of quantum circuit design problems in networks of quantum computersQuantum Information Processing10.1007/s11128-020-02630-819:5Online publication date: 17-Mar-2020
https://dl.acm.org/doi/10.1007/s11128-020-02630-8
Sanaei SMohammadzadeh N(2019)Qubit mapping of one-way quantum computation patterns onto 2D nearest-neighbor architecturesQuantum Information Processing10.1007/s11128-019-2177-x18:2(1-19)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11128-019-2177-x
Rogers LMcAllister J(2019)Comparison of Exponentially Decreasing Vs. Polynomially Decreasing Objective Functions for Making Quantum Circuits Nearest Neighbour CompliantEmbedded Computer Systems: Architectures, Modeling, and Simulation10.1007/978-3-030-27562-4_25(348-357)Online publication date: 7-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-27562-4_25
Ruffinelli DBarán B(2017)Linear nearest neighbor optimization in quantum circuitsQuantum Information Processing10.1007/s11128-017-1662-316:9(1-26)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11128-017-1662-3
Wang YGuo ZWang Y(2017)Enhanced harmony search with dual strategies and adaptive parametersSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-017-2563-121:15(4431-4445)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00500-017-2563-1

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents