Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Implementing multi-controlled X gates using the quantum Fourier transform

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

Quantum computing has the potential to solve many complex algorithms in the domains of optimization, arithmetics, structural search, financial risk analysis, machine learning, image processing, and others. Quantum circuits built to implement these algorithms usually require multi-controlled gates as fundamental building blocks, where the multi-controlled Toffoli stands out as the primary example. For implementation in quantum hardware, these gates should be decomposed into many elementary gates, which results in a large depth of the final quantum circuit. However, even moderately deep quantum circuits have low fidelity due to decoherence effects and, thus, may return an almost perfectly uniform distribution of the output results. This paper proposes a different approach for efficient cost multi-controlled gates implementation using the quantum Fourier transform. We show how the depth of the circuit can be significantly reduced using only a few ancilla qubits, making our approach viable for application to noisy intermediate-scale quantum computers. This quantum arithmetic-based approach can be efficiently used to implement many complex quantum gates.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

Data availability

The datasets generated and analyzed during the current study are available from the corresponding author on reasonable request.

References

  1. Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys.21(6), 467–488 (1982).https://doi.org/10.1007/BF02650179

    Article MathSciNet  Google Scholar 

  2. McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S.C., Yuan, X.: Quantum computational chemistry. Rev. Mod. Phys.92(1), 015003 (2020).https://doi.org/10.1103/RevModPhys.92.015003

    Article ADS MathSciNet  Google Scholar 

  3. Bauer, B., Bravyi, S., Motta, M., Chan, G.K.-L.: Quantum algorithms for quantum chemistry and quantum materials science. Chem. Rev.120(22), 12685–12717 (2020).https://doi.org/10.1021/acs.chemrev.9b00829

    Article  Google Scholar 

  4. Ichikawa, T., Hakoshima, H., Inui, K., Ito, K., Matsuda, R., Mitarai, K., Miyamoto, K., Mizukami, W., Mori, Y., Nakano, Y., Nakayama, A., Okada, K. N., Sugimoto, T., Takahira, S., Takemori, N., Tsukano, S., Ueda, H., Watanabe, R., Yoshida, Y., Fujii, K.: A comprehensive survey on quantum computer usage: How many qubits are employed for what purposes? (2023) Preprint athttps://doi.org/10.48550/arXiv.2307.16130

  5. Schuld, M., Fingerhuth, M., Petruccione, F.: Implementing a distance-based classifier with a quantum interference circuit. EPL119(6), 60002 (2017).https://doi.org/10.1209/0295-5075/119/60002

    Article ADS  Google Scholar 

  6. Rebentrost, P., Mohseni, M., Lloyd, S.: Quantum support vector machine for big data classification. Phys. Rev. Lett.113(13), 130503 (2014).https://doi.org/10.1103/PhysRevLett.113.130503

    Article ADS  Google Scholar 

  7. Li, Y.-C., Zhou, R.-G., Xu, R.-Q., Luo, J., Hu, W.-W.: A quantum deep convolutional neural network for image recognition. Quantum Sci. Technol.5(4), 44003 (2020).https://doi.org/10.1088/2058-9565/ab9f93

    Article  Google Scholar 

  8. Orús, R., Mugel, S., Lizaso, E.: Quantum computing for finance: overview and prospects. Rev. Phys.4, 100028 (2019).https://doi.org/10.1016/j.revip.2019.100028

    Article  Google Scholar 

  9. Woerner, S., Egger, D.J.: Quantum risk analysis. Npj Quantum Inf.5(1), 15 (2019).https://doi.org/10.1038/s41534-019-0130-6

    Article ADS  Google Scholar 

  10. Stamatopoulos, N., Egger, D.J., Sun, Y., Zoufal, C., Iten, R., Shen, N., Woerner, S.: Option pricing using quantum computers. Quantum4, 291 (2020).https://doi.org/10.22331/q-2020-07-06-291

    Article  Google Scholar 

  11. Martin, A., Candelas, B., Rodríguez-Rozas, Á., Martín-Guerrero, J., Chen, X., Lamata, L., Orús, R., Solano, E., Sanz, M.: Toward pricing financial derivatives with an IBM quantum computer. Phys. Rev. Res.3(1), 013167 (2021).https://doi.org/10.1103/PhysRevResearch.3.013167

    Article  Google Scholar 

  12. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing STOC’96. Association for Computing Machinery, pp. 212–219. NewYork, NY, USA (1996).https://doi.org/10.1145/237814.237866

  13. Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A52(5), 3457–3467 (1995).https://doi.org/10.1103/PhysRevA.52.3457

    Article ADS  Google Scholar 

  14. Saeedi, M., Pedram, M.: Linear-depth quantum circuits for\(n\)-qubit Toffoli gates with no ancilla. Phys. Rev. A87(6), 062318 (2013).https://doi.org/10.1103/PhysRevA.87.062318

    Article ADS  Google Scholar 

  15. da Silva, A.J., Park, D.K.: Linear-depth quantum circuits for multiqubit controlled gates. Phys. Rev. A106(4), 042602 (2022).https://doi.org/10.1103/PhysRevA.106.042602

    Article ADS MathSciNet  Google Scholar 

  16. Maslov, D.: Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Phys. Rev. A93(2), 022311 (2016).https://doi.org/10.1103/PhysRevA.93.022311

    Article ADS  Google Scholar 

  17. Balauca, S., Arusoaie, A.: Efficient constructions for simulating multi controlled quantum gates. In: Groen, D., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds.) Computational Science - ICCS 2022, vol. 13353, pp. 179–194. Springer International Publishing, Cham (2022)

    Chapter  Google Scholar 

  18. Nielsen, M.C., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2010)

    Google Scholar 

  19. Barenco, A., Ekert, A., Suominen, K.-A., Törmä, P.: Approximate quantum Fourier transform and decoherence. Phys. Rev. A54(1), 139–146 (1996).https://doi.org/10.1103/PhysRevA.54.139

    Article ADS MathSciNet  Google Scholar 

  20. Draper, T. G.: Addition on a quantum computer (2000).https://doi.org/10.48550/arXiv.quant-ph/0008033

  21. Ruiz-Perez, L., Garcia-Escartin, J.C.: Quantum arithmetic with the Quantum Fourier Transform. Quantum Inf. Process.16(6), 1–14 (2017).https://doi.org/10.1007/s11128-017-1603-1

    Article MathSciNet  Google Scholar 

  22. Yuan, Y., Wang, C., Wang, B., Chen, Z.-Y., Dou, M.-H., Wu, Y.-C., Guo, G.-P.: An improved QFT-based quantum comparator and extended modular arithmetic using one ancilla qubit. New J. Phys.25(10), 103011 (2023).https://doi.org/10.1088/1367-2630/acfd52

    Article ADS MathSciNet  Google Scholar 

  23. https://pypi.org/project/qiskit/

  24. Fowler, A.G., Devitt, S.J., Hollenberg, L.C.L.: Implementation of Shor’s algorithm on a linear nearest neighbour qubit array. Quantum Inf. Comput.4(4), 237–251 (2004).https://doi.org/10.26421/QIC4.4-1

    Article MathSciNet  Google Scholar 

  25. Maslov, D.: Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures. Phys. Rev. A76(5), 052310 (2007).https://doi.org/10.1103/PhysRevA.76.052310

    Article ADS  Google Scholar 

  26. Park, B., Ahn, D.: Reducing CNOT count in quantum Fourier transform for the linear nearest-neighbor architecture. Sci. Rep.13, 8638 (2023).https://doi.org/10.1038/s41598-023-35625-3

    Article ADS  Google Scholar 

  27. Cleve, R., Watrous, J.: Fast parallel circuits for the quantum Fourier transform. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, pp. 526–536. CA, USA (2000).https://doi.org/10.1109/SFCS.2000.892140

  28. Jun, Y.-M., Choi, I.-C.: Optimal multi-bit Toffoli gate synthesis. IEEE Access11, 27342–27351 (2023).https://doi.org/10.1109/ACCESS.2023.3243798

    Article  Google Scholar 

  29. https://github.com/qclib/qclib

Download references

Acknowledgements

This work was financially supported by the Ministry of Science, Technological Development and Innovation of the Republic of Serbia under contract number: 451-03-65/2024-03/200103.

Funding

This work was financially supported by the Ministry of Science, Technological Development and Innovation of the Republic of Serbia under contract number: 451-03-65/2024-03/200103.

Author information

Authors and Affiliations

  1. The Department of Microelectronics and Technical Physics, School of Electrical Engineering - University of Belgrade, Bulevar kralja Aleksandra 73, Belgrade, P.O. Box 35–54, Serbia

    Vladimir V. Arsoski

Authors
  1. Vladimir V. Arsoski

Contributions

The author, Vladimir V. Arsoski, contributed to the conception and design of this work. He agrees to be accountable for all aspects of the work in ensuring that questions related to the accuracy or integrity of any part of the work are appropriately investigated and resolved.

Corresponding author

Correspondence toVladimir V. Arsoski.

Ethics declarations

Conflict of interest

The author has no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The unitary operator implemented using the QFT-based MCX

The unitary operator implemented using the QFT-based MCX

We will show that the unitary operator implemented using our approach is the same as one implemented by standard MCX. The circuit implements

$$\begin{aligned} \text {MCX}_n=(I_{2\times 2}\otimes (\text {IQFT}_{n_c} P_{+1,n_c} \text {QFT}_{n_c}))^\dagger \cdot \text {IQFT}_{n} P_{+1,n} \text {QFT}_n, \end{aligned}$$
(A1)

where the number of qubits\(n=n_c+1\), and\(N=2^n\). Here,

$$\begin{aligned} \left( \text {IQFT}_{n_c} P_{+1,n_c} \text {QFT}_{n_c}\right) ^\dagger = \text {QFT}_{n_c}^\dagger P_{+1,n_c}^\dagger \text {IQFT}_{n_c}^\dagger = \text {IQFT}_{n_c} P_{-1,n_c} \text {QFT}_{n_c} , \end{aligned}$$
(A2)

where\(\text {QFT}_{n_c}^\dagger =\text {IQFT}_{n_c}\) (\(\text {IQFT}_{n_c}^\dagger =\text {QFT}_{n_c}\)), and\(P_{+1,n_c}^\dagger =P_{-1,n_c}\).

At first, we manipulated the unitary matrix representation of the QFT, IQFT, and P for\(n=3\) and\(n=4\) and multiplied matrices according to Eq. A1 to show it correct in these cases. Using inductive reasoning, results were generalized for an arbitraryn. That was very tedious and uneasy to prove. While doing it, we noticed that the result for the\(\text {IQFT}_{n} P_{+1,n} \text {QFT}_n\) was evident:

(A3)

since it performsN-element circular shifts to the left in the computationalZ-basis. Similarly,

$$\begin{aligned} \text {IQFT}_{n_c} P_{-1,n_c} \text {QFT}_{n_c}= \begin{bmatrix} \begin{array}{c|c} 0 & I_{\left( \frac{N}{2}-1\right) \times \left( \frac{N}{2}-1\right) } \\ \hline 1 & \overbrace{0\cdots \cdots \cdots 0}^{\frac{N}{2}-1} \end{array} \end{bmatrix} \end{aligned}$$
(A4)

executes circular shifts to the right. Substituting Eqs. (A3) and (A4) into Eq. (A1), we obtain

$$\begin{aligned} \text {MCX}_n=&\begin{bmatrix} \begin{array}{c|c|c|c} I_{\left( \frac{N}{2}-1\right) \times \left( \frac{N}{2}-1\right) } & 0_{\left( \frac{N}{2}-1\right) \times 1} & 0_{\left( \frac{N}{2}-1\right) \times \left( \frac{N}{2}-1\right) } & 0_{\left( \frac{N}{2}-1\right) \times 1} \\ \hline 0\,0\,0\,0\cdots 0\,0\,0\,0 & 0 & 0\,0\,0\,0\cdots 0\,0\,0\,0 & 1\\ \hline 0_{\left( \frac{N}{2}-1\right) \times \left( \frac{N}{2}-1\right) } & 0_{\left( \frac{N}{2}-1\right) \times 1} & I_{\left( \frac{N}{2}-1\right) \times \left( \frac{N}{2}-1\right) } & 0_{\left( \frac{N}{2}-1\right) \times 1} \\ \hline 0\,0\,0\,0\cdots 0\,0\,0\,0 & 1 & 0\,0\,0\,0\cdots 0\,0\,0\,0 & 0 \end{array} \end{bmatrix}\nonumber \\ =&C_1C_2\cdots C_{n-2}C_{n-1}-X_n=C^{n_c}-X_n. \end{aligned}$$
(A5)

Using the reversed qubits ordering, one may find familiar notation

$$\begin{aligned} \text {MCX}_n^{\textrm{rev}}= \begin{bmatrix} \begin{array}{c|c} I_{(N-2)\times (N-2)} & 0_{(N-2)\times 2} \\ \hline 0_{2\times (N-2)} & X_{2\times 2} \end{array} \end{bmatrix}, \end{aligned}$$
(A6)

where\(X_{2\times 2}\) is the Pauli-X matrix

$$\begin{aligned} X_{2\times 2}= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} . \end{aligned}$$
(A7)

The gates schematics, truth tables, and permutation matrices for different qubits ordering in the 3-qubit case, which is the Toffoli gate, are given in Fig. 8.

Fig. 8
figure 8

The Toffoli gate, truth table, and permutation matrix when the target qubit isa the most significant andb the least significant

Based on quantum arithmetics, even one that is not the QFT-based, many complex gates can be very efficiently implemented.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp