IP Library › Granted Patent US 12,731,061
Granted Patent B2
US 12,731,061 · App. 17/863,554 · Granted Sep 8, 2026

Quantum circuit for estimating matrix spectral sums

Inventors: Shashanka Ubaru (Ossining, NY); Ismail Yunus Akhalwaya (Emmarentia, ZA); Kenneth Lee Clarkson (Madison, NJ); Mark S. Squillante (Greenwich, CT); Vasileios Kalantzis (White Plains, NY); Lior Horesh (North Salem, NY)
Assignee: International Business Machines Corporation
G06N10/40G06F17/16
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,731,061
App. No.
17/863,554
Granted
Sep 8, 2026
Kind
B2
Abstract

Systems and methods for operating a quantum system are described. A controller of a quantum system can generate a command signal. The quantum system can include quantum hardware having a plurality of qubits. An interface of the quantum system can control the quantum hardware based on the command signal received from the controller to determine a plurality of moments of a matrix using a random state vector represented by the plurality of qubits. The controller can be further configured to output the plurality of moments of the matrix to a computing device to estimate a trace of a matrix function based on one or more selected moments among the plurality of moments. The matrix function can be a function of the matrix.

Claims (41)

1 . An apparatus comprising:

a controller configured to generate a command signal;

quantum hardware including a plurality of qubits; and

an interface connected to the controller and the quantum hardware, the interface being configured to convert the command signal into a quantum operation to control the quantum hardware to determine a plurality of moments of a matrix using a random state vector represented by the plurality of qubits, wherein a portion of elements of the matrix is unknown; and

the controller being further configured to output the plurality of moments of the matrix to a computing device to estimate a trace of a matrix function based on one or more selected moments among the plurality of moments, wherein the matrix function is a function of the matrix.

2 . The apparatus of claim 1 , wherein the matrix is a Hermitian matrix.

3 . The apparatus of claim 1 , wherein the quantum hardware is configured to generate the random state vector.

4 . The apparatus of claim 1 , wherein the matrix corresponds to a combinatorial Laplacian of simplices of a specific order in a simplicial complex, and a determination of Betti numbers of the simplicial complex is based on the estimated trace of the matrix function.

5 . The apparatus of claim 1 , wherein the trace of the matrix function is based on a set of polynomials determined based on the plurality of moments.

6 . The apparatus of claim 5 , wherein the set of polynomials is a set of Chebyshev polynomials.

7 . The apparatus of claim 1 , wherein the random state vector comprises a specific number of independent entries.

8 . The apparatus of claim 1 , wherein the computing device is a classical computer.

9 . A system comprising:

a first computing device configured to process data encoded in binary data;

a second computing device configured to be in communication with the first computing device, the second computing device being configured to process data encoded in qubits, wherein the second computer device comprises:

a controller configured to generate a command signal;

quantum hardware including a plurality of qubits; and

an interface connected to the controller and the quantum hardware, the interface being configured to convert the command signal into a quantum operation to control the quantum hardware to determine a plurality of moments of a matrix using a random state vector represented by the plurality of qubits, wherein a portion of elements of the matrix is unknown; and

the controller being further configured to output the plurality of moments of the matrix to the first computing device to estimate a trace of a matrix function based on one or more selected moments among the plurality of moments, wherein the matrix function is a function of the matrix.

10 . The system of claim 9 , wherein the matrix is a Hermitian matrix.

11 . The system of claim 9 , wherein the trace of the matrix function is based on a set of Chebyshev polynomials.

12 . The system of claim 9 , wherein the matrix corresponds to a combinatorial Laplacian of simplices of a specific order in a simplicial complex, and first computing device is further configured to determine Betti numbers of the simplicial complex is based on the estimated trace of the matrix function.

13 . The system of claim 9 , wherein the first computing device is configured to estimate the trace of the matrix function by averaging the moments of the matrix function over a number of samples used for generating the random state vector.

14 . The system of claim 9 , wherein to estimate of the trace of the matrix function, the first computing device is configured to determine a set of expansion coefficients based on the matrix function.

15 . The system of claim 9 , wherein the second computing device is configured to generate the random state vector.

16 . The system of claim 9 , wherein the first computing device is configured to:

select a subset of moments among the plurality of moments; and

determine a set of polynomials using the selected subset of moments, wherein the trace of the matrix function is based on the set of polynomials.

17 . The system of claim 9 , wherein the random state vector comprises a specific number of independent entries.

18 . A method of operating a quantum circuit to estimate a trace of a matrix function, the method comprising:

receiving, by a controller of a quantum system, an instruction;

generating, by the controller of the quantum system, a command signal based on the instruction;

converting, by an interface of the quantum system, the command signal into a quantum operation; and

based on the quantum operation, controlling, by the interface of the quantum system, quantum hardware of the quantum system to determine a plurality of moments of a matrix using a random state vector represented by a plurality of qubits, wherein a portion of elements of the matrix is unknown; and outputting, by the controller of the quantum system, the plurality of moments of the matrix to a computing device to estimate a trace of a matrix function based on one or more selected moments among the plurality of moments, wherein the matrix function is a function of the matrix.

19 . The method of claim 18 , wherein the matrix is a Hermitian matrix.

20 . The method of claim 18 , wherein the trace of the matrix function is based on a set of polynomials determined based on the plurality of moments.

21 . The method of claim 20 , wherein the set of polynomials are Chebyshev polynomials.

22 . The method of claim 20 , wherein the set of polynomials are determined based on a subset of the plurality of moments.

23 . The method of claim 18 , wherein the matrix corresponds to a combinatorial Laplacian of simplices of a specific order in a simplicial complex, and a determination of Betti numbers of the simplicial complex is based on the estimated trace of the matrix function.

24 . The method of claim 18 , wherein the random state vector comprises a specific number of independent entries.

25 . The method of claim 18 , wherein the computing device is a classical computer.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 13, 2022
From: UBARU, SHASHANKA; AKHALWAYA, ISMAIL YUNUS; CLARKSON, KENNETH LEE; SQUILLANTE, MARK S.; KALANTZIS, VASILEIOS; HORESH, LIOR
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 060492/0630 →
Continuity (1)
Related Publication 20240020565A1 · Jan 18, 2024
References Cited (94)
US 9275011B2 · Svore et al. · 2016 [cited by applicant]
US 9430688B1 · Ray · 2016 [cited by applicant]
US 10311370B2 · Bravyi et al. · 2019 [cited by applicant]
US 10977546B2 · Gambetta et al. · 2021 [cited by applicant]
US 11321627B1 · Arriola et al. · 2022 [cited by applicant]
US 11625637B2 · Gidney · 2023 [cited by applicant]
US 12001925B2 · Barber et al. · 2024 [cited by applicant]
US 12505370B2 · Akhalwaya et al. · 2025 [cited by applicant]
US 20070036434A1 · Saveliev · 2007 [cited by applicant]
US 20150363708A1 · Amin et al. · 2015 [cited by applicant]
US 20160191060A1 · Mcdermott et al. · 2016 [cited by applicant]
US 20170147946A1 · Umeda · 2017 [cited by applicant]
US 20180025073A1 · Singh et al. · 2018 [cited by applicant]
US 20180287788A1 · Pitala Garcia · 2018 [cited by applicant]
US 20190164034A1 · Gambetta et al. · 2019 [cited by applicant]
US 20200265274A1 · Kachman et al. · 2020 [cited by applicant]
US 20200342380A1 · Selina et al. · 2020 [cited by applicant]
US 20200349050A1 · Ghobadi et al. · 2020 [cited by applicant]
US 20200349459A1 · Cao et al. · 2020 [cited by applicant]
US 20210042651A1 · Das et al. · 2021 [cited by applicant]
US 20210058244A1 · Jacak et al. · 2021 [cited by applicant]
US 20210089953A1 · Bocharov et al. · 2021 [cited by applicant]
US 20210232960A1 · Scott N. et al. · 2021 [cited by applicant]
US 20210256410A1 · Bravyi et al. · 2021 [cited by applicant]
US 20210256414A1 · Kachman et al. · 2021 [cited by applicant]
US 20210272009A1 · Gidney et al. · 2021 [cited by applicant]
US 20210329601A1 · Li · 2021 [cited by applicant]
US 20210383022A1 · Bennati et al. · 2021 [cited by applicant]
US 20220019931A1 · Jiang et al. · 2022 [cited by applicant]
US 20220058435A1 · Ou et al. · 2022 [cited by applicant]
US 20220084398A1 · Zhang et al. · 2022 [cited by applicant]
US 20220172050A1 · Dalli et al. · 2022 [cited by applicant]
US 20220180214A1 · Cervantes et al. · 2022 [cited by applicant]
US 20220299341A1 · Zhang · 2022 [cited by applicant]
US 20230040289A1 · Sels et al. · 2023 [cited by applicant]
US 20230080319A1 · Zhang et al. · 2023 [cited by applicant]
US 20230104188A1 · Zilberman et al. · 2023 [cited by applicant]
US 20230401792A1 · Hofmann · 2023 [cited by applicant]
US 20240020563A1 · Akhalwaya et al. · 2024 [cited by applicant]
US 20240020564A1 · Ubaru et al. · 2024 [cited by applicant]
US 20240022247A1 · Ubaru et al. · 2024 [cited by applicant]
US 20240028939A1 · Akhalwaya et al. · 2024 [cited by applicant]
US 20240037304A1 · Akhalwaya et al. · 2024 [cited by applicant]
US 20240296367A1 · Rubin et al. · 2024 [cited by applicant]
CN 103810227A · 2014 [cited by examiner]
CN 110443785A · 2019 [cited by applicant]
CN 110612540A · 2019 [cited by examiner]
CN 112651418A · 2021 [cited by applicant]
CN 113204738A · 2021 [cited by applicant]
WO 2014081882A2 · 2014 [cited by applicant]
WO 2020164772A1 · 2020 [cited by applicant]
WO 2020263146A1 · 2020 [cited by applicant]
C. Bekas, etc., “An Estimator for the Diagonal of a Matrix”, published online in 2005 to https://www-users.cse.umn.edu/~saad/PDF/umsi-2005-082.pdf, retrieved Oct. 7, 2025. (Year: 2005). [cited by examiner]
Marco Taboga, “Trace of a matrix”, published on Mar. 13, 2019 to https://www.statlect.com/matrix-algebra/trace-of-a-matrix, retrieved Oct. 7, 2025. (Year: 2019). [cited by examiner]
Alice Cortinovis, etc., “On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants”, published to Foundations of Computational Mathematics in an online version as of Jul. 9, 2021, retriev… [cited by examiner]
Bhargavi Jonnadula, etc., “On the moments of characteristic polynomials”, published on Jun. 22, 2021 to arXiv, retrieved Oct. 7, 2025. (Year: 2021). [cited by examiner]
Andreas Holzner, etc., “Chebyshev matrix product state approach for spectral functions”, published to Physical Review B 83, 195115 (2011), retrieved Oct. 7, 2025. (Year: 2011). [cited by examiner]
Joao Pita Costa, “Topological data analysis and applications”, published via MIPRO, May 22-26, 2017, Opatija, Croatia, retrieved Oct. 7, 2025. (Year: 2017). [cited by examiner]
Xiaoming Sun, etc., “Querying a Matrix through Matrix-Vector Products”, published on Nov. 7, 2019 to arXiv, retrieved Apr. 20, 2026. (Year: 2019). [cited by examiner]
Alessandro Luongo, etc., “Quantum algorithms for spectral sums”, published on Nov. 12, 2020 to arXiv, retrieved Apr. 20, 2026. (Year: 2020). [cited by examiner]
Adrian Steffens, etc., “An efficient quantum algorithm for spectral estimation”, published via 2017 New J. Phys. 19 033005, retrieved Apr. 20, 2026. (Year: 2017). [cited by examiner]
Anirban Chowdhury, “Classical and quantum algorithms for estimating traces and partition functions”, published to YouTube at https://www.youtube.com/watch?v=xiwpH9i3m5g on Jan. 26, 2022, retrieved Apr. 20, 2026. (Year: … [cited by examiner]
Aram W. Harrow, etc., “Quantum algorithm for linear systems of equations”, published on Sep. 30, 2009 to arXiv, retrieved Apr. 20, 2026. (Year: 2009). [cited by examiner]
Adriyan Bayu Suksmono, etc., “Quantum computing formulation of some classical Hadamard matrix searching methods and its implementation on a quantum”, published on Jan. 7, 2022 via Nature-Scientific Reports, retrieved Ap… [cited by examiner]
Ubaru, Shashanka et al., “Quantum Topological Data Analysis with Linear Depth and Exponential Speedup,” arXiv preprint arXiv:2108.02811, Aug. 5, 2021, 27 pages (Grace Period Disclosure). [cited by applicant]
Hayakawa, Ryu, “Quantum Algorithm for Persistent Betti Numbers and Topological Data Analysis,” arXiv preprint arXiv:2111.00433, Oct. 31, 2021, 25 pages. [cited by applicant]
Seth Lloyd, “Quantum algorithms for topological and geometric analysis of data.” arXiv:1408.3106v2 [quant-ph] Dec. 15, 2015 20 pages https://arxiv.org/abs/1408.3106. [cited by applicant]
Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212-219 https://arxiv.org/abs/quant-ph/9605043. [cited by applicant]
Hajij, Mustafa et al., “Simplicial Complex Representation Learning,” arXiv preprint arXiv:2103.04046, Feb. 22, 2022, 10 pages. [cited by applicant]
NIST, “NIST Cloud Computing Program”, http://csrc.nist.gov/groups/SNS/cloud-computing/index.html, Created Dec. 1, 2016, Updated Oct. 6, 2017, 9 pages. [cited by applicant]
Horesh, L., et al., “Quantum Computing Algorithms for Decision Making Under Uncertainty”, Jul. 14, 2021, 111 pages, (Grace Period Disclosure). [cited by applicant]
Low, G.H., et al., “Optimal Hamiltonian Simulation by Quantum Signal Processing”, arXiv:1606.02685v2, Dec. 20, 2016, 6 pages. [cited by applicant]
Van Den Berg, E., et al., “Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters”, arXiv:2003.13599v2, Sep. 5, 2020, 28 pages. [cited by applicant]
Cade, Chris, and Ashley Montanaro. “The Quantum Complexity of Computing Schatten norms.” arXiv preprint arXiv:1706.09279 (Jun. 28, 2017). 28 Pages. [cited by applicant]
Luongo, Alessandro, and Changpeng Shao. “Quantum algorithms for spectral sums.” arXiv preprint arXiv:2011.06475 (Nov. 12, 2020). 24 Pages. [cited by applicant]
Gyurik, Casper, Chris Cade, and Vedran Dunjko. “Towards quantum advantage for topological data analysis.” arXiv e-prints (Mar. 1, 2020): arXiv-2005. 29 Pages. [cited by applicant]
Avron, Haim, and Sivan Toledo. “Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix.” Journal of the ACM (JACM) 58.2 (Apr. 2010): 16 Pages. [cited by applicant]
Hutchinson, M.F., 1989. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communications in Statistics—Simulation and Computation, 18(3), pp. 1059-1076. [cited by applicant]
Brakerski, Zvika, and Shmueli, Omri “(Pseudo) Random Quantum States with Binary Phase.” Theory of Cryptography Conference. Springer, Cham, Jun. 26, 2019, 21 pages. [cited by applicant]
Fitzsimons, Jack K. et al., “Improved Stochastic Trace Estimation using Mutually Unbiased Bases,” arXiv preprint arXiv:1608.00117, Jul. 30, 2016, 5 pages. [cited by applicant]
Fika, Paraskevi et al., “Estimation of the Bilinear Form y□ f (A) x for Hermitian Matrices,” Linear Algebra and its Applications 502, 2016, pp. 140-158. (See article history for dates). [cited by applicant]
Ubaru, Shashanka, and Yousef Saad. “Fast methods for estimating the numerical rank of large matrices.” International Conference on Machine Learning. PMLR, 2016. 10 Pages. [cited by applicant]
Han, I., Malioutov, D., Avron, H., & Shin, J. (2017). Approximating spectral sums of large-scale matrices using stochastic chebyshev approximations. SIAM Journal on Scientific Computing, 39(4), A1558-A1585. Mar. 9, 2017… [cited by applicant]
Fan, Li et al., “Spectrum-Adapted Polynomial Approximation for Matrix Functions,” arXiv preprint arXiv:1808.09506, Aug. 28, 2018, 5 pages. [cited by applicant]
Han, Insu et al., “Stochastic Chebyshev Gradient Descent for Spectral Optimization,” Advances in Neural Information Processing Systems 31, 2018, 11 pages. [cited by applicant]
Akhalwaya, Ismail Yunus et al., “Don't Count the Shots, Make the Shots Count: Efficient Quantum Computation of the Fermionic Boundary Operator”, arXiv:2201.11510v1, Jan. 27, 2022, 16 pages. [cited by applicant]
Non-Final Rejection Mailed on Apr. 11, 2025 for U.S. Appl. No. 17/863,449, 8 page(s). [cited by applicant]
Notice of Allowance and Fees Due (PTOL-85) Mailed on Apr. 10, 2025 for U.S. Appl. No. 17/863,524, 9 page(s). [cited by applicant]
Non-Final Rejection Mailed on Aug. 22, 2025 for U.S. Appl. No. 17/863,484, 6 page(s). [cited by applicant]
Non-Final Rejection Mailed on Jun. 30, 2025 for U.S. Appl. No. 17/863,508, 25 page(s). [cited by applicant]
United States Final Rejection dated Dec. 4, 2025, 16 pages, in U.S. Appl. No. 17/863,484. [cited by applicant]
Thurey et al. “A Boundary Operator for Simplices”, arXiv: 1109.2161 [math. GT], Sep. 13, 2018, pp. 1-33. [cited by applicant]
United States Non-Final Rejection dated Mar. 13, 2026, 50 pages, in U.S. Appl. No. 17/863,500. [cited by applicant]
United States Notice of Allowance dated Nov. 4, 2025, 17 pages, in U.S. Appl. No. 17/863,508. [cited by applicant]