PaperlayerView exact revision on arXiv

Source-linked AI summary

Trading classical and quantum computational resources

Sergey Bravyi, Graeme Smith, John Smolin

arXiv:1506.01396v1quant-ph

TL;DR

The paper asks whether a small quantum processor can help simulate larger quantum computations without expanding the hardware. It develops hybrid simulations for sparse circuits and Pauli-based computation, then gives a faster classical PBC simulation using stabilizer decompositions, with an exponent of approximately 0.94 instead of 1. The paper also notes that a stronger asymptotic stabilizer-rank lower bound was not derived without assumptions.

  • Problem

    The paper investigates how to add virtual qubits to a limited quantum processor and characterize the resulting classical–quantum resource tradeoff.

  • Method

    The paper uses sparse-circuit decompositions, Pauli-based computation, and low-rank decompositions of magic-state tensor products into stabilizer states.

  • Results

    The paper shows that adding k virtual qubits costs 2^O(kd) for d-sparse computations, 2^O(k) for PBCs, and classical PBC simulation runs in time 2^αnpoly(n) with α ≈ 0.94.

  • Takeaways & Limitations

    Hybrid quantum-classical computation can extend sparse-circuit and PBC computations beyond the available quantum hardware, while PBCs also admit a faster-than-brute-force classical simulation.

  • Takeaways & Limitations

    The paper was unable to derive a super-polynomial lower bound for χ_n directly without assumptions.

Abstract

from arXiv · show

We propose examples of a hybrid quantum-classical simulation where a classical computer assisted by a small quantum processor can efficiently simulate a larger quantum system. First we consider sparse quantum circuits such that each qubit participates in O(1) two-qubit gates. It is shown that any sparse circuit on n+k qubits can be simulated by sparse circuits on n qubits and a classical processing that takes time $2^{O(k)} poly(n)$. Secondly, we study Pauli-based computation (PBC) where allowed operations are non-destructive eigenvalue measurements of n-qubit Pauli operators. The computation begins by initializing each qubit in the so-called magic state. This model is known to be equivalent to the universal quantum computer. We show that any PBC on n+k qubits can be simulated by PBCs on n qubits and a classical processing that takes time $2^{O(k)} poly(n)$. Finally, we propose a purely classical algorithm that can simulate a PBC on n qubits in a time $2^{c n} poly(n)$ where $c\approx 0.94$. This improves upon the brute-force simulation method which takes time $2^n poly(n)$. Our algorithm exploits the fact that n-fold tensor products of magic states admit a low-rank decomposition into n-qubit stabilizer states.

I. INTRODUCTION

The paper studies hybrid quantum-classical computation, showing how small quantum processors can simulate larger sparse-circuit and Pauli-based computations with exponential dependence on added virtual qubits. It also gives a classical PBC simulation faster than brute force by exploiting low-rank stabilizer decompositions.

  • Motivation: Hybrid computation combines a small quantum processor with large-scale classical processing to simulate larger quantum systems.The paper asks how virtual qubits can be added without changing available hardware.
  • Sparse quantum circuits: Sparse circuits are defined by a constant or slowly growing bound on each qubit’s participation in two-qubit gates.The d-sparse model initializes qubits, applies a d-sparse circuit, measures them, and classically processes the outcomes.
  • Sparse quantum circuits: 2^O(kd) repetitions and 2^O(kd)poly(n) classical processing simulate any d-sparse computation on n+k qubits using (d + 3)-sparse computations on n qubits.Theorem 1 assumes n ≥ kd + 1.
  • Sparse quantum circuits: For k = O(1) and d = O(log n), the sparse-circuit simulation has polynomial quantum and classical running times.The paper presents this regime as an example where hybrid simulation is more efficient than classical simulation alone.
  • Pauli-based computation: PBC consists of non-destructive measurements of n-qubit Pauli operators, followed by polynomial-time classical processing of the measured eigenvalues.The paper states that PBC has the same computational power as standard circuit-based quantum computing.
  • Pauli-based computation: 2^O(k) repetitions and 2^O(k)poly(n) classical processing simulate a PBC on n+k qubits using PBCs on n qubits.This is the paper’s virtual-qubit result for Pauli-based computation.
  • Classical PBC simulation: O(n2^n) is the brute-force classical cost for simulating an n-qubit PBC, but the paper proves a 2^αnpoly(n) algorithm with α ≈ 0.94.The improved method uses low-rank decompositions of tensor products of magic states into stabilizer states.
  • Classical PBC simulation: χ(H⊗2) = 2 yields χ_n ≤ 2^n/2, while χ_6 ≤ 7 establishes β = log_2(7)/6 ≈ 0.468 for the improved bound.Stabilizer rank is the minimum number of stabilizer states in a linear decomposition of a quantum state.

II. DISCUSSION AND PREVIOUS WORK

The paper places its stabilizer-rank simulation method alongside earlier classical simulation techniques, tensor-decomposition ideas, and open questions about magic-state decompositions and asymptotic scaling.

  • Previous simulation methods: Theorem 2 and Theorem 4 yield a classical simulation time of 2^0.94m poly(n) for Clifford+T circuits with m T-gates, improving on an earlier 2^4m poly(n) method.The comparison uses the transformation of circuits with m T-gates into PBCs and the paper’s stabilizer-rank simulation result.
  • Previous simulation methods: Earlier stabilizer-frame methods used pairwise orthogonal stabilizer decompositions, whereas this work studies more general decompositions and applies them to magic states.The paper identifies this distinction as a difference from prior work by Garcia, Markov, and Cross.
  • Previous simulation methods: A related Wigner-function approach gives time approximately 2^0.543n poly(n), but only for nonadaptive PBCs measuring exclusively X-type or Z-type Pauli operators.The restricted model is not known to be universal for quantum computation.
  • Connections: The sparse-circuit proof can be interpreted as tensor contraction: smaller quantum circuits estimate individual tensor entries before classical addition.This connects the method to tensor-network representations of quantum circuits.
  • Open questions: The paper conjectures that |H⟩ may have the smallest stabilizer rank among all non-stabilizer single-qubit states.It also reports matching stabilizer ranks for |H⟩^⊗n and |R⟩^⊗n through n = 6 and conjectures equality for all n.
  • Open questions: The known lower bound χ_n ≥ Ω(n^1/2) is weaker than the conjectured χ_n ≥ 2^Ω(n), and the authors cannot derive the stronger bound without assumptions.The paper notes that χ_n ≤ 2^o(n) would imply sub-exponential classical simulation for constant-depth Clifford+T circuits.
  • Open questions: Approximate stabilizer decompositions would need precision at least 2^-Ω(n), and it remains unclear whether they can substantially reduce rank.This requirement arises because particular measurement outcomes may have exponentially small probability.

III. SPARSE QUANTUM CIRCUITS

Sparse quantum circuits can be decomposed across k and n qubits, allowing an n+k-qubit computation to be estimated using smaller sparse circuits and classical processing exponential only in k.

  • Circuit decomposition: A d-sparse circuit on k+n qubits decomposes into 2^O(kd) tensor-product terms V_α ⊗ W_α, with both component circuits d-sparse.The decomposition expands cross-partition two-qubit gates in the Pauli basis.
  • Interference estimation: The simulation reduces to smaller W_α circuits and interference terms between pairs of them, estimated using a controlled SWAP-test-like circuit.The auxiliary circuit uses a control qubit and final computational-basis measurements.
  • Interference estimation: The estimator σ′_{y,α,β} is unbiased for the real part of ⟨φ_α|Π(y)|φ_β⟩ and is sampled from a sparse quantum computation.It equals 1 exactly when b = 0 and f(yz) = 1; otherwise it takes the opposite value.
  • Simulation cost: 2^O(kd) repetitions of (d+3)-sparse circuits on n qubits suffice, provided n ≥ kd+1.Swapping the control qubit distributes its larger interaction load across the available qubits.

IV. STABILIZER RANK AND CLASSICAL SIMULATION OF PBC

The classical simulation of Pauli-based computation uses stabilizer decompositions of magic states and efficient evaluation of stabilizer-state overlaps, reducing the exponential base below brute force.

  • Classical simulation: Stabilizer-state projector overlaps can be computed exactly in O(n^3) time, enabling exact evaluation of each term in the probability expansion.The method reduces the relevant sums to degree-two polynomial sums over binary variables.
  • Classical simulation: For a k-qubit decomposition with χ stabilizer terms, PBC outcome probabilities are computable in O(χ^{2n/k}n^3) time.The algorithm enumerates pairs of tensor-product stabilizer terms and evaluates their overlaps.
  • Result: The six-qubit decomposition requires non-symmetric stabilizer states because |H⟩^⊗6 is not in the span of symmetric six-qubit stabilizer states.For n ≤ 5, the paper reports decompositions formed by symmetric stabilizer states.

V. ADDING VIRTUAL QUBITS TO A PBC

Pauli-based computation can represent Clifford+T circuits using magic-state measurement gadgets, enabling virtual-qubit removal through stabilizer decompositions and classical recombination.

  • PBC representation: Each T gate is replaced by a gadget using one ancillary magic state, Pauli measurements, and a measurement-dependent Clifford correction.The four measurement outcomes produce T, ZT, T^-1, or ZT^-1 before correction.
  • PBC representation: Commuting Clifford operations toward the end converts the resulting generalized PBC into standard PBC measurements on the enlarged register.Anticommuting Pauli measurements can be replaced by uniform sampling plus a discardable Clifford correction.
  • Virtual qubits: A k-qubit stabilizer decomposition of the initialized magic states expresses the larger PBC probability as a linear combination of PBCs on n qubits.Each stabilizer initialization can be converted to |0⟩ initialization using a Clifford unitary and updated Pauli measurements.
  • Virtual qubits: Using χ = 3^k terms for k magic-state copies gives classical processing cost 2^O(k) while the quantum component remains an n-qubit PBC.The estimator is sampled by repeating n-qubit PBCs χ times, with variance controlled by the decomposition coefficients.

APPENDIX A

Appendix A evaluates quadratic exponential sums by transforming their quadratic form into blocks, isolating linear variables, and classifying the resulting sum magnitudes and phases.

  • Quadratic-form reduction: The quadratic Boolean form is represented by a symmetric zero-diagonal matrix H that is independent of the linear-function label.An invertible binary change of variables transforms H into block-diagonal form.
  • Quadratic-form reduction: If the transformed linear function contains a variable outside the nonzero blocks, summation over that variable cancels the corresponding contribution.This reduces the sum to values determined by the rank of H.
  • Result: The resulting exponential sum is either zero or a power of two times an eighth root of unity, with the power determined by the matrix rank.The appendix gives the general form ⟨f⟩ = 2^{p/2}ω^m and computes it in O(n^3) time.

APPENDIX B

The appendix develops a Monte Carlo simulated-annealing method for finding low-rank stabilizer decompositions, specialized to real stabilizer states for |H⟩^⊗n. It reports decompositions whose term counts upper-bound stabilizer rank and conjectures their optimality.

  • Numerical decomposition method: Exhaustive search is impractical because the set of pure n-qubit stabilizer states grows as 2^(1/2+o(1))n^2.The algorithm therefore uses a Monte Carlo random walk over χ-tuples.
  • Numerical decomposition method: The method searches χ-tuples of n-qubit stabilizer states by maximizing the norm of the projector onto their span.A decomposition exists exactly when the maximum objective value reaches 1.
  • Simulated annealing: Each Monte Carlo move replaces one stabilizer state with a normalized projection c(I + P)φ_a, which preserves stabilizer states.Moves that improve the objective are accepted, while others follow the specified annealing acceptance rule.
  • Real-state restriction: Because |H⟩^⊗n has real computational-basis amplitudes, the search can be restricted to real stabilizer states.The update remains real when the Pauli operator contains an even number of Y operators.
  • Numerical results: The number of terms χ in each decomposition provides an upper bound on the stabilizer rank χ_n.The appendix conjectures that the displayed decompositions, including the |H⟩^⊗6 decomposition, are optimal.

APPENDIX C

The appendix establishes a lower bound on the stabilizer rank of |H⟩^⊗n and develops a related construction separating stabilizer rank from T-count. It also sketches a route toward stronger, potentially exponential lower bounds.

  • Lower bound for magic states: χ_n = Ω(n^1/2) is proved for the stabilizer rank of |H⟩^⊗n.The bound follows by combining a T-count-based inequality with a constructed family of states.
  • T-count and stabilizer rank: The T-count τ(φ) is the minimum number of T-gates needed to prepare φ using Clifford gates, T-gates, and postselective Pauli measurements.This definition supports relating state preparation cost to stabilizer rank.
  • T-count and stabilizer rank: A T-count-τ state can be expressed as a linear combination of χ_τ stabilizer states because each T-gate consumes one magic state.Clifford operations and postselective Pauli measurements do not increase stabilizer rank.
  • A separating state family: The constructed state φ_n has 2^n distinct computational-basis amplitudes, while any stabilizer state has O(1).Consequently, any decomposition of φ_n into χ stabilizer states requires χ(φ_n) = Ω(n).
  • A separating state family: Each θ_k can be prepared with T-count O(k), so φ_n has total T-count O(n^2).The construction uses a multiple-control CNOT implemented with O(k) Toffoli gates, each realizable with seven T-gates.
  • Potential stronger bound: In the special case of pairwise orthogonal stabilizer states, the appendix obtains the stronger bound χ ≥ 2^Ω(n).This follows from the overlap bound δ_n ≤ 2^-Ω(n) and Gram-matrix conditioning with g_min = 1.
Loading 1506.01396v1…