A divide-and-conquer algorithm for quantum state preparation
Open accessThe DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with exponential time advantage using a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
LeCun, Y., Bengio, Y., & Hinton, G. (2015) · Nature · doi:10.1038/nature14539 · Cited by 84,126
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
Santos, A. G., da Rocha, G. O., & de Andrade, J. B. (2019) · Scientific Reports · doi:10.1038/s41598-018-37186-2 · Cited by 8,495
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
A single quantum cannot be cloned
Wootters, W. K., & Zurek, W. H. (1982) · Nature · doi:10.1038/299802a0 · Cited by 5,406
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
PennyLane: Automatic differentiation of hybrid quantum-classical computations
Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., Ahmed, S., Ajith, V., Alam, M. S., Alonso-Linaje, G., AkashNarayanan, B., Asadi, A., et al. (2018) · arXiv · doi:10.48550/arxiv.1811.04968 · Cited by 732
Aaronson, S. (2015) · Nature Physics · doi:10.1038/nphys3272 · Cited by 567
Hoare, C. A. R. (1961) · Communications of the ACM · doi:10.1145/366622.366644 · Cited by 537
Quantum Entanglement in Deep Learning Architectures
Levine, Y., Sharir, O., Cohen, N., & Shashua, A. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.065301 · Cited by 206
Research works printed but not linked: 13
- Dong, Y. et al. Stochastic quantization for learning accurate low-bit deep neural networks. Int. J. Comput. Vis. 127, 1629–1642 (2019). · DOI
- Yang, C.-C. & Cong, G. Accelerating data loading in deep neural network training. In 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC), 235–245 (IEEE, 2019). · DOI
- Hughes, R. J., James, D. F., Knill, E. H., Laflamme, R. & Petschek, A. G. Decoherence bounds on quantum computation with trapped ions. Phys. Rev. Lett. 77, 3240 (1996). · DOI
- Shende, V. V., Bullock, S. S. & Markov, I. L. Synthesis of quantum-logic circuits. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 25, 1000–1010 (2006). · DOI · Paper page
- Iten, R., Colbeck, R., Kukuljan, I., Home, J. & Christandl, M. Quantum circuits for isometries. Phys. Rev. A 93, 032318 (2016). · DOI · Paper page
- 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, 083024. https://doi.org/10.1088/1367-2630/ab35fb (2019). · DOI
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. Introduction to algorithms (MIT press, 2009).
- Gentleman, W. M. & Sande, G. Fast fourier transforms: for fun and profit. In Proceedings of the November 7-10, 1966, fall joint computer conference, 563–578 (1966). · DOI · Paper page
- Mottonen, M., Vartiainen, J. J., Bergholm, V. & Salomaa, M. M. Transformation of quantum states using uniformly controlled rotations. Quant. Inf. Comput. 5, 467–473 (2005).
- Grant, E. et al. Hierarchical quantum classifiers. npj Quant. Inf.4, 65. https://doi.org/10.1038/s41534-018-0116-9 (2018). · DOI · Paper page
- Cohen, N. & Shashua, A. Convolutional rectifier networks as generalized tensor decompositions. Int. Conf. Mach. Learn. 955–963, (2016).
- Rossi, R. A. & Ahmed, N. K. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, 4292–4293 (AAAI Press, 2015). · DOI · Paper page
- Demšar, J. Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006).
Cited by
Quantum convolutional neural network for classical data classification
Hur, T., Kim, L., & Park, D. K. (2022) · Quantum Machine Intelligence · doi:10.1007/s42484-021-00061-x · Cited by 378
Self-citationVariational Quantum Classifier for Binary Classification: Real vs Synthetic Dataset
Maheshwari, D., Sierra-Sosa, D., & Garcia-Zapirain, B. (2022) · IEEE Access · doi:10.1109/access.2021.3139323 · Cited by 108
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
“see [147]), requiring on the order of log2N qubits.”
BackgroundTensorFlow Quantum: Impacts of Quantum State Preparation on Quantum Machine Learning Performance
Sierra-Sosa, D., Telahun, M., & Elmaghraby, A. (2020) · IEEE Access · doi:10.1109/access.2020.3040798 · Cited by 46
“Design and Implementation of Efficient Quantum Support Vector Machine,”
Mafu, M., & Senekane, M. (2021) · 2021 International Conference on Electrical, Computer and Energy Technologies (ICECET) · doi:10.1109/icecet52533.2021.9698509 · Cited by 25
Metadata
- Authors
- Araujo, I. F., Park, D. K., Petruccione, F., & da Silva, A. J.
- Venue
- Scientific Reports
- Published
- 2021-03-18
- Volume
- 11
- Issue
- 1
- Pages
- 6329-6329
- ISSN
- 2045-2322 (ISSN-L)
- OpenAlex
- W3047378565
- Cited by
- 166
- References
- 12
- FWCI
- 10.59
- Type
- journal article
- Language
- en
- Open access
- gold
- Licence
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A divide-and-conquer algorithm for quantum state preparation. https://app.cochat.ai/papers/10.1038/s41598-021-85474-1
- The paper
- Araujo, I. F., Park, D. K., Petruccione, F., & da Silva, A. J. (2021). A divide-and-conquer algorithm for quantum state preparation. Scientific Reports. https://doi.org/10.1038/s41598-021-85474-1
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.