PaperlayerView exact revision on arXiv

Source-linked AI summary

Measuring all compatible operators in one series of a single-qubit measurements using unitary transformations

Tzu-Ching Yen, Vladyslav Verteletskyi, Artur F. Izmaylov

arXiv:1907.09386v4quant-phphysics.chem-ph

TL;DR

VQE requires estimating qubit-Hamiltonian expectation values, and whether fully commuting terms can be grouped without hardware changes remains an open question. This paper uses unitary transformations to convert fully commuting groups into qubit-wise-commuting groups; for considered molecular Hamiltonians, it reports at least N-fold fewer measurable groups than QWC grouping.

  • Problem

    VQE requires estimating qubit-Hamiltonian expectation values, and whether fully commuting terms can be grouped without hardware changes and optimally remains an open question.

    Source: §I · p. 1, A. Tensor product eigen-basis sharing… · p. 2

  • Method

    Unitary transformations convert groups of fully commuting Hamiltonian terms into qubit-wise-commuting groups that can be measured simultaneously.

    Source: §I · p. 2, §IV · p. 6

  • Results

    At least N-fold fewer measurable groups than QWC grouping were produced for the considered molecular Hamiltonians.

    Source: §IV · p. 6

  • Takeaways & Limitations

    The technique requires no modification of currently used measuring hardware to measure larger groups of compatible operators.

    Source: §IV · p. 6

    The demonstrated approach focuses on fully commuting groups, while broader unitary transformations are described only as a potential way to reduce measurements further.

    Source: §IV · pp. 6–7

Abstract

from arXiv · show

The Variational Quantum Eigensolver approach to the electronic structure problem on a quantum computer involves measurement of the Hamiltonian expectation value. Formally, quantum mechanics allows one to measure all mutually commuting or compatible operators simultaneously. Unfortunately, the current hardware permits measuring only a much more limited subset of operators that share a common tensor product eigen-basis. We introduce unitary transformations that transform any fully commuting group of operators to a group that can be measured on current hardware. These unitary operations can be encoded as a sequence of Clifford gates and let us not only measure much larger groups of terms but also to obtain these groups efficiently on a classical computer. The problem of finding the minimum number of fully commuting groups of terms covering the whole Hamiltonian is found to be equivalent to the minimum clique cover problem for a graph representing Hamiltonian terms as vertices and commutativity between them as edges. Tested on few molecular electronic Hamiltonians with up to 50 thousand terms, the introduced technique allows for the reduction of the number of separately measurable operator groups down to few hundreds, thus achieving up to 2 orders of magnitude reduction. It was also shown that this gain scales at least linearly with the number of qubits.

I. INTRODUCTION

The introduction presents measurement of the VQE Hamiltonian as a key difficulty and proposes unitary transformations to make fully commuting term groups measurable on current hardware.

I. INTRODUCTION

  • In VQE, a quantum computer estimates the target Hamiltonian expectation value for a trial wavefunction, and a classical computer uses prior estimates to propose the next wavefunction [2–4].The variational theorem guarantees that any trial wavefunction approaches the solution from above.Source: §I · p. 1
  • In universal gate quantum computing, the qubit Hamiltonian is not physically implemented, making its expectation-value measurement difficult; only an O(N^4) subset of 4^N Pauli products is needed [17, 18].The Hamiltonian measurement problem is described as similar to quantum tomography.Source: §I · pp. 1–2
  • TPE-based grouping reduces the number of terms by approximately three times but does not change the O(N^4) scaling of measured groups [19].Current hardware permits simultaneous measurement only for Pauli products sharing a common tensor-product eigenbasis.Source: §I · p. 2
  • Mean-field partitioning offers an advantage over TPE grouping but requires feed-forward measurement unavailable on mainstream hardware and lacks an optimal partitioning algorithm [20–24].Source: §I · p. 2

II. THEORY · A. Tensor product eigen-basis sharing groups

The section distinguishes hardware-compatible qubit-wise commuting (QWC) groups from the larger groups allowed by full commutativity, and frames grouping as a graph-clique problem. It motivates seeking fully commuting groups while noting the practical constraints of measurement and grouping.

II. THEORY · A. Tensor product eigen-basis sharing groups

B. Unitary Transformations

The section introduces unitary transformations that convert fully commuting operator groups into qubit-wise commuting groups, enabling their measurement with the standard single-qubit protocol. It outlines a construction based on an extension of qubit tapering and notes that the transformations can be implemented efficiently as Clifford gates.

B. Unitary Transformations

  • The transformations U_n map each fully commuting group H_n to a qubit-wise commuting group A_n, which need not match the Hamiltonian’s original qubit-wise commuting groups.This allows measurement of more efficient fully commuting partitions while retaining the single-qubit measurement protocol.Source: B. Unitary Transformations · p. 3
  • Qubit-wise measurements of A_n on the transformed wavefunction yield the energy expectation value, while U_n preserves the commutativity of H_n.The construction inserts U_n and its adjoint around the trial wavefunction so the transformed group can be measured regularly.Source: B. Unitary Transformations · p. 3
  • Extending qubit tapering, the construction maps all single-qubit operators within H_n to a fixed Pauli operator, making the transformed terms qubit-wise commuting.The paper states that such transformations always exist for linear combinations of commuting Pauli products.Source: B. Unitary Transformations · p. 3
  • The transformations can be expressed as sequences of Clifford gates, whose implementation efficiency on quantum and classical computers is guaranteed by the Gottesman-Knill theorem.26The construction procedure is detailed in Appendix B.Source: B. Unitary Transformations · p. 3

C. Illustrative Example

In a two-qubit model with commuting terms that share Bell-state eigenstates, the example shows a unitary mapping to a QWC operator allows both term contributions to be read in one measurement set.

C. Illustrative Example

  • The model Hamiltonian H_m = a x_1x_2 + b z_1z_2 has commuting terms sharing Bell-state eigenstates, with z_1z_2 eigenvalues +1 or −1 and x_1x_2 eigenvalues ±1.Source: C. Illustrative Example · p. 3
  • In the conventional single-qubit scheme, measuring z_1z_2 collapses |∥+⟩ into |↑↑⟩ or |↓↓⟩ and destroys information about x_1x_2, requiring a separate measurement basis.The z-basis outcomes cannot distinguish |∥+⟩ from |∥−⟩.Source: C. Illustrative Example · pp. 3–4
  • The new technique introduces U = (x1x2 + z1)(z1z2 + x2)/2 and uses it to modify the model Hamiltonian into a QWC group.Source: C. Illustrative Example · p. 4
  • For |∥+⟩ and |∥−⟩, measuring transformed operator a z_1 + b x_2 returns a+b and −a+b, respectively, in one measurement set.The transformed operator is QWC.Source: C. Illustrative Example · p. 4

D. Optimal partitioning of the Hamiltonian

The section formulates optimal grouping of mutually commuting Pauli products as a minimum clique-cover problem on a commutativity graph and describes heuristic approaches to solving it.

D. Optimal partitioning of the Hamiltonian

  • Representing Pauli products as vertices connected when they commute turns optimal grouping into a minimum clique-cover (MCC) problem.Each clique is a group of mutually commuting terms that can be measured together.Source: D. Optimal partitioning of the… · p. 4
  • MCC is NP-hard in general, so the section applies the same heuristics used for QWC grouping.The methods are Greedy Coloring, Largest First, Smallest Last, DSATUR, Recursive Largest First, Dutton and Brigham, COSINE, Ramsey, and Bron-Kerbosch-Tomita.Source: D. Optimal partitioning of the… · p. 4
  • The heuristics scale quadratically with graph vertices; all except Bron-Kerbosch-Tomita have polynomial computational scaling.The section notes that these methods can readily produce close-to-optimal solutions.Source: D. Optimal partitioning of the… · p. 4

III. NUMERICAL STUDIES AND DISCUSSION

The study solves the minimum clique cover problem for graphs of qubit Hamiltonians from several molecule/basis pairs. It evaluates heuristic performance and the scaling of fully commuting groups with qubit count.

  • RLF is the algorithm of choice: it is fastest and yields about 25% fewer cliques than the next-best heuristics, while BKT scales exponentially and DB is much slower.Heuristic clique counts can differ by up to 50%; DB takes two orders of magnitude longer than RLF for 14-qubit systems.Source: §III · p. 6
  • Maximum clique sizes grow at a rate slightly higher than linear in N, while standard deviations of clique-size distributions grow at a rate slightly lower than linear.Source: §III · p. 6
  • Separate analyses found no significant differences between groupings for Hamiltonians obtained with JW and BK transformations.Source: §III · p. 6
  • The number of RLF fully commuting groups scales as N^3, versus N^4 for total Hamiltonian terms, an N-fold reduction in scaling.The clique-count fit uses N in double-logarithmic scale; Figure 3 shows the dependencies for systems in Table II.Source: Figure 3 · p. 6, §III · p. 6

IV. CONCLUSIONS

The method groups Hamiltonian terms into fully commuting sets and uses unitary transformations to make each set measurable as qubit-wise commuting terms. For the molecular Hamiltonians considered, it reduces the number of measurable groups compared with conventional QWC grouping without modifying current measuring hardware.

IV. CONCLUSIONS

  • Partitioning the qubit Hamiltonian into the minimum number of fully mutually commuting groups, then transforming each group to QWC terms, enables simultaneous measurement on current hardware.The transformations do not require modification of the measuring hardware.Source: §IV · p. 6
  • The method achieves at least N-fold fewer measurable groups than previously used QWC grouping for the considered molecular electronic Hamiltonians.Each added transformation uses 2N one-qubit gates and N multi-qubit Pauli product exponents; the transformations can be encoded with Clifford gates, and the number of CNOT gates can be reduced to O(N^2/log(N)).Source: §IV · p. 6
  • When circuit depth makes the added transformations unaffordable, conventional QWC grouping is preferable because it introduces no nonlocal gates.The transformations add 2N one-qubit gates and N multi-qubit Pauli product exponents, decomposable into up to ∼N^(1+log_2 3) two-qubit gates.Source: §IV · p. 6
  • For MUB quantum state tomography, the transformations convert each of the 2Nq + 1 groups of 2Nq − 1 fully commuting Pauli strings into a QWC group, enabling local measurements.The passage contrasts this with QWC grouping's 3Nq measurements and says naive tomography would require 4Nq − 1.Source: §IV · p. 6
  • A single unitary could transform the entire Hamiltonian into a QWC group and permit measurement in one set, but its complexity equals that of the original many-body problem.This possibility follows from the passage's stated maximum QWC group size of 2N.Source: §IV · p. 6
  • The example suggests that more general unitary transformations may reduce the number of simultaneously measurable terms beyond groups of fully commuting terms.Such transformations could act on the whole Hamiltonian, rather than only Hamiltonian fragments.Source: §IV · pp. 6–7

NOTE ADDED: … Obtaining expansions in ˆτi’s

The appendices explain how symplectic linear algebra turns fully commuting Pauli products into operators measurable in a qubit-wise commuting basis, and show that commuting products vastly outnumber qubit-wise commuting ones for an average product.

APPENDIX A: COMMUTING AND QUBIT-WISE COMMUTING TERMS

  • The ratio of commuting to qubit-wise commuting terms grows as 2^(3N/4−1) for the average Pauli product considered.The comparison is over the full set of 4^N Pauli products, with N mod 4 = 0 for convenience.Source: Appendix A · p. 7

Unitary transformations; NOTE ADDED:; APPENDIX B: DETAILS OF UNITARY TRANSFORMATIONS

  • The transformation construction finds N commuting τ_i that commute with every term, pairs them with single-qubit σ_i operators, and maps each τ_i to its σ_i.The construction draws on Bravyi et al. [25]; after submission, the authors noted several new measurement proposals [41–47].Source: Unitary transformations · p. 7, Appendix B · p. 7, NOTE ADDED · p. 7

Operator-vector space mapping

  • A 2N-dimensional binary symplectic representation maps Pauli-product commutation to vector orthogonality and vector addition to operator multiplication up to phase.Each qubit’s identity, X, Y, and Z corresponds to a pair of binary entries; the mapping uses GF(2).Source: Operator-vector space mapping · p. 8

FEW ELEMENTS OF SYMPLECTIC GEOMETRY

  • The appendix introduces symplectic geometry as the framework for treating fully commuting operator sets.It states the orthogonal-complement dimension relation dim(V) + dim(V⊥) = 2N and that taking the complement twice returns V.Source: Types of symplectic subspaces · p. 8

Types of symplectic subspaces

  • The commuting operators form an isotropic subspace that can be extended to a Lagrangian subspace with N basis vectors, mapped to mutually commuting τ_i operators.For an isotropic subspace V, a Lagrangian L exists with V ⊆ L ⊆ V⊥ and dim(L) = N.Source: Types of symplectic subspaces · p. 8, PROCEDURES · p. 8

PROCEDURES

  • The procedure uses Gaussian elimination and symplectic Gram–Schmidt orthogonalization to extend a commuting set to a Lagrangian basis of N operators τ_i.It first forms an isotropic basis, finds its symplectic orthogonal complement when needed, then removes anticommuting pairs until N mutually commuting vectors remain.Source: PROCEDURES · pp. 8–9
  • The construction ensures a distinct-qubit single-qubit operator for each τ_i, using orthogonalization to preserve the required commutation relations.At each intermediate step, a nontrivial operator on an as-yet-unused qubit exists; otherwise the remaining terms would violate the assumed commutation conditions or be the zero vector.Source: PROCEDURES · p. 9

Obtaining expansions in ˆτi’s

  • Each Hamiltonian term’s expansion in the τ_i basis is found by solving a binary linear system with Gaussian elimination over GF(2).The nonzero solution entries select the τ_i factors, and their product reproduces the Pauli product up to phase.Source: Obtaining expansions in ˆτi’s · p. 9

Complexity of operations performed on a classical · 2) Finding ˆσi’s:

Classical grouping uses an RLF heuristic with total scaling O(N^12), while generating each group’s unitary has largest scaling O(nN^3).

computer

  • O(N^12) is the total scaling of the RLF heuristic for partitioning the Hamiltonian into fully commuting groups, despite its small pre-factor.The heuristic scales cubically in the number of Hamiltonian terms, whose total count scales as O(N^4).Source: computer · p. 10
  • O(nN) is required to represent n Pauli terms in binary, and Gaussian elimination on the n × 2N matrix costs O(nN^2).These are preliminary steps in constructing the group unitary.Source: computer · p. 10
  • O(N^2) is required to obtain the null space after Gaussian elimination.Source: computer · p. 10
  • O(N^3) CPU time and O(N^2) memory are required to construct the Lagrangian subspace and save intermediate anti-commuting pairs.Source: computer · p. 10
  • O(N^3) scaling arises when orthogonalization searches for the σ_i operators by modifying up to N other τ_i operators for each of N τ_i operators.Each modification scales as O(N).Source: 2) Finding ˆσi’s · p. 10

2) Finding ˆσi’s:

  • O(nN^3) is required to expand n Pauli terms as products of τ_k, while computing their phases costs O(nN^2).Source: 2) Finding ˆσi’s · p. 10
  • O(nN^3) is the largest scaling across all parts of generating each group’s unitary transformation.The group contains n Pauli terms, and the largest cost comes from expanding them in the τ_i operators.Source: 2) Finding ˆσi’s · p. 10

Encoding unitary transformations on a quantum

The section describes a Clifford-gate implementation of unitary transformations for measuring commuting Pauli operators, and illustrates the procedure by converting a group in the H2/STO-3G Hamiltonian into a qubit-wise commuting group.

computer

  • In the worst case, each e^(iπτ_i/4) decomposes into O(N log_2 3) two-qubit operations, and U_n uses at most O(N^(1+log_2 3)) one- and two-qubit gates [49].Because U_n maps Pauli products to Pauli products, it can be encoded as Clifford gates [26]; Clifford circuits have a CNOT bound of O(N^2/log(N)) [36].Source: computer · p. 10

Example: H2 molecule

  • The H2/STO-3G example transforms one mutually commuting group into a qubit-wise commuting (QWC) group.The construction gives sets T = {z3, z1, y2y0, x2x0} and Q = {x3, x1, x2, y0}.Source: Example: H2 molecule · p. 10
Loading 1907.09386v4…