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

On Crossref's cited-by service no data on citing works was found (last attempt 2022-10-05 01:21:58). On SAO/NASA ADS no data on citing works was found (last attempt 2022-10-05 01:21:58).