Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Configurable sublinear circuits for quantum state preparation

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

The theory of quantum algorithms promises unprecedented benefits of harnessing the laws of quantum mechanics for solving certain computational problems. A prerequisite for applying quantum algorithms to a wide range of real-world problems is loading classical data to a quantum state. Several circuit-based methods have been proposed for encoding classical data as probability amplitudes of a quantum state. However, in these methods, either quantum circuit depth or width must grow linearly with the data size, nullifying the advantage of representing exponentially many classical data in a quantum state. In this paper, we present a configurable bidirectional procedure that addresses this problem by tailoring the resource trade-off between quantum circuit width and depth. In particular, we show a configuration that encodes an N-dimensional classical data using a quantum circuit whose width and depth both grow sublinearly with N. We demonstrate proof-of-principle implementations on five quantum computers accessed through the IBM and IonQ quantum cloud services.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability statement

The sites https://github.com/qclib/qclib-papers and https://github.com/qclib/qclib contain all the data and the software generated during the current study.

References

  1. Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21(6–7), 467–488 (1982)

    MathSciNet  Google Scholar 

  2. Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A Math. Phys. Sci. 439(1907), 553–558 (1992)

    ADS  MathSciNet  MATH  Google Scholar 

  3. 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, pp. 212–219. Association for Computing Machinery, Philadelphia (1996)

  4. Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)

    MathSciNet  MATH  Google Scholar 

  5. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)

    ADS  MathSciNet  MATH  Google Scholar 

  6. Aaronson, S.: Read the fine print. Nat. Phys. 11(4), 291–293 (2015)

    Google Scholar 

  7. Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549(7671), 195–202 (2017)

    ADS  Google Scholar 

  8. Leymann, F., Barzen, J.: The bitter truth about gate-based quantum algorithms in the NISQ era. Quantum Sci. Technol. 5(4), 044007 (2020)

    ADS  Google Scholar 

  9. Tang, E.: Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions. Phys. Rev. Lett. 127, 060503 (2021)

    ADS  MathSciNet  Google Scholar 

  10. Shende, V.V., Bullock, S.S., Markov, I.L.: Synthesis of quantum-logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(6), 1000–1010 (2006)

    Google Scholar 

  11. Hogg, T., Huberman, B.A., Williams, C.P.: Phase transitions and the search problem. Artif. Intell. 81(1), 1–15 (1996) (Frontiers in problem solving: phase transitions and complexity)

  12. Terhal, B.M., Smolin, J.A.: Single quantum querying of a database. Phys. Rev. A 58(3), 1822–1826 (1998)

    ADS  MathSciNet  Google Scholar 

  13. Zidan, M., Eleuch, H., Abdel-Aty, M.: Non-classical computing problems: toward novel type of quantum computing problems. Results Phys. 21, 103536 (2021)

    Google Scholar 

  14. Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)

    ADS  MathSciNet  Google Scholar 

  15. Grover, L.K.: Synthesis of quantum superpositions by quantum computation. Phys. Rev. Lett. 85(6), 1334–1337 (2000)

    ADS  Google Scholar 

  16. Sanders, Y.R., Low, G.H., Scherer, A., Berry, D.W.: Black-box quantum state preparation without arithmetic. Phys. Rev. Lett. 122, 020502 (2019)

    ADS  Google Scholar 

  17. Wang, S., Wang, Z., Cui, G., Shi, S., Shang, R., Fan, L., Li, W., Wei, Z., Gu, Y.: Fast black-box quantum state preparation based on linear combination of unitaries. Quantum Inf. Process. 20(8), 270 (2021)

    ADS  MathSciNet  MATH  Google Scholar 

  18. Trugenberger, C.A.: Probabilistic quantum memories. Phys. Rev. Lett. 87(6), 067901 (2001)

    ADS  Google Scholar 

  19. Ventura, D., Martinez, T.: Quantum associative memory. Inf. Sci. 124(1), 273–296 (2000)

    MathSciNet  Google Scholar 

  20. Trugenberger, C.A.: Quantum pattern recognition. Quantum Inf. Process. 1(6), 471–493 (2002)

    MathSciNet  Google Scholar 

  21. Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100, 160501 (2008)

    ADS  MathSciNet  MATH  Google Scholar 

  22. Silva, A., de Oliveira, W., Ludermir, T.: A weightless neural node based on a probabilistic quantum memory. In: 2010 Eleventh Brazilian Symposium on Neural Networks, pp. 259–264. IEEE, Sao Paulo (2010). ISSN: 2375-0235

  23. de Paula Neto, F.M., da Silva, A.J., de Oliveira, W.R., Ludermir, T.B.: Quantum probabilistic associative memory architecture. Neurocomputing 351, 101–110 (2019)

    Google Scholar 

  24. Park, D.K., Petruccione, F., Rhee, J.-K.K.: Circuit-based quantum random access memory for classical data. Sci. Rep. 9(1), 3949 (2019)

    ADS  Google Scholar 

  25. Zidan, M., Abdel-Aty, A.-H., Khalil, A., Abdel-Aty, M., Eleuch, H.: A novel efficient quantum random access memory. IEEE Access 9, 151775–151780 (2021)

    Google Scholar 

  26. Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning (2013). arXiv:1307.0411 [quant-ph]

  27. Stoudenmire, E., Schwab, D.J.: Supervised learning with tensor networks. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 29, p. 9. Curran Associates, Inc., Centre Convencions Internacional Barcelona, Barcelona (2016)

    Google Scholar 

  28. Schuld, M., Fingerhuth, M., Petruccione, F.: Implementing a distance-based classifier with a quantum interference circuit. EPL (Europhys. Lett.) 119(6), 60002 (2017)

    ADS  Google Scholar 

  29. Schuld, M., Petruccione, F.: Supervised Learning with Quantum Computers, 1st ed. 2018 edn. Quantum Science and Technology. Springer, Cham (2018)

  30. Benedetti, M., Lloyd, E., Sack, S., Fiorentini, M.: Parameterized quantum circuits as machine learning models. Quantum Sci. Technol. 4, 043001 (2019)

    ADS  Google Scholar 

  31. Levine, Y., Sharir, O., Cohen, N., Shashua, A.: Quantum entanglement in deep learning architectures. Phys. Rev. Lett. 122(6), 065301 (2019)

    ADS  MathSciNet  Google Scholar 

  32. Blank, C., Park, D.K., Rhee, J.-K.K., Petruccione, F.: Quantum classifier with tailored quantum kernel. npj Quantum Inf. 6(1), 1–7 (2020)

    ADS  Google Scholar 

  33. Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nat. Phys. 10(9), 631–633 (2014)

    Google Scholar 

  34. Childs, A.M., Kothari, R., Somma, R.D.: Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput. 46(6), 1920–1950 (2017)

    MathSciNet  MATH  Google Scholar 

  35. Wossnig, L., Zhao, Z., Prakash, A.: Quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120, 050502 (2018)

    ADS  MathSciNet  Google Scholar 

  36. Rebentrost, P., Steffens, A., Marvian, I., Lloyd, S.: Quantum singular-value decomposition of nonsparse low-rank matrices. Phys. Rev. A 97(1), 012327 (2018)

    ADS  MathSciNet  Google Scholar 

  37. Mitchell, T.M.: Machine Learning. McGraw-Hill Series in Computer Science, Nachdr McGraw-Hill, New York (2013)

    Google Scholar 

  38. Ventura, D., Martinez, T.: Initializing the amplitude distribution of a quantum state. Found. Phys. Lett. 12(6), 547–559 (1999)

    MathSciNet  Google Scholar 

  39. Long, G.-L., Sun, Y.: Efficient scheme for initializing a quantum register with an arbitrary superposed state. Phys. Rev. A 64(1), 014303 (2001)

    ADS  Google Scholar 

  40. Mottonen, M., Vartiainen, J.J., Bergholm, V., Salomaa, M.M.: Transformation of quantum states using uniformly controlled rotations. Quantum Inf. Comput. 5(6), 467–473 (2005)

    MathSciNet  MATH  Google Scholar 

  41. Plesch, M., Brukner, C.: Quantum-state preparation with universal gate decompositions. Phys. Rev. A 83(3), 032302 (2011)

    ADS  Google Scholar 

  42. Cortese, J.A., Braje, T.M.: Loading classical data into a quantum computer (2018)

  43. Araujo, I.F., Park, D.K., Petruccione, F., da Silva, A.J.: A divide-and-conquer algorithm for quantum state preparation. Sci. Rep. 11(1), 6329 (2021)

    Google Scholar 

  44. Park, D.K., Sinayskiy, I., Fingerhuth, M., Petruccione, F., Rhee, J.-K.K.: Parallel quantum trajectories via forking for sampling without redundancy. New J. Phys. 21(8), 083024 (2019)

    ADS  Google Scholar 

  45. Low, G.H., Kliuchnikov, V., Schaeffer, L.: Trading T-gates for dirty qubits in state preparation and unitary synthesis (2018)

  46. Zoufal, C., Lucchi, A., Woerner, S.: Quantum generative adversarial networks for learning and loading random distributions. npj Quantum Inf. 5(1), 1–9 (2019)

    Google Scholar 

  47. Kuzmin, V.V., Silvi, P.: Variational quantum state preparation via quantum data buses. Quantum 4, 290 (2020)

    Google Scholar 

  48. IBM: IBM’s roadmap for scaling quantum technology (2020). https://research.ibm.com/blog/ibm-quantum-roadmap

  49. Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018)

    Google Scholar 

  50. Xin, T., Wei, S., Cui, J., Xiao, J., Arrazola, I.N., Lamata, L., Kong, X., Lu, D., Solano, E., Long, G.: Quantum algorithm for solving linear differential equations: theory and experiment. Phys. Rev. A 101, 032307 (2020)

    ADS  MathSciNet  Google Scholar 

  51. Aleksandrowicz, G., et al.: Qiskit: an open-source framework for quantum computing (2021)

  52. Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., Alam, M.S., Ahmed, S., Arrazola, J.M., Blank, C., Delgado, A., Jahangiri, S., McKiernan, K., Meyer, J.J., Niu, Z., Száva, A., Killoran, N.: PennyLane: automatic differentiation of hybrid quantum-classical computations (2020)

  53. Schuld, M., Petruccione, F.: Machine Learning with Quantum Computers. Quantum Science and Technology. Springer, Cham (2021)

    MATH  Google Scholar 

  54. Bergholm, V., Vartiainen, J.J., Möttönen, M., Salomaa, M.M.: Quantum circuits with uniformly controlled one-qubit gates. Phys. Rev. A 71(5), 052330 (2005)

    ADS  MATH  Google Scholar 

Download references

Acknowledgements

This work is based upon research supported by CNPq (Grant Nos. 308730/2018-6, 306727/2017-0, 409415/2018-9 and 421849/2016-9), CAPES – Finance Code 001, FACEPE (Grant No. IBPG-0834\(-\)1.03/19), National Research Foundation of Korea (Grant Nos. 2019M3E4A1079666, 2021M3H3A1038085 and 2022M3E4A1074591), the South African Research Chair Initiative, Grant No. 64812, of the Department of Science and Innovation and the National Research Foundation (NRF). Support of the NICIS (National Integrated Cyberinfrastructure System) e-research grant QICSA is kindly acknowledged. We acknowledge the use of IBM Quantum services for this work. The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Quantum team.

Author information

Authors and Affiliations

  1. Centro de Informática, Universidade Federal de Pernambuco, Recife, Pernambuco, 50740-560, Brazil

    Israel F. Araujo, Teresa B. Ludermir & Adenilton J. da Silva

  2. Department of Applied Statistics, Yonsei University, Seoul, 03722, Republic of Korea

    Israel F. Araujo & Daniel K. Park

  3. Department of Statistics and Data Science, Yonsei University, Seoul, 03722, Republic of Korea

    Israel F. Araujo & Daniel K. Park

  4. Departamento de Estatística e Informática, Universidade Federal Rural de Pernambuco, Recife, Pernambuco, Brazil

    Wilson R. Oliveira

  5. School of Data Science and Computational Thinking, Stellenbosch University, Stellenbosch, 7600, South Africa

    Francesco Petruccione

  6. National Institute for Theoretical and Computational Sciences (NITheCS), Stellenbosch, 7600, South Africa

    Francesco Petruccione

  7. Quantum Research Group, University of KwaZulu-Natal, Durban, 4001, South Africa

    Francesco Petruccione

Authors
  1. Israel F. Araujo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel K. Park
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Teresa B. Ludermir
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wilson R. Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Francesco Petruccione
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Adenilton J. da Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Israel F. Araujo.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

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

Appendices

A Numerical example

The following case study illustrates how the BDSP algorithm (Algorithm 5) encodes the example input vector \( {\textbf{x}} = \left( 0, \sqrt{2/8}e^{-i\pi /7}, \sqrt{3/8}e^{-i\pi /3},0,0,0,\sqrt{3/8},0 \right) \).

Fig. 7
figure 7

Example of state and angle decomposition trees. a State decomposition tree generated by Algorithm 1 for the example input vector \({\textbf{x}}\) (dashed nodes). b Angle tree generated by Algorithm 2 for the state tree of Fig. 7a

Full size image

Initially (step 1 of Algorithm 5), Algorithm 1 is employed, as detailed below, to produce the state decomposition tree (Fig. 7b).

Iteration #1 (\(n=3; k=1; i=1\dots 4\)):

$$\begin{aligned} \eta _{1,1}&=\sqrt{\vert x_0\vert ^2+\vert x_1\vert ^2}=\sqrt{2/8}&\Omega _{1,1}&=(\omega _0+\omega _1)=-\pi /7 \\ \eta _{2,1}&=\sqrt{\vert x_2\vert ^2+\vert x_3\vert ^2}=\sqrt{3/8}&\Omega _{2,1}&=(\omega _2+\omega _3)=-\pi /3 \\ \eta _{3,1}&=\sqrt{\vert x_4\vert ^2+\vert x_5\vert ^2}=0&\Omega _{3,1}&=(\omega _4+\omega _5)=0 \\ \eta _{4,1}&=\sqrt{\vert x_6\vert ^2+\vert x_7\vert ^2}=\sqrt{3/8}&\Omega _{4,1}&=(\omega _6+\omega _7)=0 \end{aligned}$$

Iteration #2 (\(n=3; k=2; i=1\dots 2\)):

$$\begin{aligned} \eta _{1,2}&=\sqrt{\vert x_0\vert ^2+\vert x_1\vert ^2+\vert x_2\vert ^2+\vert x_3\vert ^2}=\sqrt{\eta _{1,1}^2+\eta _{2,1}^2}=\sqrt{5/8} \\ \eta _{2,2}&=\sqrt{\vert x_4\vert ^2+\vert x_5\vert ^2+\vert x_6\vert ^2+\vert x_7\vert ^2}=\sqrt{\eta _{3,1}^2+\eta _{4,1}^2}=\sqrt{3/8} \\ \Omega _{1,2}&=(\omega _0+\omega _1+\omega _2+\omega _3)/2=(\Omega _{1,1}+\Omega _{2,1})/2=-5\pi /21 \\ \Omega _{2,2}&=(\omega _4+\omega _5+\omega _6+\omega _7)/2=(\Omega _{3,1}+\Omega _{4,1})/2=0 \end{aligned}$$

Iteration #3 (\(n=3; k=3; i=1\)):

$$\begin{aligned} \eta _{1,3}&=\sqrt{\vert x_0\vert ^2+\vert x_1\vert ^2+\vert x_2\vert ^2+\vert x_3\vert ^2+\vert x_4\vert ^2+\vert x_5\vert ^2+\vert x_6\vert ^2+\vert x_7\vert ^2} \\ {}&=\sqrt{\eta _{1,2}^2+\eta _{2,2}^2}=1 \\ \Omega _{1,3}&=(\omega _0+\omega _1+\omega _2+\omega _3+\omega _4+\omega _5+\omega _6+\omega _7)/4 \\ {}&=(\Omega _{1,2}+\Omega _{2,2})/2=-5\pi /42 \end{aligned}$$

Then (step 2 of Algorithm 5), Algorithm 2 uses the state tree data to generate the angle tree (Fig. 7b). The iterations of the procedure are detailed below.

Iteration #1 (\(n=3; v=3; j=1\)):

$$\begin{aligned} \beta _{1,3}&=\eta _{2,2}/\eta _{1,3}=\sqrt{3/8}&\alpha _{1,3}&=2\textrm{asin}(\beta _{1,3})=1.32 \\ \lambda _{1,3}&=\Omega _{2,2}-\Omega _{1,3}=5\pi /42 \end{aligned}$$

Iteration #2 (\(n=3; v=2; j=1\dots 2\)):

$$\begin{aligned} \beta _{1,2}&=\eta _{2,1}/\eta _{1,2}=\sqrt{3/5}&\alpha _{1,2}&=2\textrm{asin}(\beta _{1,2})=1.77 \\ \beta _{2,2}&=\eta _{4,1}/\eta _{2,2}=1&\alpha _{2,2}&=2\textrm{asin}(\beta _{2,2})=\pi \\ \lambda _{1,2}&=\Omega _{2,1}-\Omega _{1,2}=-2\pi /21 \\ \lambda _{2,2}&=\Omega _{4,1}-\Omega _{2,2}=0 \end{aligned}$$

Iteration #3 (\(n=3; v=1; j=1\dots 4, \eta _{i,0}=\vert x_{i-1}\vert , \Omega _{i,0}=2\omega _{i-1}\)):

$$\begin{aligned} \beta _{1,1}&=\eta _{2,0}/\eta _{1,1}=1&\alpha _{1,1}&=2\textrm{asin}(\beta _{1,1})=\pi \\ \beta _{2,1}&=\eta _{4,0}/\eta _{2,1}=0&\alpha _{2,1}&=2\textrm{asin}(\beta _{2,1})=0 \\ \beta _{3,1}&=\eta _{6,0}/\eta _{3,1}=0&\alpha _{3,1}&=2\textrm{asin}(\beta _{3,1})=0 \\ \beta _{4,1}&=\eta _{8,0}/\eta _{4,1}=0&\alpha _{4,1}&=2\textrm{asin}(\beta _{4,1})=0 \\ \lambda _{1,1}&=\Omega _{2,0}-\Omega _{1,1}=-\pi /7 \\ \lambda _{2,1}&=\Omega _{4,0}-\Omega _{2,1}=\pi /3 \\ \lambda _{3,1}&=\Omega _{6,0}-\Omega _{3,1}=0 \\ \lambda _{4,1}&=\Omega _{8,0}-\Omega _{4,1}=0 \end{aligned}$$

Setting the parameter \(s=2\) separates the bottom part of the angle tree into two sub-trees of height 2, and step 3 of Algorithm 5 creates a quantum circuit with \(n=(s+1)2^{n-2}-1=5\) qubits. Step 4 (named Stage 1) prepares \(2^{n-s}=2\) sub-states, \(|\psi \rangle _{1,3}\) and \(|\phi \rangle _{2,5}\), with 2 qubits each (the sub-state indexes indicate the circuit’s corresponding qubits) using amplitude encoding (see Eqs. (5) and (6) from Sect. 2.2 and Refs. [29, 40, 53, 54] for details on amplitude encoding) with sub-trees as input (Fig. 8).

Fig. 8
figure 8

Circuit generated by the top-down strategy (Algorithm 3) to prepare two 2-qubit sub-states for the example input vector \({\textbf{x}}\)

Full size image

Preparing sub-state \(|\psi \rangle _{1,3}\):

$$\begin{aligned} |\psi _2\rangle&= e^{-i\frac{\lambda _{1,2}}{2}}\sqrt{1-\vert \beta _{1,2}\vert ^2}|0\rangle _1 +e^{i\frac{\lambda _{1,2}}{2}}\beta _{1,2}|1\rangle _1 \end{aligned}$$
$$\begin{aligned} |\psi _{1}\rangle&= |0\rangle _1\vert 0\rangle {\psi _{2}}_1 \big ( e^{-i\frac{\lambda _{1,1}}{2}}\sqrt{1-\vert \beta _{1,1}\vert ^2}|0\rangle _3+e^{i\frac{\lambda _{1,1}}{2}}\beta _{1,1}|1\rangle _3 \big ) \\&\quad +|1\rangle _1\vert 1\rangle {\psi _{2}}_1 \big ( e^{-i\frac{\lambda _{2,1}}{2}}\sqrt{1-\vert \beta _{2,1}\vert ^2}|0\rangle _3+e^{i\frac{\lambda _{2,1}}{2}}\beta _{2,1}|1\rangle _3 \big ) \\&= e^{-i\frac{\lambda _{1,2}}{2}}\sqrt{1-\vert \beta _{1,2}\vert ^2} \big ( e^{-i\frac{\lambda _{1,1}}{2}}\sqrt{1-\vert \beta _{1,1}\vert ^2}|00\rangle _{1,3}+e^{i\frac{\lambda _{1,1}}{2}}\beta _{1,1}|01\rangle _{1,3} \big ) \\&\quad +e^{i\frac{\lambda _{1,2}}{2}}\beta _{1,2} \big ( e^{-i\frac{\lambda _{2,1}}{2}}\sqrt{1-\vert \beta _{2,1}\vert ^2}|10\rangle _{1,3}+e^{i\frac{\lambda _{2,1}}{2}}\beta _{2,1}|11\rangle _{1,3} \big ) \end{aligned}$$
$$\begin{aligned} |\psi \rangle _{1,3} = e^{-i\frac{\pi }{42}}\sqrt{\frac{2}{5}}|01\rangle _{1,3}+e^{-i\frac{9\pi }{42}}\sqrt{\frac{3}{5}}|10\rangle _{1,3} \end{aligned}$$
(A1)

Preparing sub-state \(|\phi \rangle _{2,5}\):

$$\begin{aligned} |\phi _2\rangle&= e^{-i\frac{\lambda _{2,2}}{2}}\sqrt{1-\vert \beta _{2,2}\vert ^2}|0\rangle _2+e^{i\frac{\lambda _{2,2}}{2}}\beta _{2,2}|1\rangle _2 \end{aligned}$$
$$\begin{aligned} |\phi _{1}\rangle +&= |0\rangle _2\vert 0\rangle {\phi _{2}}_2 \big ( e^{-i\frac{\lambda _{3,1}}{2}} \sqrt{1-\vert \beta _{3,1}\vert ^2}|0\rangle _5+e^{i\frac{\lambda _{3,1}}{2}}\beta _{3,1}|1\rangle _5 \big ) \\&\quad +|1\rangle _2\vert 1\rangle {\phi _{2}}_2 \big ( e^{-i\frac{\lambda _{4,1}}{2}} \sqrt{1-\vert \beta _{4,1}\vert ^2}|0\rangle _5+e^{i\frac{\lambda _{4,1}}{2}}\beta _{4,1}|1\rangle _5 \big ) \\&= e^{-i\frac{\lambda _{2,2}}{2}}\sqrt{1-\vert \beta _{2,2}\vert ^2} \big ( e^{-i\frac{\lambda _{3,1}}{2}}\sqrt{1-\vert \beta _{3,1}\vert ^2} |00\rangle _{2,5}+e^{i\frac{\lambda _{3,1}}{2}}\beta _{3,1}|01\rangle _{2,5} \big ) \\&\quad +e^{i\frac{\lambda _{2,2}}{2}}\beta _{2,2}\big ( e^{-i\frac{\lambda _{4,1}}{2}}\sqrt{1-\vert \beta _{4,1}\vert ^2}|10\rangle _{2,5}+e^{i\frac{\lambda _{4,1}}{2}}\beta _{4,1}|11\rangle _{2,5} \big ) \end{aligned}$$
$$\begin{aligned} |\phi \rangle _{2,5} = |10\rangle _{2,5} \end{aligned}$$
(A2)

Step 5 of Algorithm 5 (named Stage 2) uses the bottom-up approach (see Eq. (8) from Sect. 2.3 and Refs. [43, 53] for details on divide-and-conquer quantum state preparation) to combine the two states (Eqs. (A1) and (A2)) prepared in Step 4 (Stage 1) into the final state \(|\Psi \rangle \) using the remaining qubit (Fig. 9).

Preparing final state \(|\Psi \rangle \):

$$\begin{aligned} \begin{aligned} |\Psi \rangle&= e^{-i\frac{\lambda _{1,3}}{2}}\sqrt{1-\vert \beta _{1,3}\vert ^2}|0\rangle _0|\psi \rangle _{1,3}|\phi \rangle _{2,5} + e^{i\frac{\lambda _{1,3}}{2}}\beta _{1,3}|1\rangle _0|\phi \rangle _{1,3}|\psi \rangle _{2,5} \\&= e^{i\frac{5\pi }{84}}\left( e^{-i\frac{\pi }{7}}\sqrt{\frac{2}{8}}|001\rangle _{0,1,3} + e^{-i\frac{\pi }{3}}\sqrt{\frac{3}{8}}|010\rangle _{0,1,3} \right) |\phi \rangle _{2,5} \\&\quad + e^{i\frac{5\pi }{84}}\left( \sqrt{\frac{3}{8}}|110\rangle _{0,1,3} \right) |\psi \rangle _{2,5} \\&= e^{-i\frac{\pi }{7}}\sqrt{\frac{2}{8}}|001\rangle |\phi \rangle + e^{-i\frac{\pi }{3}}\sqrt{\frac{3}{8}}|010\rangle |\phi \rangle + \sqrt{\frac{3}{8}}|110\rangle |\psi \rangle \end{aligned} \end{aligned}$$
(A3)

The global phase \(e^{i\frac{5\pi }{84}}\) in Eq. (A3) can be easily calculated (\(e^{-i \sum _{j=0}^{N-1} \omega _j / N}\)) and eliminated, as prescribed in Ref. [40]. The indexes have been removed from Eq. (A3) last expression to improve readability.

Fig. 9
figure 9

Circuit generated by the bottom-up strategy (Algorithm 4) to combine two 2-qubit sub-states for the example input vector \({\textbf{x}}\)

Full size image

Figure 10 presents the complete circuit constructed by Algorithm 5 using the angle tree split at level \(s=2\), operating only multi-controlled rotations and CSWAP gates.

Fig. 10
figure 10

Complete circuit generated by the bidirectional strategy (Algorithm 5) for the example input vector \({\textbf{x}}\)

Full size image

B Pseudocode

Pseudocodes 1 to 5 express algorithms 1 to 5. Pseudocodes 1 and 2 construct the tree representations of the state preparation algorithms, namely the state tree and the angle tree, as described in Sect. 2.1. Pseudocodes 3 and 4, which algorithms are explained in Sects. 2.2 and 2.3, build quantum circuits using top-down and bottom-up approaches for encoding a complex input vector into the amplitudes of a quantum state. Pseudocode 5 employs pseudocodes 1 to 4 and expresses the bidirectional state preparation algorithm (Sect. 3, Algorithm 5).

Lines 5 and 6 of Pseudocode 5 indicate the two stages of the BDSP algorithm. Line 5 at function performs the first stage preparing the sub-states expected by the next stage, equivalent to what would be generated by bottom-up DCSP up to the tree split, but with the absence of ancilla due to the top-down approach. Line  6 at function performs the second stage, starting at level \(s+1\) with the sub-states initialized by the previous stage. Line 3 at function configures the recurrence so that at split level s it divides the angle tree into \(2^{n-s}\) (number of nodes at split level s) sub-trees of height s, loading all these sub-trees concurrently using the top-down strategy. Lines 11 and 12 of function initialize \(2^{n-s}-1\) qubits exclusive to the second stage with values \(R_y(\alpha _{j,v})\) and \(R_z(\lambda _{j,v})\). Then, function combine the states through CSWAP gates controlled by the nodes above level s. With the tree described in Fig. 4a and \(s=2\), the bidirectional procedure (Pseudocode 5) generates the circuit presented in Fig. 4c.

figure k
figure l
figure m
figure n
figure o

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

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Araujo, I.F., Park, D.K., Ludermir, T.B. et al. Configurable sublinear circuits for quantum state preparation. Quantum Inf Process 22, 123 (2023). https://doi.org/10.1007/s11128-023-03869-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-023-03869-7

Keywords

Search

Navigation