Computationally Efficient Quantum Expectation with Extended Bell Measurements

Ruho Kondo; Yuki Sato; Satoshi Koide; Seiji Kajita; Hideki Takamatsu

doi:10.22331/q-2022-04-13-688

Computationally Efficient Quantum Expectation with Extended Bell Measurements

Ruho Kondo¹, Yuki Sato¹, Satoshi Koide¹, Seiji Kajita¹, and Hideki Takamatsu²

¹Toyota Central R&D Labs., Inc., 41-1, Yokomichi, Nagakute, Aichi 480-1192, Japan
²Toyota Motor Corporation, 1 Toyota-Cho, Toyota, Aichi 471-8571, Japan

Published:	2022-04-13, volume 6, page 688
Eprint:	arXiv:2110.09735v2
Doi:	https://doi.org/10.22331/q-2022-04-13-688
Citation:	Quantum 6, 688 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Evaluating an expectation value of an arbitrary observable $A\in{\mathbb C}^{2^n\times 2^n}$ through naïve Pauli measurements requires a large number of terms to be evaluated. We approach this issue using a method based on Bell measurement, which we refer to as the extended Bell measurement method. This analytical method quickly assembles the $4^n$ matrix elements into at most $2^{n+1}$ groups for simultaneous measurements in $O(nd)$ time, where $d$ is the number of non-zero elements of $A$. The number of groups is particularly small when $A$ is a band matrix. When the bandwidth of $A$ is $k=O(n^c)$, the number of groups for simultaneous measurement reduces to $O(n^{c+1})$. In addition, when non-zero elements densely fill the band, the variance is $O((n^{c+1}/2^n)\,{\rm tr}(A^2))$, which is small compared with the variances of existing methods. The proposed method requires a few additional gates for each measurement, namely one Hadamard gate, one phase gate and at most $n-1$ CNOT gates. Experimental results on an IBM-Q system show the computational efficiency and scalability of the proposed scheme, compared with existing state-of-the-art approaches. Code is available at https://github.com/ToyotaCRDL/extended-bell-measurements.

Featured image: Measurement operators for each component of the matrix using the extended Bell measurements.

► BibTeX data

@article{Kondo2022computationally,
  doi = {10.22331/q-2022-04-13-688},
  url = {https://doi.org/10.22331/q-2022-04-13-688},
  title = {Computationally {E}fficient {Q}uantum {E}xpectation with {E}xtended {B}ell {M}easurements},
  author = {Kondo, Ruho and Sato, Yuki and Koide, Satoshi and Kajita, Seiji and Takamatsu, Hideki},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {688},
  month = apr,
  year = {2022}
}

► References

[1] Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5 (1): 1–7, 2014. 10.1038/ncomms5213.
https://doi.org/10.1038/ncomms5213

[2] Cerezo, M. et al. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625–644, 2021. 10.1038/s42254-021-00348-9.
https://doi.org/10.1038/s42254-021-00348-9

[3] Preskill, J. Quantum computing in the NISQ era and beyond. Quantum, 2: 79, 2018. 10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[4] Huang, H.Y., Bharti, K. and Rebentrost, P. Near-term quantum algorithms for linear systems of equations with regression loss functions. New Journal of Physics, 23 (11): 113021, nov 2021a. 10.1088/1367-2630/ac325f.
https://doi.org/10.1088/1367-2630/ac325f

[5] Bravo-Prieto, C., LaRose, R., Cerezo, M., Subasi, Y., Cincio, L. and Coles, P.J. Variational quantum linear solver. arXiv preprint arXiv:1909.05820, 2019. 10.48550/arXiv.1909.05820.
https://doi.org/10.48550/arXiv.1909.05820
arXiv:1909.05820

[6] Xu, X., Sun, J., Endo, S., Li, Y., Benjamin, S.C. and Yuan, X. Variational algorithms for linear algebra. Science Bulletin, 66 (21): 2181–2188, 2021. 10.1016/j.scib.2021.06.023.
https://doi.org/10.1016/j.scib.2021.06.023

[7] Liu, H.L. et al. Variational quantum algorithm for the poisson equation. Physical Review A, 104 (2): 022418, 2021. 10.1103/physreva.104.022418.
https://doi.org/10.1103/physreva.104.022418

[8] Sato, Y., Kondo, R., Koide, S., Takamatsu, H. and Imoto, N. Variational quantum algorithm based on the minimum potential energy for solving the poisson equation. Physical Review A, 104 (5): 052409, 2021. 10.1103/physreva.104.052409.
https://doi.org/10.1103/physreva.104.052409

[9] Farhi, E., Goldstone, J. and Gutmann, S. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. 10.48550/arXiv.1411.4028.
https://doi.org/10.48550/arXiv.1411.4028
arXiv:1411.4028

[10] Zhou, L., Wang, S.T., Choi, S., Pichler, H. and Lukin, M.D. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10 (2): 021067, 2020. 10.1103/PhysRevX.10.021067.
https://doi.org/10.1103/PhysRevX.10.021067

[11] Harrigan, M.P. et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332–336, 2021. 10.1038/s41567-020-01105-y.
https://doi.org/10.1038/s41567-020-01105-y

[12] Romero, J., Olson, J.P. and Aspuru-Guzik, A. Quantum autoencoders for efficient compression of quantum data. Quantum Science and Technology, 2 (4): 045001, 2017. 10.1088/2058-9565/aa8072.
https://doi.org/10.1088/2058-9565/aa8072

[13] Verdon, G., Broughton, M. and Biamonte, J. A quantum algorithm to train neural networks using low-depth circuits. arXiv preprint arXiv:1712.05304, 2017. 10.48550/arXiv.1712.05304.
https://doi.org/10.48550/arXiv.1712.05304
arXiv:1712.05304

[14] Schuld, M. and Killoran, N. Quantum machine learning in feature hilbert spaces. Physical review letters, 122 (4): 040504, 2019. 10.1103/physrevlett.122.040504.
https://doi.org/10.1103/physrevlett.122.040504

[15] Benedetti, M., Garcia-Pintos, D., Perdomo, O., Leyton-Ortega, V., Nam, Y. and Perdomo-Ortiz, A. A generative modeling approach for benchmarking and training shallow quantum circuits. npj Quantum Information, 5 (1): 1–9, 2019. 10.1038/s41534-019-0157-8.
https://doi.org/10.1038/s41534-019-0157-8

[16] Havlíček, V. et al. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209–212, 2019. 10.1038/s41586-019-0980-2.
https://doi.org/10.1038/s41586-019-0980-2

[17] Schuld, M., Bocharov, A., Svore, K.M. and Wiebe, N. Circuit-centric quantum classifiers. Physical Review A, 101 (3): 032308, 2020. 10.1103/physreva.101.032308.
https://doi.org/10.1103/physreva.101.032308

[18] Romero, J. and Aspuru-Guzik, A. Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions. Advanced Quantum Technologies, 4 (1): 2000003, 2021. 10.1002/qute.202000003.
https://doi.org/10.1002/qute.202000003

[19] Wecker, D., Hastings, M.B. and Troyer, M. Progress towards practical quantum variational algorithms. Physical Review A, 92 (4): 042303, 2015. 10.1103/physreva.92.042303.
https://doi.org/10.1103/physreva.92.042303

[20] Jena, A., Genin, S. and Mosca, M. Pauli partitioning with respect to gate sets. arXiv preprint arXiv:1907.07859, 2019. 10.48550/arXiv.1907.07859.
https://doi.org/10.48550/arXiv.1907.07859
arXiv:1907.07859

[21] Verteletskyi, V., Yen, T.C. and Izmaylov, A.F. Measurement optimization in the variational quantum eigensolver using a minimum clique cover. The Journal of chemical physics, 152 (12): 124114, 2020. 10.1063/1.5141458.
https://doi.org/10.1063/1.5141458

[22] Izmaylov, A.F., Yen, T.C., Lang, R.A. and Verteletskyi, V. Unitary partitioning approach to the measurement problem in the variational quantum eigensolver method. Journal of chemical theory and computation, 16 (1): 190–195, 2020. 10.1021/acs.jctc.9b00791.
https://doi.org/10.1021/acs.jctc.9b00791

[23] Zhao, A., Tranter, A., Kirby, W.M., Ung, S.F., Miyake, A. and Love, P.J. Measurement reduction in variational quantum algorithms. Physical Review A, 101 (6): 062322, 2020. 10.1103/PhysRevA.101.062322.
https://doi.org/10.1103/PhysRevA.101.062322

[24] Gokhale, P. et al. $O(N^3)$ measurement cost for variational quantum eigensolver on molecular hamiltonians. IEEE Transactions on Quantum Engineering, 1: 1–24, 2020. 10.1109/tqe.2020.3035814.
https://doi.org/10.1109/tqe.2020.3035814

[25] Crawford, O., van Straaten, B., Wang, D., Parks, T., Campbell, E. and Brierley, S. Efficient quantum measurement of pauli operators in the presence of finite sampling error. Quantum, 5: 385, 2021. 10.22331/q-2021-01-20-385.
https://doi.org/10.22331/q-2021-01-20-385

[26] Hamamura, I. and Imamichi, T. Efficient evaluation of quantum observables using entangled measurements. npj Quantum Information, 6 (1): 1–8, 2020. 10.1038/s41534-020-0284-2.
https://doi.org/10.1038/s41534-020-0284-2

[27] McClean, J.R., Romero, J., Babbush, R. and Aspuru-Guzik, A. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, 2016. 10.1088/1367-2630/18/2/023023.
https://doi.org/10.1088/1367-2630/18/2/023023

[28] Kandala, A. et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242–246, 2017. 10.1038/nature23879.
https://doi.org/10.1038/nature23879

[29] Jacob, F. and Ted, B. A first course in finite elements. Wiley, 2007. 10.1002/9780470510858.
https://doi.org/10.1002/9780470510858

[30] Kirby, W.M. and Love, P.J. Variational quantum eigensolvers for sparse hamiltonians. Physical review letters, 127 (11): 110503, 2021. 10.1103/physrevlett.127.110503.
https://doi.org/10.1103/physrevlett.127.110503

[31] Huang, H.Y., Kueng, R. and Preskill, J. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16 (10): 1050–1057, 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[32] Hadfield, C., Bravyi, S., Raymond, R. and Mezzacapo, A. Measurements of quantum hamiltonians with locally-biased classical shadows. Communications in Mathematical Physics, 2022. 10.1007/s00220-022-04343-8.
https://doi.org/10.1007/s00220-022-04343-8

[33] Huang, H.Y., Kueng, R. and Preskill, J. Efficient estimation of pauli observables by derandomization. Physical Review Letters, 127 (3): 030503, 2021b. 10.1103/physrevlett.127.030503.
https://doi.org/10.1103/physrevlett.127.030503

[34] Abraham, H. et al. Qiskit: An open-source framework for quantum computing, 2019. 10.5281/zenodo.2562110.
https://doi.org/10.5281/zenodo.2562110

[35] de Wolf, R. Quantum computing: Lecture notes. arXiv preprint arXiv:1907.09415, 2019. 10.48550/arXiv.1907.09415.
https://doi.org/10.48550/arXiv.1907.09415
arXiv:1907.09415

[36] McClean, J.R. et al. Openfermion: the electronic structure package for quantum computers. Quantum Science and Technology, 5 (3): 034014, 2020. 10.1088/2058-9565/ab8ebc.
https://doi.org/10.1088/2058-9565/ab8ebc

[37] Bron, C. and Kerbosch, J. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16 (9): 575–577, 1973. 10.1145/362342.362367.
https://doi.org/10.1145/362342.362367

Cited by

[1] Bojia Duan and Chang-Yu Hsieh, "Hamiltonian-based data loading with shallow quantum circuits", Physical Review A 106 5, 052422 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-05 13:57:36) and SAO/NASA ADS (last updated successfully 2023-06-05 13:57:37). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.