Skip to main content
Top
Published in: Quantum Information Processing 2/2024

01-02-2024

An efficient quantum algorithm for preparation of uniform quantum superposition states

Authors: Alok Shukla, Prakash Vedula

Published in: Quantum Information Processing | Issue 2/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Quantum state preparation involving a uniform superposition over a non-empty subset of n-qubit computational basis states is an important and challenging step in many quantum computation algorithms and applications. In this work, we address the problem of preparation of a uniform superposition state of the form \(\left| {\Psi }\right\rangle = \frac{1}{\sqrt{M}}\sum _{j = 0}^{M - 1} \left| {j}\right\rangle \), where M denotes the number of distinct states in the superposition state and \(2 \le M \le 2^n\). We show that the superposition state \(\left| {\Psi }\right\rangle \) can be efficiently prepared, using a deterministic approach, with a gate complexity and circuit depth of only \(O(\log _2~M)\) for all M. This demonstrates an exponential reduction in gate complexity in comparison with other existing deterministic approaches in the literature for the general case of this problem. Another advantage of the proposed approach is that it requires only \(n=\lceil \log _2~M\rceil \) qubits. Furthermore, neither ancilla qubits nor any quantum gates with multiple controls are needed in our approach for creating the uniform superposition state \(\left| {\Psi }\right\rangle \). It is also shown that a broad class of nonuniform superposition states that involve a mixture of uniform superposition states can also be efficiently created with the same circuit configuration that is used for creating the uniform superposition state \(\left| {\Psi }\right\rangle \) described earlier, but with modified parameters.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Literature
1.
go back to reference Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
2.
go back to reference Wittek, P.: Quantum Machine Learning: What Quantum Computing Means to Data Mining. Academic Press, London (2014) Wittek, P.: Quantum Machine Learning: What Quantum Computing Means to Data Mining. Academic Press, London (2014)
3.
go back to reference Kieferová, M., Scherer, A., Berry, D.W.: Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series. Phys. Rev. A 99(4), 042314 (2019)ADSCrossRef Kieferová, M., Scherer, A., Berry, D.W.: Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series. Phys. Rev. A 99(4), 042314 (2019)ADSCrossRef
5.
go back to reference Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett. 114(9), 090502 (2015)ADSCrossRefPubMed Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett. 114(9), 090502 (2015)ADSCrossRefPubMed
6.
go back to reference 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)MathSciNetCrossRef 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)MathSciNetCrossRef
7.
8.
9.
go back to reference Shukla, A., Vedula, P.: A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations. Appl. Math. Comput. 442, 127708 (2023)MathSciNet Shukla, A., Vedula, P.: A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations. Appl. Math. Comput. 442, 127708 (2023)MathSciNet
10.
go back to reference Shukla, A., Vedula, P.: A hybrid classical-quantum algorithm for digital image processing. Quantum Inf. Process. 22(3), 19 (2022)MathSciNet Shukla, A., Vedula, P.: A hybrid classical-quantum algorithm for digital image processing. Quantum Inf. Process. 22(3), 19 (2022)MathSciNet
11.
go back to reference 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)CrossRef 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)CrossRef
12.
go back to reference Plesch, M., Brukner, Č: Quantum-state preparation with universal gate decompositions. Phys. Rev. A 83(3), 032302 (2011)ADSCrossRef Plesch, M., Brukner, Č: Quantum-state preparation with universal gate decompositions. Phys. Rev. A 83(3), 032302 (2011)ADSCrossRef
14.
go back to reference Möttönen, 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 Möttönen, 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
15.
go back to reference 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)ADSMathSciNetCrossRef 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)ADSMathSciNetCrossRef
16.
go back to reference Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp. 11–20 (1993) Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp. 11–20 (1993)
17.
go back to reference Shukla, A., Vedula, P.: A generalization of Bernstein–Vazirani algorithm with multiple secret keys and a probabilistic oracle. Quantum Inf. Process. 22(244), 18 (2023)MathSciNet Shukla, A., Vedula, P.: A generalization of Bernstein–Vazirani algorithm with multiple secret keys and a probabilistic oracle. Quantum Inf. Process. 22(244), 18 (2023)MathSciNet
18.
go back to reference Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325 (1997)ADSCrossRef Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325 (1997)ADSCrossRef
19.
21.
go back to reference Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)ADSMathSciNetCrossRef Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)ADSMathSciNetCrossRef
22.
go back to reference Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation (2002) Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation (2002)
23.
go back to reference Ben-Or, M., Hassidim, A.: Fast quantum Byzantine agreement. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 481–485 (2005) Ben-Or, M., Hassidim, A.: Fast quantum Byzantine agreement. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 481–485 (2005)
24.
go back to reference Gleinig, N., Hoefler, T.: An efficient algorithm for sparse quantum state preparation. In: 2021 58th ACM/IEEE Design Automation Conference (DAC). IEEE, pp. 433–438 (2021) Gleinig, N., Hoefler, T.: An efficient algorithm for sparse quantum state preparation. In: 2021 58th ACM/IEEE Design Automation Conference (DAC). IEEE, pp. 433–438 (2021)
25.
go back to reference Mozafari, F., Riener, H., Soeken, M., De Micheli, G.: Efficient Boolean methods for preparing uniform quantum states. IEEE Trans. Quantum Eng. 2, 1–12 (2021)CrossRef Mozafari, F., Riener, H., Soeken, M., De Micheli, G.: Efficient Boolean methods for preparing uniform quantum states. IEEE Trans. Quantum Eng. 2, 1–12 (2021)CrossRef
26.
go back to reference Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023) Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023)
27.
go back to reference Sanders, Y.R., Berry, D.W., Costa, P.C.S., Tessler, L.W., Wiebe, N., Gidney, C., Neven, H., Babbush, R.: Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum 1(2), 020312 (2020)CrossRef Sanders, Y.R., Berry, D.W., Costa, P.C.S., Tessler, L.W., Wiebe, N., Gidney, C., Neven, H., Babbush, R.: Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum 1(2), 020312 (2020)CrossRef
28.
go back to reference Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4), 041015 (2018) Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4), 041015 (2018)
29.
go back to reference Fischer, L.E., Chiesa, A., Tacchino, F., Egger, D.J., Carretta, S., Tavernelli, I.: Universal qudit gate synthesis for transmons. PRX Quantum 4(3), 030327 (2023)ADSCrossRef Fischer, L.E., Chiesa, A., Tacchino, F., Egger, D.J., Carretta, S., Tavernelli, I.: Universal qudit gate synthesis for transmons. PRX Quantum 4(3), 030327 (2023)ADSCrossRef
30.
go back to reference Hua, F., Wang, M., Li, G., Peng, B., Liu, C., Zheng, M., Stein, S., Ding, Y., Zhang, E.Z., Humble, T.S., et al.: QASMTrans: A QASM based Quantum Transpiler Framework for NISQ Devices. arXiv preprint arXiv:2308.07581 (2023) Hua, F., Wang, M., Li, G., Peng, B., Liu, C., Zheng, M., Stein, S., Ding, Y., Zhang, E.Z., Humble, T.S., et al.: QASMTrans: A QASM based Quantum Transpiler Framework for NISQ Devices. arXiv preprint arXiv:​2308.​07581 (2023)
31.
go back to reference Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for NISQ-era quantum devices. In: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1001–1014 (2019) Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for NISQ-era quantum devices. In: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1001–1014 (2019)
32.
go back to reference Younis, E., Iancu, C.: Quantum circuit optimization and transpilation via parameterized circuit instantiation. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, pp. 465–475 (2022) Younis, E., Iancu, C.: Quantum circuit optimization and transpilation via parameterized circuit instantiation. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, pp. 465–475 (2022)
33.
go back to reference Weaver, J.L., Harkins, F.J.: Qiskit Pocket Guide. O’Reilly Media, Sebastopol (2022) Weaver, J.L., Harkins, F.J.: Qiskit Pocket Guide. O’Reilly Media, Sebastopol (2022)
Metadata
Title
An efficient quantum algorithm for preparation of uniform quantum superposition states
Authors
Alok Shukla
Prakash Vedula
Publication date
01-02-2024
Publisher
Springer US
Published in
Quantum Information Processing / Issue 2/2024
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-024-04258-4

Other articles of this Issue 2/2024

Quantum Information Processing 2/2024 Go to the issue