Abstract
Quantum arithmetic circuits have practical applications in various quantum algorithms. In this paper, we address quantum addition on 2-dimensional nearest-neighbor architectures based on the work presented by Choi and Van Meter (JETC 2012). To this end, we propose new circuit structures for some basic blocks in the adder, and reduce communication overhead by adding concurrency to consecutive blocks and also by parallel execution of expensive Toffoli gates. The proposed optimizations reduce total depth from \(140\sqrt n+k_1\) to \(92\sqrt n+k_2\) for constants k 1,k 2 and affect the computation fidelity considerably.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cheung, D., Maslov, D., Severini, S.: Translation techniques between quantum circuit architectures. In: Workshop on Quant. Inf. Proc. (December 2007)
Díaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002)
Choi, B.-S., Van Meter, R.: On the effect of quantum interaction distance on quantum addition circuits. J. Emerg. Technol. Comput. Syst. 7(3), 11(1-17) (2011)
Beals, R., et al.: Efficient distributed quantum computing arXiv:1207.2307v2 (2012)
Takahashi, Y., Kunihiro, N., Ohta, K.: The quantum Fourier transform on a linear nearest neighbor architecture. Quant. Inf. Comput. 7, 383–391 (2007)
Maslov, D.: Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Phys. Rev. A 76 (2007)
Fowler, A.G., Devitt, S.J., Hollenberg, L.: Implementation of Shor’s algorithm on a linear nearest neighbour qubit array. Quant. Inf. Comput. 4, 237–245 (2004)
Kutin, S.A.: Shor’s algorithm on a nearest-neighbor machine. In: Asian Conf. on Quant. Inf. Sci. (2007)
Pham, P., Svore, K.M.: A 2D nearest-neighbor quantum architecture for factoring arXiv:1207.6655 (2012)
Fowler, A.G., Hill, C.D., Hollenberg, L.C.L.: Quantum error correction on linear nearest neighbor qubit arrays. Phys. Rev. A 69, 042314.1–042314.4 (2004)
Arabzadeh, M., Saheb Zamani, M., Sedighi, M., Saeedi, M.: Depth-optimized reversible circuit synthesis. Quant. Inf. Proc. 12(4), 1677–1699 (2013)
Möttönen, M., Vartiainen, J.J.: Decompositions of general quantum gates. In: Trends in Quant. Comput. Research, Ch. 7. NOVA Publishers, New York (2006)
Shende, V.V., Bullock, S.S., Markov, I.L.: Synthesis of quantum-logic circuits. IEEE Trans. CAD 25(6), 1000–1010 (2006)
Saeedi, M., Arabzadeh, M., Saheb Zamani, M., Sedighi, M.: Block-based quantum-logic synthesis. Quant. Inf. Comput. 11(3-4), 0262–0277 (2011)
Saeedi, M., Saheb Zamani, M., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. J. Emerg. Technol. Comput. 6(4), 13(1–26) (2010)
Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quant. Inf. Proc. 10(3), 355–377 (2011)
Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quant. Inf. Comput. 11(1-2), 0142–0166 (2011)
Shafaei, A., Saeedi, M., Pedram, M.: Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In: Design Autom. Conf. (2013)
Choi, B.-S., Van Meter, R.: A \(\sqrt{n}\)-depth quantum adder on the 2D NTC quantum computer architecture. J. Emerg. Technol. Comput. Syst. 8(3), 24(1-22) (2012)
Szkopek, T., et al.: Threshold error penalty for fault-tolerant quantum computation with nearest neighbor communication. IEEE Trans. Nano. 5(1), 42–49 (2006)
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge Univ. Press (2000)
Markov, I.L., Saeedi, M.: Constant-optimized quantum circuits for modular multiplication and exponentiation. Quant. Info. Comput. 12(5-6), 361–394 (2012)
Markov, I.L., Saeedi, M.: Faster quantum number factoring via circuit synthesis. Phys. Rev. A 87, 012310 (2013)
Shende, V.V., Markov, I.L.: On the CNOT-cost of TOFFOLI gates. Quant. Inf. Comput. 9(5-6), 461–486 (2009)
Amy, M., Maslov, D., Mosca, M., Rötteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. CAD arXiv:1206.0758v3 (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saeedi, M., Shafaei, A., Pedram, M. (2013). Constant-Factor Optimization of Quantum Adders on 2D Quantum Architectures. In: Dueck, G.W., Miller, D.M. (eds) Reversible Computation. RC 2013. Lecture Notes in Computer Science, vol 7948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38986-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-38986-3_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38985-6
Online ISBN: 978-3-642-38986-3
eBook Packages: Computer ScienceComputer Science (R0)