PaperlayerView exact revision on arXiv

Source-linked AI summary

Term Grouping and Travelling Salesperson for Digital Quantum Simulation

Kaiwen Gui, Teague Tomesh, Pranav Gokhale, Yunong Shi, Frederic T. Chong, Margaret Martonosi, Martin Suchara

arXiv:2001.05983v3quant-ph

TL;DR

Digital quantum simulation is limited by high gate counts and Trotter errors from noncommuting terms. This paper proposes max-commute-tsp, which combines commuting-term grouping, fidelity-oriented ordering, and TSP-based gate cancellation. In noisy benchmarks, it achieves lower Hellinger infidelities than lexicographic or magnitude ordering, with reductions of 1.1%, 1.6%, 2.6%, and 3.0% across error levels.

  • Problem

    Digital quantum simulation faces high physical errors from large circuits and algorithmic errors from Trotter approximation of noncommuting terms.

  • Method

    Max-commute-tsp groups Pauli terms into commuting families, optimizes their ordering for Trotter fidelity, and formulates gate cancellation as a travelling salesperson problem.

  • Results

    Max-commute-tsp attains minimum infidelities 1.1%, 1.6%, 2.6%, and 3.0% lower than lexicographic or magnitude ordering across respective error levels.

  • Takeaways & Limitations

    The combined strategy mitigates physical and algorithmic errors in quantum-circuit simulations of molecular Hamiltonians.

Abstract

from arXiv · show

Digital simulation of quantum dynamics by evaluating the time evolution of a Hamiltonian is the initially proposed application of quantum computing. The large number of quantum gates required for emulating the complete second quantization form of the Hamiltonian, however, makes such an approach unsuitable for near-term devices with limited gate fidelities that cause high physical errors. In addition, Trotter error caused by noncommuting terms can accumulate and harm the overall circuit fidelity, thus causing algorithmic errors. In this paper, we propose a new term ordering strategy, max-commute-tsp (MCTSP), that simultaneously mitigates both algorithmic and physical errors. First, we improve the Trotter fidelity compared with previously proposed optimization by reordering Pauli terms and partitioning them into commuting families. We demonstrate the practicality of this method by constructing and evaluating quantum circuits that simulate different molecular Hamiltonians, together with theoretical explanations for the fidelity improvements from our term grouping method. Second, we describe a new gate cancellation technique that reduces the high gate counts by formulating the gate cancellation problem as a travelling salesperson problem, together with benchmarking experiments. Finally, we also provide benchmarking results that demonstrate the combined advantage of max-commute-tsp to mitigate both physical and algorithmic errors via quantum circuit simulation under realistic noise models.

I. INTRODUCTION

Digital quantum simulation maps Hamiltonian evolution to quantum circuits, but large circuit depth and noncommuting Pauli terms create physical and algorithmic errors. The proposed max-commute-tsp strategy groups and orders terms to improve fidelity while enabling gate cancellation.

  • Large DQS circuits can cause high physical errors on near-term devices, while Trotter-Suzuki approximation introduces algorithmic errors from noncommuting Pauli terms.The paper identifies both limited hardware fidelity and accumulated Trotter error as central obstacles.
  • Max-commute-tsp simultaneously targets physical and algorithmic errors through Pauli-term grouping and ordering.The strategy first forms commuting groups, then optimizes ordering within and across groups.
  • The method uses commuting cliques to improve Trotter fidelity and preserve ordering freedom for subsequent gate cancellation.Reordering terms within a commuting group does not harm Trotter fidelity, while the available freedom supports cancellation optimization.
  • Gate cancellation is formulated as a travelling salesperson problem, with the paper providing theoretical analysis and initial implementations.The TSP formulation maps vertices, edges, and weights to a minimal-gate ordering problem.
  • The benchmarking focuses on molecular Hamiltonians and evaluates separate and combined physical- and algorithmic-error mitigation using noisy and noiseless simulations.The authors also provide an open-source DQS implementation for benchmarking.

C. Travelling Salesperson Problem

The paper recasts gate-cancellation ordering as a Hamiltonian-path variant of TSP, mapping Pauli-term relationships to weighted graph paths. Because exact TSP is NP-hard, the approach relies on polynomial-time heuristics and compares against established orderings.

  • C. Travelling Salesperson Problem: TSP seeks a minimum-weight route visiting every vertex once, while the paper uses the related path problem without requiring a return to the origin.This graph formulation supplies the optimization framework for term ordering.
  • C. Travelling Salesperson Problem: Gate-cancellation ordering is formulated as a Hamiltonian-path problem whose vertices, edges, and weights map to Pauli-term optimization.The path visits each vertex once and minimizes the total gate count rather than returning to the starting vertex.
  • C. Travelling Salesperson Problem: Exact TSP is NP-hard, so the proposed gate-cancellation optimization cannot generally be solved in polynomial time.The paper therefore discusses polynomial-time approximation heuristics.
  • C. Travelling Salesperson Problem: The method is evaluated against lexicographic, interleave, and magnitude orderings, which target gate cancellation or Trotter-error reduction differently.Lexicographic ordering groups similar Pauli characters for CNOT cancellation, whereas interleave and magnitude ordering emphasize Trotter fidelity.

B. Interleave Term Ordering

Interleave ordering structures Pauli terms according to molecular operator classes and groups several mutually commuting terms. Magnitude ordering instead sorts by coefficient size, which prior work suggests can produce orderings resembling interleave ordering.

  • B. Interleave Term Ordering: Interleave ordering executes molecular operator classes in a prescribed sequence, with several terms commuting within the grouped stages.The listed sequence processes Hpp and Hpqqp terms, then Hpq with Hprrq terms, followed by Hpqrs terms.
  • B. Interleave Term Ordering: Interleave ordering improves Trotter fidelity by grouping terms with similar physical properties, with lines 1 and 2a commuting under the stated condition.The paper contrasts this physical similarity with lexicographic ordering.
  • B. Interleave Term Ordering: Magnitude ordering sorts Pauli terms by the absolute values of their coefficients, assuming similar magnitudes indicate similar physical properties and fewer Trotter errors.The cited prior work reports hpp > hpqqp > hpq > hpqqr > hpqrs for particular molecules.
  • B. Interleave Term Ordering: For the studied molecules, prior work suggests magnitude ordering can produce orderings similar to interleave ordering.This connection motivates magnitude ordering as a Trotter-fidelity baseline.
  • B. Interleave Term Ordering: The paper also considers depleteGroups, random ordering, and TSP gate cancellation as related alternatives or optimization contexts.depleteGroups partitions terms into mutually commuting cliques, while random ordering serves as a baseline and TSP is applied after grouping.

C. Group Commutation Circuit

The group-commutation circuit partitions Pauli terms into commuting groups so their subcircuits can be concatenated with reduced Trotter error. Within each group, term order can then be optimized for gate cancellation without changing Trotter fidelity.

  • C. Group Commutation Circuit: Mutually commuting Pauli groups can be mapped exactly within each group, allowing the method to exploit commuting partitions without losing Trotter fidelity.Theorem 2 and Corollary 2 justify constructing exact group circuits and freely reordering terms inside a commuting partition.
  • C. Group Commutation Circuit: The first-order Trotter approximation becomes exact in the limit as the Trotter number increases and the timestep decreases, while higher-order decompositions are also compatible with the techniques.The experiments and theoretical examination use first-order Trotterization, but the authors state that the techniques apply to higher orders.
  • C. Group Commutation Circuit: The method first groups commuting terms, then concatenates the resulting subcircuits to reduce potential Trotter error before optimizing internal order.This ordering creates subcircuits containing as many pairwise commuting terms as possible.
  • C. Group Commutation Circuit: Group-commutation ordering matches magnitude ordering in Trotter fidelity and outperforms lexicographic ordering in the reported experiments.The comparison is stated for the experimental demonstrations in Section VII.
  • C. Group Commutation Circuit: After grouping, internal term order can be chosen to maximize gate cancellation because commuting-term reordering does not affect fidelity.This enables a TSP formulation for optimizing the order within each group.

A. Problem Abstraction

The paper abstracts Pauli-term grouping as a graph problem: vertices are terms and edges represent commutation, enabling minimum clique covers. It then heuristically orders the resulting cliques using inter-clique commutation information to reduce Trotter error.

  • A. Problem Abstraction: Pauli terms become graph vertices, with edges connecting commuting pairs; coefficients are omitted during grouping because they do not affect commutativity.Coefficients are considered later for clique-clique ordering and determine Rz parameters in circuit mapping.
  • A. Problem Abstraction: For H2, the 14 Pauli terms form two fully connected cliques that can be concatenated as separate commuting circuit blocks.The graph representation records commutation relations but not the molecular coefficients.
  • A. Problem Abstraction: The grouping objective is a minimum partition into commuting families, implemented through clique-cover algorithms such as recursive Bron–Kerbosch and polynomial-time heuristics.The paper uses prior clique-finding methods to construct the commuting partition.
  • A. Problem Abstraction: Optimal clique-clique ordering is intractable because it requires nested-commutator information, so the paper uses a polynomial-time heuristic based on approximated commutators.The heuristic relies on the commutation graph rather than computing the full nested expansion.
  • A. Problem Abstraction: The heuristic greedily grows trees from inter-clique edge information, treats root-to-leaf paths as candidate permutations, and selects the permutation with the smallest summed magnitude.For M cliques, the stated runtime is O(M^4) and it produces O(M^2) candidate permutations.

VI. THEORETICAL ANALYSIS ON GROUP-COMMUTATION ORDERING

Group-commutation ordering can reduce Trotter-error bounds by keeping commuting terms together, although a strict advantage over naive ordering is not proven without complete commutation and magnitude information.

  • Setup: The method partitions Hamiltonian terms into two internally commuting groups and compares the resulting group ordering with other permutations.The framework is introduced for two commuting cliques and is stated to generalize to more groups.
  • Error analysis: The analysis recursively expresses arbitrary Lie-Trotter ordering errors through permutations of Hamiltonian terms and bounds them using operator norms.The bound uses the triangle inequality, norm submultiplicativity, and unitary norm equal to 1.
  • Limitation: The authors do not prove that group-commutation ordering always has smaller error because full commutation and coefficient information are unavailable.The theoretical discussion motivates experimental verification rather than establishing a universal ordering theorem.
  • Theoretical comparison: Group-commutation ordering has a lower upper-bound structure because its error bound does not scale with the number of terms and omits an additional naive-ordering contribution.The analysis identifies these properties as evidence for an advantage in eliminating Trotter errors.
  • Validation: The predicted advantage is tested on molecular Hamiltonians against lexicographic and magnitude orderings using Trotter-fidelity experiments.The experiments are intended to support the theoretical intuition with real molecular Hamiltonians.

VII. EXPERIMENTAL DEMONSTRATION OF GROUP-COMMUTATION ORDERING

Experiments show that grouping commuting Pauli terms can preserve or improve process fidelity, while clique permutations and a heuristic materially affect the result. For CO2, the heuristic reaches constant process fidelity 1.0, overlapping magnitude ordering.

  • A. Methodology: Group ordering achieves perfect fidelity for the two-qubit example, whereas random ordering oscillates between 0 and 1 because of Trotter errors.The grouped terms form two mutually commuting collections whose combined commutation enables the exact circuit in this example.
  • D. Result Discussion: Perfect fidelity is not expected for typical Hamiltonians because commuting groups generally fail to commute after coefficients are included.The two-qubit perfect-fidelity example therefore represents a special case rather than the general molecular setting.
  • B. Benchmarking of Molecular Hamiltonian: The experiments evaluate molecular Hamiltonians by constructing circuits for clique permutations with Trotter step t = 0.01 and Trotter number r = 10.LiH is used as the detailed example, with other molecules reported as behaving similarly.
  • B. Benchmarking of Molecular Hamiltonian: For LiH, the best clique permutations achieve fidelities on a par with magnitude ordering across the enumerated commuting-clique permutations.The benchmark partitions 26 Pauli terms into four commuting cliques and evaluates all 24 clique permutations.
  • C. Effects of Clique-Clique Ordering Heuristics: Process fidelity reaches a constant 1.0 for CO2 when the clique-clique heuristic is used, overlapping the magnitude-ordering result.Without the heuristic, max-commute-tsp process fidelity varies over time; the heuristic is reported to behave similarly across benchmark Hamiltonians.

D. Result Discussion

The discussion connects clique grouping to gate-cancellation opportunities and compares star and ladder circuit implementations. An ancilla-assisted star construction can bypass cancellation restrictions and produce substantial CNOT reductions.

  • D. Result Discussion: Group-commutation ordering is preferable for gate optimization because terms can be reordered within cliques, unlike coefficient-determined magnitude ordering.This flexibility supports choosing neighboring Pauli terms that enable cancellations.
  • 2. Cancellation of Multiqubit Gates: The star implementation permits CNOT cancellation in an example where the ladder implementation cannot cancel the corresponding gates without changing the circuit output.Both implementations produce identical outputs in general, but their cancellation opportunities differ.

2. Restriction II

The gate-cancellation problem is modeled as ordering Pauli strings by transition costs, then approximated through a TSP-based Hamiltonian path. The formulation captures cancellations between neighboring circuit subcircuits but remains computationally hard exactly.

  • 1. Bypassing the Restrictions: The ancilla-assisted star construction cancels six middle CNOT gates in the ZZZZZZ and ZXZXZX example despite restrictions blocking cancellation in the original star and ladder circuits.The modification adds four CNOT gates and one ancilla but achieves six cancellations in that example.
  • 2. Restriction II: A suitable Pauli-string permutation reduces CNOT count because neighboring exponential subcircuits can cancel gates in their transition zones.Cancellation requires matching control and target qubits together with compatible single-qubit gates.
  • 2. Restriction II: The corrected CNOT distance measures the transition-zone CNOT cost between neighboring Pauli strings after gate cancellation.It accounts for positions where both differing Pauli characters generate CNOTs, avoiding the undercount of ordinary Hamming distance.
  • IX. GATE CANCELLATION VIA TSP: TSP converts Pauli-string ordering into a shortest Hamiltonian-path problem by assigning pairwise distances equal to CNOT transition costs.A virtual zero-cost node converts the path objective into a cycle formulation before removing that node.
  • IX. GATE CANCELLATION VIA TSP: Exact TSP optimization is impractical for large instances because TSP is NP-hard, despite a Bellman-Held-Karp algorithm with O(k2^k) time.The paper therefore motivates heuristics and approximation algorithms for polynomial-sized quantum circuits.

A. TSP Approximation

The paper approximates gate-cancellation ordering as a metric TSP, enabling Christofides’ algorithm to produce an efficient 1.5-approximation.

  • A. TSP Approximation: Because exact TSP is NP-hard and lacks a guaranteed constant-ratio polynomial-time approximation in general, the metric structure is essential here.The paper uses Christofides’ algorithm only after establishing metricity.
  • A. TSP Approximation: The CNOT-distance metric follows from proving non-negativity of each coordinate-wise contribution to the triangle-inequality expression.The proof handles the three possible values of the third term: 0, -1, and -2.
  • A. TSP Approximation: 1.5x is the CNOT-cost bound for Christofides’ ordering relative to the optimal TSP ordering.The underlying CNOT-distance graph is shown to satisfy the triangle inequality, making it metric.
  • A. TSP Approximation: The shortest Hamiltonian-path construction cannot directly use the virtual-node bijection because the added zero-cost edges would violate the triangle inequality.The proposed workaround first approximates TSP, then deletes the most expensive edge, introducing two approximation levels.

B. Advantage Over Lexicographic Ordering

TSP ordering can substantially reduce CNOT cost compared with lexicographic ordering, while max-commute-tsp retains high process fidelity by applying TSP within commuting cliques.

  • B. Advantage Over Lexicographic Ordering: 62 CNOTs are required with the TSP route, versus 112 for lexicographic ordering and 180 without cancellation.This four-qubit example demonstrates the direct gate-saving advantage of TSP reordering.
  • B. Advantage Over Lexicographic Ordering: O(N log N) CNOTs replace O(N^2) for TSP in the constructed asymptotic example, whereas lexicographic ordering follows an unfavorable sequence.TSP ignores the index-prefix bottleneck and keeps adjacent PXZ(i) strings at unit Hamming distance.
  • B. Advantage Over Lexicographic Ordering: The asymptotic TSP advantage is demonstrated by a pathological construction, while future work targets empirical and heuristic-TSP comparisons.The cost function could also incorporate single-qubit cancellations or hardware constraints, although such costs may cease to be metric.
  • B. Advantage Over Lexicographic Ordering: Lexicographic ordering can show greater single-circuit cancellation, but its poorer process fidelity may require larger Trotter numbers that erase those savings.Max-commute-tsp necessarily sacrifices some cancellation because it optimizes only within commuting cliques.
  • B. Advantage Over Lexicographic Ordering: Max-commute-tsp outperforms max-commute-lex in gate cancellation while maintaining high process fidelity across the many-term regime.Within relatively small commuting cliques, the TSP heuristic produces stronger cancellation than lexicographic ordering.

X. COMBINED BENCHMARKING

The combined benchmarks evaluate ordering strategies under noisy simulations and trapped-ion experiments across varied initial states. Max-commute-tsp generally achieves lower noisy-simulation infidelity while balancing physical and algorithmic errors.

  • X. COMBINED BENCHMARKING: The benchmarks cover 156 molecular Hamiltonians, three initial states, four error rates, and six trapped-ion experiments.The experiments use 7- and 11-qubit processors, with entangling-gate errors near 2%.
  • X. COMBINED BENCHMARKING: For the entangled initial state, max-commute-tsp produces lower average infidelity and minimum infidelities 1.2%, 2.4%, 3.6%, and 6.7% below the alternatives as error increases.The evaluation uses a depolarizing channel on two-qubit gates and compares lexicographic, magnitude, and max-commute-tsp orderings.
  • X. COMBINED BENCHMARKING: The trapped-ion experiments confirm the noisy-simulation results while exposing the continuing impact of algorithmic errors on current NISQ processors.For several molecules, magnitude ordering can outperform lexicographic despite producing deeper circuits and higher process fidelity.
  • X. COMBINED BENCHMARKING: 20.3% smaller Hellinger-infidelity ranges are produced by max-commute-tsp for equal-superposition initial states.In the low-error regime, magnitude and max-commute-tsp outperform lexicographic ordering, while minimum infidelities remain comparable.
  • X. COMBINED BENCHMARKING: The equal-superposition results can show decreasing infidelity at higher noise because the noisy output increasingly resembles the ideal nearly uniform final state.The paper attributes strategy differences in this setting to average process fidelities.
  • X. COMBINED BENCHMARKING: 1.1%, 1.6%, 2.6%, and 3.0% lower minimum infidelities are obtained by max-commute-tsp across the tested error levels.For some Hamiltonians, the improvement reaches 58% over lexicographic and 11% over magnitude ordering.

XI. APPENDIX

The appendix establishes the algebraic result that mutually commuting Hermitian terms can be exponentiated as a product of individual exponentials, supporting commuting-group manipulation.

  • XI. APPENDIX: For commuting matrices A and B, the binomial expansion of (A + B)^n has the same rearrangement structure as the scalar binomial theorem.Commutation permits arbitrary rearrangement of A and B within each product string.
  • XI. APPENDIX: A multiplication series of pairwise commuting matrices can be expanded by separating the newly added matrix from the preceding product.This corollary extends the two-matrix result inductively.
  • XI. APPENDIX: Applying Taylor expansion and induction yields e^(H_1+...+H_M)t = e^(H_1t)...e^(H_Mt) for mutually commuting Hamiltonian terms.The proof substitutes h_i = -iH_it and adds commuting terms inductively.
  • XI. APPENDIX: The induction step factors e^(H_BEG+h_{P+1}) into e^H_BEG e^h_{P+1}, completing the product decomposition.The commutation of h_{P+1} with all preceding terms enables the factorization.
Loading 2001.05983v3…