Qiskit / qiskit-addon-slc / 33365885072

79%

push

github

Perf: reduced-op eigensolver (#97)

* perf: solve the commutator spectral norm via symplectic reduction

`get_extremal_eigenvalue` converted the operator to a 2^n sparse matrix and
ran an iterative Davidson solve for the smallest eigenvalue. Instead,
exploit that the spectral norm of a Hermitian Pauli sum depends only on the
*-algebra its terms generate: that algebra is M_{2^p} tensored with a
2^c-dimensional center, so the operator reduces to a 2^(p+c)-dimensional one
(p = independent anticommuting pairs, c = commuting directions) whose size
is set by the algebra, not the qubit count n.

The reduction (symplectic Gram-Schmidt over GF(2), with phases read from
Qiskit's Pauli arithmetic rather than derived by hand) yields a small
operator that is diagonalized densely and exactly when 2^(p+c) is small, and
otherwise handed to the iterative Davidson solver on the reduced (never the
full 2^n) operator. For the commutators encountered here this is exact,
avoiding potential convergence issues, and can be much faster.

The public (converged, eigenvalue) contract is unchanged.

Written with assistance of Claude ai tool.

* lint

* add tests: reduce_op / get_extremal_eigenvalue

* try to help type checker

* try again to help type checker

* fix false-positive typo

* update test pickles

Updated pickles verified by dense numpy eigvalsh on the original commutator (not reduced operator), agreeing to numerical precision (<1e-13).

* Simplify row-reduction by using `anticommutes()`

* clean up `_symplectic_gram_schmidt()`

* add _commutation_matrix() subroutine

uses private attributes inside qiskit so may need to revisit

* clean up `_xor_row_reduce` (now `_get_basis`)

* update _reduce_operator()

* delete unused _logical_generators()

* update get_extremal_eigenvalue()

- use new _reduce_operator() return signature
- shrink size of exponentially large array made in p == 0 case (no anticommuting generators)

* update (and simplify) tests

* lint

* fix: don't c... (continued)

121 of 126 new or added lines in 2 files covered. (96.03%)

748 of 950 relevant lines covered (78.74%)

0.79 hits per line