{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T19:28:13Z","timestamp":1780082893214,"version":"3.54.0"},"reference-count":37,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T00:00:00Z","timestamp":1649808000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Evaluating an expectation value of an arbitrary observable A<\/mml:mi>&#x2208;<\/mml:mo>C<\/mml:mi><\/mml:mrow><\/mml:mrow>2<\/mml:mn>n<\/mml:mi><\/mml:msup>&#x00D7;<\/mml:mo>2<\/mml:mn>n<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:msup><\/mml:math> through na\u00efve 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<\/mml:mn>n<\/mml:mi><\/mml:msup><\/mml:math> matrix elements into at most 2<\/mml:mn>n<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math> groups for simultaneous measurements in O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>d<\/mml:mi>)<\/mml:mo><\/mml:math> time, where d<\/mml:mi><\/mml:math> is the number of non-zero elements of A<\/mml:mi><\/mml:math>. The number of groups is particularly small when A<\/mml:mi><\/mml:math> is a band matrix. When the bandwidth of A<\/mml:mi><\/mml:math> is k<\/mml:mi>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>c<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math>, the number of groups for simultaneous measurement reduces to O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>c<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>. In addition, when non-zero elements densely fill the band, the variance is O<\/mml:mi>(<\/mml:mo>(<\/mml:mo>n<\/mml:mi>c<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn>n<\/mml:mi><\/mml:msup>)<\/mml:mo>t<\/mml:mi>r<\/mml:mi><\/mml:mrow>(<\/mml:mo>A<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo>)<\/mml:mo><\/mml:math>, 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<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2022-04-13-688","type":"journal-article","created":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T15:56:38Z","timestamp":1649865398000},"page":"688","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":13,"title":["Computationally Efficient Quantum Expectation with Extended Bell Measurements"],"prefix":"10.22331","volume":"6","author":[{"given":"Ruho","family":"Kondo","sequence":"first","affiliation":[{"name":"Toyota Central R&D Labs., Inc., 41-1, Yokomichi, Nagakute, Aichi 480-1192, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuki","family":"Sato","sequence":"additional","affiliation":[{"name":"Toyota Central R&D Labs., Inc., 41-1, Yokomichi, Nagakute, Aichi 480-1192, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satoshi","family":"Koide","sequence":"additional","affiliation":[{"name":"Toyota Central R&D Labs., Inc., 41-1, Yokomichi, Nagakute, Aichi 480-1192, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seiji","family":"Kajita","sequence":"additional","affiliation":[{"name":"Toyota Central R&D Labs., Inc., 41-1, Yokomichi, Nagakute, Aichi 480-1192, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hideki","family":"Takamatsu","sequence":"additional","affiliation":[{"name":"Toyota Motor Corporation, 1 Toyota-Cho, Toyota, Aichi 471-8571, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,4,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5 (1): 1\u20137, 2014. 10.1038\/ncomms5213.","DOI":"10.1038\/ncomms5213"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Cerezo, M. et al. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625\u2013644, 2021. 10.1038\/s42254-021-00348-9.","DOI":"10.1038\/s42254-021-00348-9"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Preskill, J. Quantum computing in the NISQ era and beyond. Quantum, 2: 79, 2018. 10.22331\/q-2018-08-06-79.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1367-2630\/ac325f"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1909.05820"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Xu, X., Sun, J., Endo, S., Li, Y., Benjamin, S.C. and Yuan, X. Variational algorithms for linear algebra. Science Bulletin, 66 (21): 2181\u20132188, 2021. 10.1016\/j.scib.2021.06.023.","DOI":"10.1016\/j.scib.2021.06.023"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Liu, H.L. et al. Variational quantum algorithm for the poisson equation. Physical Review A, 104 (2): 022418, 2021. 10.1103\/physreva.104.022418.","DOI":"10.1103\/physreva.104.022418"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.104.052409"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Farhi, E., Goldstone, J. and Gutmann, S. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. 10.48550\/arXiv.1411.4028.","DOI":"10.48550\/arXiv.1411.4028"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.10.021067"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Harrigan, M.P. et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332\u2013336, 2021. 10.1038\/s41567-020-01105-y.","DOI":"10.1038\/s41567-020-01105-y"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/2058-9565\/aa8072"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1712.05304"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Schuld, M. and Killoran, N. Quantum machine learning in feature hilbert spaces. Physical review letters, 122 (4): 040504, 2019. 10.1103\/physrevlett.122.040504.","DOI":"10.1103\/physrevlett.122.040504"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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\u20139, 2019. 10.1038\/s41534-019-0157-8.","DOI":"10.1038\/s41534-019-0157-8"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Havl\u00ed\u010dek, V. et al. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209\u2013212, 2019. 10.1038\/s41586-019-0980-2.","DOI":"10.1038\/s41586-019-0980-2"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.101.032308"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1002\/qute.202000003"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.92.042303"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1907.07859"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.5141458"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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\u2013195, 2020. 10.1021\/acs.jctc.9b00791.","DOI":"10.1021\/acs.jctc.9b00791"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.101.062322"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Gokhale, P. et al. $O(N^3)$ measurement cost for variational quantum eigensolver on molecular hamiltonians. IEEE Transactions on Quantum Engineering, 1: 1\u201324, 2020. 10.1109\/tqe.2020.3035814.","DOI":"10.1109\/tqe.2020.3035814"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2021-01-20-385"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Hamamura, I. and Imamichi, T. Efficient evaluation of quantum observables using entangled measurements. npj Quantum Information, 6 (1): 1\u20138, 2020. 10.1038\/s41534-020-0284-2.","DOI":"10.1038\/s41534-020-0284-2"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1367-2630\/18\/2\/023023"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Kandala, A. et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242\u2013246, 2017. 10.1038\/nature23879.","DOI":"10.1038\/nature23879"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Jacob, F. and Ted, B. A first course in finite elements. Wiley, 2007. 10.1002\/9780470510858.","DOI":"10.1002\/9780470510858"},{"key":"29","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physrevlett.127.110503"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Huang, H.Y., Kueng, R. and Preskill, J. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16 (10): 1050\u20131057, 2020. 10.1038\/s41567-020-0932-7.","DOI":"10.1038\/s41567-020-0932-7"},{"key":"31","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/s00220-022-04343-8"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physrevlett.127.030503"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Abraham, H. et al. Qiskit: An open-source framework for quantum computing, 2019. 10.5281\/zenodo.2562110.","DOI":"10.5281\/zenodo.2562110"},{"key":"34","doi-asserted-by":"publisher","unstructured":"de Wolf, R. Quantum computing: Lecture notes. arXiv preprint arXiv:1907.09415, 2019. 10.48550\/arXiv.1907.09415.","DOI":"10.48550\/arXiv.1907.09415"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/2058-9565\/ab8ebc"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Bron, C. and Kerbosch, J. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16 (9): 575\u2013577, 1973. 10.1145\/362342.362367.","DOI":"10.1145\/362342.362367"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-04-13-688\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T15:56:49Z","timestamp":1649865409000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-04-13-688\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,13]]},"references-count":37,"URL":"https:\/\/doi.org\/10.22331\/q-2022-04-13-688","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,13]]},"article-number":"688"}}