Source-linked AI summary
Quantum circuits and low-degree polynomials over F_2
Ashley Montanaro
TL;DR
The paper asks how quantum circuits and low-degree polynomials over F2 can be connected. It constructs a circuit–polynomial correspondence, uses it to establish classical hardness results and simulation methods, and identifies width computation as a practical boundary for approximation.
Problem
The work investigates a simple connection between quantum-circuit amplitudes and counting zeroes or gaps of low-degree polynomials over F2.
Method
It maps circuits using Hadamard, Z, CZ, and CCZ gates to degree-3 polynomials, then transfers methods between quantum circuits and classical polynomial algorithms.
Results
The correspondence yields #P-hardness results for computing polynomial gaps, including degree-3 polynomials with each variable appearing in at most three terms, and classical simulation algorithms for certain circuits.
Takeaways & Limitations
Quantum-circuit concepts can prove classical complexity results, while polynomial structure can provide classical simulation techniques for quantum circuits.
Takeaways & Limitations
Efficiently finding a circuit with minimum width w(f), or even width within O(log n) of minimum, is not known and determining w(f) itself could be NP-complete.
Abstract
from arXiv · showhide
In this work we explore a correspondence between quantum circuits and low-degree polynomials over the finite field F_2. Any quantum circuit made up of Hadamard, Z, controlled-Z and controlled-controlled-Z gates gives rise to a degree-3 polynomial over F_2 such that calculating quantum circuit amplitudes is equivalent to counting zeroes of the corresponding polynomial. We exploit this connection, which is especially clean and simple for this particular gate set, in two directions. First, we give proofs of classical hardness results based on quantum circuit concepts. Second, we find efficient classical simulation algorithms for certain classes of quantum circuits based on efficient algorithms for classes of polynomials.
1 Introduction
The paper develops a simple correspondence between quantum circuits and low-degree polynomials over F2, using it both to prove classical hardness results and to derive classical simulation algorithms.
- Quantum computation can serve as a theoretical tool for studying science and mathematics even without a large-scale general-purpose quantum computer.
- The work associates quantum circuit amplitudes with counting zeroes of low-degree polynomials over F2.The chosen gate set makes this correspondence especially simple.
- Quantum-circuit ideas yield proofs of classical computational-complexity results for counting polynomial zeroes.
- Classical results about polynomials yield new algorithms for simulating classes of quantum circuits.
- The paper uses a Hadamard, Z, CZ, and CCZ gate set, shifting prior Toffoli-and-Hadamard formulations toward a single-polynomial representation.Toffoli gates are equivalent to CCZ gates conjugated by a Hadamard on the target qubit.
- The correspondence is presented as an accessible bridge between quantum-circuit concepts and classical computational complexity for physicists and computer scientists.
2 Circuits and polynomials
The paper maps circuits built from Hadamard, Z, CZ, and CCZ gates to degree-3 polynomials over F2, with amplitudes determined by the polynomial gap. The mapping is non-unique, supports width-based analysis, and underlies hardness and simulation results.
- The circuit family uses Hadamard, Z, controlled-Z, and controlled-controlled-Z gates, with circuits arranged to begin and end with Hadamard columns.
- The central identity relates the amplitude ⟨0|C|0⟩ to gap(fC), the difference between the numbers of zeroes and ones of the corresponding polynomial.For the Figure 1 example, gap(fC) = 16 and ⟨0|C|0⟩ = 1/2.
- Diagonal Z, CZ, and CCZ gates contribute linear, quadratic, and cubic monomials, respectively, producing a degree-3 polynomial over F2.
- Internal Hadamard gates are replaced using ancilla-based controlled-Z gadgets, adding one polynomial variable per internal Hadamard and a normalization factor.The resulting circuit uses n = ℓ + h qubits, where h is the number of internal Hadamards.
- 2.1 Basic observations: A polynomial can correspond to multiple circuits because diagonal gates can be reordered and some controlled-Z gates and Hadamards are interchangeable.Figure 3 gives two circuits corresponding to x1x2.
- 2.1 Basic observations: Every degree-3 polynomial without a constant term has a corresponding circuit on n qubits, constructed by associating variables with qubits and monomials with gates.
- 2.1 Basic observations: The correspondence also gives the bound |gap(fC)| ≤ 2^n/2+ℓ/2 when fC corresponds to a circuit on ℓ qubits.This follows from the amplitude identity and the unitary bound on quantum amplitudes.
- 2.1 Basic observations: The minimum number of qubits among circuits corresponding to f defines its quantum circuit width w(f), which can differ substantially between polynomials.The chain polynomial x1x2 + x2x3 + ··· + xn−1xn has width 1, while a cited family has width n.
3 Computational complexity
The paper frames polynomial counting within computational complexity, then uses the circuit–polynomial correspondence to establish exact and approximate hardness results and identify regimes for classical simulation.
- Complexity background: #P consists of counting problems expressible as Circuit Counting, and many physical and mathematical problems are #P-hard.Examples include Ising model partition functions, Jones and Tutte polynomials, and exact computation of 0-1 matrix permanents.
- Exact computation: Computing the gap of degree-3 polynomials over F2 is #P-hard, via the correspondence between polynomial gaps and quantum circuit amplitudes.The proof reduces exact amplitude computation for suitable quantum circuits to gap computation.
- Exact computation: Degree-3 gap computation remains #P-hard when every variable appears in at most 3 terms.Inserting pairs of Hadamards preserves the circuit unitary while relabelling variables to limit term appearances.
- Approximate computation: Classical simulation based on a circuit acting on ℓ qubits computes gap(f) exactly in O(2^2ℓ poly(n)) and approximates it in O(poly(n)/ε^2).Matching the accuracy of an optimal quantum circuit yields runtime O(2^(n−w(f)) poly(n)); super-polynomial quantum speedup is unavailable when w(f) ≥ n−O(log n) or w(f) ≤ O(log n).
- Quantum circuit width: Most degree-3 polynomials have high quantum circuit width: the probability that w(f) ≤ n−3 is at most 2^((-3n+1)/2), an exponentially small fraction.Thus the circuit approach generally cannot approximate gaps significantly more efficiently than the classical method on the basis of width alone.
- Quantum circuit width: Quantum circuit width is not determined tightly by hypergraph chromatic number: χ(G(f)) ≤ 2^w(f) can be tight, yet χ(G(f)) = 2 while w(f) = n/2 for an infinite family.This demonstrates that low chromatic number does not always imply low circuit width.
4 Polynomials and simulation of quantum circuits
The section develops classical simulation algorithms by reducing circuit amplitudes to polynomial gaps, then exploiting structural simplicity such as small hitting sets, few variables, or linear transformations.
- Simulation by hitting sets: gap(f) can be computed in time O(2^|S| poly(n)) when S hits every degree-3 term.Fixing variables in S reduces the remaining polynomials to degree at most 2.
- Simulation by hitting sets: A polynomial-time 3-approximation to the minimum hitting set yields gap(f) computation in time 2^O(h(f)) poly(n).Finding a better approximation is NP-hard assuming the Unique Games Conjecture.
- Simulation by hitting sets: The resulting circuit simulation generalizes non-Clifford-gate methods because circuits with many CCZ gates can still have a small hitting set.The construction maps a circuit C to f_C′ with h(f_C′) ≤ 2h(f_C); Figure 4 gives such a circuit with hitting set size 1.
- Simulation by linear transformations: Nonsingular linear transformations preserve degree 3 and gap(f), while potentially changing quantum circuit width and exact-computation efficiency.For example, a transformation maps x_1 + ··· + x_n, of width n, to x_1, of width 1.
- Simulation by linear transformations: If some linear transformation makes f_C depend on v variables, the amplitude ⟨0|C|0⟩ can be computed exactly in time O(2^v poly(ℓ)).This follows by evaluating the transformed polynomial over all assignments to its v variables.
5 Conclusions
The paper investigates the circuit–polynomial correspondence over finite fields and uses it to obtain classical hardness results and classical simulation algorithms for certain quantum circuits.
- 5 Conclusions: The correspondence between quantum circuits and low-degree polynomials yields classical hardness results and ideas for classical algorithms simulating quantum circuits.The conclusion identifies further directions involving circuit width, Reed–Muller codes, and other simulation techniques.