Computationally Efficient Quantum Expectation with Extended Bell Measurements

Ruho Kondo1, Yuki Sato1, Satoshi Koide1, Seiji Kajita1, and Hideki Takamatsu2

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

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


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

► BibTeX data

► 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.

[2] Cerezo, M. et al. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625–644, 2021. 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.

[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.

[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.

[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.

[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.

[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.

[9] Farhi, E., Goldstone, J. and Gutmann, S. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. 10.48550/​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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[29] Jacob, F. and Ted, B. A first course in finite elements. Wiley, 2007. 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.

[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.

[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.

[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.

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

[35] de Wolf, R. Quantum computing: Lecture notes. arXiv preprint arXiv:1907.09415, 2019. 10.48550/​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.

[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.

Cited by

[1] Francisco Escudero, David Fernández-Fernández, Gabriel Jaumà, Guillermo F. Peñas, and Luciano Pereira, "Hardware-Efficient Entangled Measurements for Variational Quantum Algorithms", Physical Review Applied 20 3, 034044 (2023).

[2] Matteo Ippoliti, "Classical shadows based on locally-entangled measurements", Quantum 8, 1293 (2024).

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

[4] Yuki Sato, Ruho Kondo, Satoshi Koide, and Seiji Kajita, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 168 (2023) ISBN:979-8-3503-4323-6.

[5] Yuki Sato, Hiroshi C. Watanabe, Rudy Raymond, Ruho Kondo, Kaito Wada, Katsuhiro Endo, Michihiko Sugawara, and Naoki Yamamoto, "Variational quantum algorithm for generalized eigenvalue problems and its application to the finite-element method", Physical Review A 108 2, 022429 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-15 00:03:09) and SAO/NASA ADS (last updated successfully 2024-04-15 00:03:10). The list may be incomplete as not all publishers provide suitable and complete citation data.