PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas

Jonathan Welch, Daniel Greenbaum, Sarah Mostame, Alán Aspuru-Guzik

arXiv:1306.3991v1quant-ph

TL;DR

Constructing diagonal unitaries efficiently is challenging: concatenating circuits for all Walsh operators has gate count O(n2^n). The paper uses the Walsh-operator basis and coefficient selection to build efficient circuits without ancillas; in the Eckart barrier example, truncation uses about 50 gates rather than 125 at 10% accuracy, and the simulations reproduce important scattering features.

  • Problem

    Concatenating circuits for all Walsh operators scales as O(n2^n) gates, motivating shorter implementations of diagonal unitaries.

    Source: §II · p. 4

  • Method

    The paper represents diagonal unitaries with Walsh operators and reduces circuit construction to selecting a short Walsh-series approximation within an error tolerance.

    Source: §III · p. 5, §V · p. 7

  • Results

    At 10% accuracy for the Eckart barrier, coefficient truncation uses approximately 50 gates versus 125 for a partial Walsh series, a greater-than-twofold reduction.

    Source: C. Simulation · p. 7

  • Takeaways & Limitations

    The simulations show that relatively few Walsh functions reproduce important features of the Eckart-barrier scattering problem, including interference fringes.

    Source: C. Simulation · p. 7, §V · p. 8

    The described classical procedure for selecting Walsh coefficients is not efficient because it first requires a high-dimensional Walsh-Fourier transform.

    Source: C. Simulation · p. 6

Abstract

from arXiv · show

The accurate evaluation of diagonal unitary operators is often the most resource-intensive element of quantum algorithms such as real-space quantum simulation and Grover search. Efficient circuits have been demonstrated in some cases but generally require ancilla registers, which can dominate the qubit resources. In this paper, we point out a correspondence between Walsh functions and a basis for diagonal operators that gives a simple way to construct efficient circuits for diagonal unitaries without ancillas. This correspondence reduces the problem of constructing the minimal-depth circuit within a given error tolerance, for an arbitrary diagonal unitary $e^{if(\hat{x})}$ in the $|x>$ basis, to that of finding the minimal-length Walsh-series approximation to the function $f(x)$. We apply this approach to the quantum simulation of the classical Eckart barrier problem of quantum chemistry, demonstrating that high-fidelity quantum simulations can be achieved with few qubits and low depth.

I. WALSH FUNCTIONS AND OPERATORS

This section introduces the mapping between Walsh functions and a basis for diagonal operators.

I. WALSH FUNCTIONS AND OPERATORS

  • The section begins by identifying the mapping between Walsh functions and a basis for diagonal operators.It then proceeds with definitions.Source: §I · p. 2

A. Walsh Functions

Walsh functions form a complete orthonormal basis that can represent functions on a continuous interval or on discretely sampled points. Their connection to representations of the bitwise-addition group links them to a basis for diagonal operators on n qubits.

A. Walsh Functions

  • Walsh functions are a complete orthonormal set on 0 ≤ x < 1, with periodic repetition extending the definition to the real line.The paper specifies indices through the binary expansion of j.Source: A. Walsh Functions · p. 2
  • The Walsh functions whose indices are powers of two are square waves called Rademacher functions, with R_n(x) = (−1)^x_n.The first eight Walsh functions are shown in Paley order, with Rademacher functions marked in red.Source: A. Walsh Functions · p. 2, Figure 1 · p. 2
  • Discrete Walsh functions are obtained by sampling the interval [0, 1) at N = 2^n points and evaluating each Walsh function at those points.The same functional form applies to continuous and discrete x; only the number of bits in x's expansion differs.Source: A. Walsh Functions · p. 2
  • The discrete Walsh-Fourier transform expands sampled function values in the discrete Walsh basis.The Walsh functions are orthonormal in the discrete case.Source: A. Walsh Functions · p. 2
  • Walsh functions are irreducible representations of the group Z^⊗n_2, whose elements correspond to a basis for diagonal operators on n qubits.This identifies the group-theoretic connection underlying the Walsh operator basis.Source: A. Walsh Functions · p. 2

B. Walsh Operators

Walsh operators are tensor products of single-qubit Pauli Z gates and form a basis for diagonal operators. Their action on computational-basis states has Walsh-function eigenvalues, allowing diagonal unitaries to be implemented term by term from a Walsh expansion.

B. Walsh Operators

  • A diagonal unitary on a sampled function f(x) is defined on computational-basis states |k⟩, with f_k = f(x_k) and x_k = kL/N.The discussion sets L = 1 so the sampled points lie in [0, 1).Source: B. Walsh Operators · p. 3
  • Walsh operators are tensor products of single-qubit Pauli Z gates and form a basis for diagonal operators on n qubits.The eigenvalues of these operators in the computational basis are Walsh functions.Source: B. Walsh Operators · p. 3
  • A diagonal operator can be expanded in Walsh operators, and implementing all terms by concatenation scales as O(n2^n) gates.Products of Walsh operators also extend the expansion to d-dimensional systems, with up to d operators tensored across registers.Source: B. Walsh Operators · p. 3
  • Each Walsh operator can be implemented with a rotation on the qubit of the most significant non-zero index bit and paired CNOTs controlled by the other non-zero bits.The rotation is R_z(−2a_j); the CNOTs flank it and target the rotation qubit.Source: B. Walsh Operators · p. 3
  • The gate count tracks the number of nonzero Walsh coefficients, so zero or negligible coefficients can reduce circuit depth.The paper uses Walsh-operator ordering and coefficient sparsity to construct shorter circuits.Source: B. Walsh Operators · p. 3

II. OPTIMAL CIRCUIT CONSTRUCTIONS

For the full set of nonidentity Walsh operators, sequency ordering produces an optimal circuit; for smaller sets, CNOT commutation can reduce gate counts to O(N') in most cases. The construction uses Gray-code order to minimize transitions between adjacent indices.

II. OPTIMAL CIRCUIT CONSTRUCTIONS

  • Concatenating individual circuits for all 2^n−1 Walsh functions costs O(n2^n) gates, while sequency ordering yields the optimal full-set circuit.The full-set construction improves on the non-optimal concatenation by arranging the operators to cancel intervening CNOTs.Source: §II · p. 4, Figure 5 · p. 5
  • Gray-code, or sequency, ordering gives adjacent indices exactly one binary transition, minimizing CNOTs between rotation gates.The CNOT controls correspond to nonzero bits in the XOR of adjacent indices.Source: §II · p. 4
  • For N' < N Walsh operators, CNOT commutation reduces the gate count to O(N') in most cases.Applying the full-set ordering directly is not optimal for smaller sets because adjacent indices may have multiple binary transitions.Source: §II · pp. 4–5
  • 2^(n+1)−3 gates implement all 2^n−1 nonidentity Walsh operators in the optimal circuit.The three-qubit optimal circuit shows cancellation of all but one CNOT between adjacent rotation gates.Source: §II · p. 4, Figure 5 · p. 5

III. EFFICIENT CIRCUITS FOR DIAGONAL UNITARIES

Partial Walsh-Fourier series provide efficient diagonal-unitary circuits by resampling the target function within an error tolerance. Further reducing the number of Walsh terms can often shorten the circuit, while the reported gate-reduction checks for examples extended only up to five qubits.

III. EFFICIENT CIRCUITS FOR DIAGONAL UNITARIES

  • The gate-reduction approach was verified on example cases with up to five qubits; general n-qubit analysis was still in progress.The authors note that the number of removed gates varies by coefficient pattern, with exceptions not changing the tested scaling.Source: §III · p. 5
  • The operator error is at most ε exactly when the phase functions differ by at most ε at every x.The operator error is defined using the spectral norm.Source: §III · p. 5
  • For continuously differentiable f, 2^k resampling points give error at most sup_x|f'(x)|/2^k and O(1/ε) gates when k ≤ n.The resulting gate count is 2^(k+1)−3 and is constant in n when k ≤ n.Source: §III · p. 5
  • Discarding Walsh coefficients below an appropriate bound gives close-to-optimal sparse approximations that can be combined with circuit optimization for minimal depth and width.Finding the shortest Walsh series within tolerance is an integer-programming problem; coefficient thresholding is the simpler approximate procedure described.Source: §III · p. 5

IV. QUANTUM SIMULATION EXAMPLE: ECKART BARRIER

The section analyzes a real-space quantum simulation of tunneling through an Eckart barrier. It presents this chemistry problem as a practical example and a benchmark for simulating quantum dynamics and transition states.

IV. QUANTUM SIMULATION EXAMPLE: ECKART BARRIER

  • The example analyzes tunneling through an Eckart barrier using a numerical implementation of the Wiesner–Zalka real-space algorithm.Source: §IV · p. 6
  • The Eckart barrier is a benchmark in classical computational quantum chemistry for simulating quantum dynamics and reaction transition states.Source: §IV · p. 6
  • The scattering solution can be used to calculate chemical reaction rates.Source: §IV · p. 6

A. Real-space algorithm

The real-space algorithm represents a wavefunction using position eigenstates on a discretized grid. For a time-independent Hamiltonian split into noncommuting kinetic and potential terms, it applies a first-order Trotter formula, with Fourier transforms used to diagonalize the kinetic term.

A. Real-space algorithm

  • The wavefunction is represented in position eigenstates, with each coordinate discretized and encoded in the computational basis.Source: A. Real-space algorithm · p. 6
  • For d dimensions, the representation uses d registers of n qubits each to encode a grid of 2^(dn) points.The passage specifies d = 3m for m particles.Source: A. Real-space algorithm · p. 6
  • A first-order Trotter formula evaluates evolution for a time-independent Hamiltonian H = K(p) + V(x), where K and V do not commute.The Trotter number is t/δt, an integer.Source: A. Real-space algorithm · p. 6
  • Quantum Fourier transforms diagonalize the kinetic-energy operator, while the potential-energy operator is already diagonal in the position representation.Source: A. Real-space algorithm · p. 6

B. Error analysis

Simulation error combines first-order Trotter error with errors in the kinetic and potential propagators. Choosing their tolerances can shorten the gate sequence while preserving an overall error bound.

B. Error analysis

  • E(U, e^(-iHt)) ≤ αtδt + εVt + εKt bounds total simulation error by Trotter error and kinetic- and potential-propagator errors.Here α = ||[V,K]|| is problem-specific; εV and εK bound the respective propagator approximations.Source: B. Error analysis · p. 6
  • The algorithm uses O(poly(n), 1/εV, 1/εK, t/δt) gates when diagonal unitaries are efficient and the QFT uses polynomially many gates.Source: B. Error analysis · p. 6
  • Varying δt, εV, and εK trades total error against gate count; the analysis considers the shortest sequence for one Trotter step.For that step, the task is finding the shortest Walsh series for the approximate potential and kinetic energies at the chosen tolerances.Source: B. Error analysis · p. 6

C. Simulation

The Eckart-barrier simulations use truncated Walsh series to reduce circuit resources. Their fidelity varies with the qubit count and energy-approximation errors, while even the lowest-fidelity run retains key scattering features, including boundary-induced fringes.

C. Simulation

  • For A=1 and a=0.05, a 19-term Walsh series approximates the Eckart barrier to 10% accuracy, with largest Paley index 67 requiring at least 7 qubits.The series keeps the largest coefficients first; the authors describe this as usually close to the fully optimized solution.Source: C. Simulation · p. 6, Figure 6 · p. 7
  • The described coefficient-selection procedure is not efficient because it first computes a high-dimensional Walsh transform, although methods can find best k-term approximations without the full transform.Source: C. Simulation · p. 6
  • For Eckart-barrier approximation, a partial Walsh-Fourier series needs n ≥ 7 for better than 10% accuracy and uses 125 gates; the truncation uses approximately 50, over a factor-two improvement.The truncated circuit has 19 rotation gates.Source: C. Simulation · p. 7
  • Even the lowest-fidelity simulation reproduces important scattering features, including interference fringes, which arise from periodic boundary conditions and are not physical.Source: C. Simulation · p. 7
  • Fidelity assesses the chosen initial states rather than the worst-case error bound; the comparison uses a 10-qubit, maximum-resolution simulation as a proxy for the exact final state.Source: C. Simulation · p. 7
  • At n=7, the simulation uses 19 Walsh functions with εV=10% and εK=3.1%, reaching F=0.9105 against the 10-qubit reference with F=1.Across the reported runs, F=0.9794 at n=8 and F=0.6507 at n=6; the reference uses n=10 and 512 Walsh functions.Source: Figure 7 · p. 7

V. CONCLUSION

The paper establishes Walsh functions as a basis for diagonal operators and uses truncated Walsh-Fourier series to construct approximately minimal-depth circuits. Its Eckart-barrier simulation demonstrates high fidelity without ancillas using few qubits and low depth.

V. CONCLUSION

  • Walsh functions form a basis for diagonal operators, enabling efficient circuits for diagonal unitaries without ancillas.Source: §V · p. 7
  • Truncating the Walsh-Fourier series for f(x) yields an approximately minimal-depth circuit for the diagonal unitary at a specified error tolerance.Source: §V · p. 7
  • The Eckart-barrier tunneling simulation demonstrates high-fidelity quantum simulation with few qubits and low depth.The circuit gate count scales proportionally to the number of Walsh functions in the series.Source: §V · p. 8
Loading 1306.3991v1…