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.

    Source: §I · p. 1

  • Method

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

    Source: §I · pp. 2–3

  • 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.

    Source: §I · pp. 2–3

  • 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.

    Source: §I · pp. 2–3

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

    Source: §II · p. 4

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.Source: §I · p. 1

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.Source: §I · pp. 1–2
  • 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.Source: §I · p. 2
  • 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.Source: §I · p. 2

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.Source: §I · p. 2
  • 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.Source: §I · p. 2

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.Source: §I · p. 3
  • χ(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.Source: §I · p. 3

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.Source: §II · p. 3
  • 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.Source: §II · p. 4
  • 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.Source: §II · p. 4

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.Source: §II · p. 4

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.Source: §II · p. 4
  • 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.Source: §II · pp. 4–5
  • 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.Source: §II · p. 5

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.Source: §III · p. 5

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.Source: §III · p. 6
  • 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.Source: §III · p. 6

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.Source: §III · p. 6

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.Source: §IV · pp. 7–8
  • 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.Source: §IV · p. 8

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.Source: §IV · p. 9

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.Source: §V · p. 9
  • 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.Source: §V · p. 9

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.Source: §V · pp. 9–10
  • 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.Source: §V · p. 10

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.Source: Appendix A · p. 11
  • 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.Source: Appendix A · p. 11

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.Source: Appendix A · p. 11

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.Source: Appendix B · p. 11
  • 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.Source: Appendix B · p. 11

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.Source: Appendix B · pp. 11–12

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.Source: Appendix B · p. 12

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.Source: Appendix B · p. 12

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.Source: Appendix C · pp. 12–13

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.Source: Appendix C · p. 12
  • 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.Source: Appendix C · p. 12

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).Source: Appendix C · p. 12
  • 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.Source: Appendix C · pp. 12–13

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.Source: Appendix C · p. 13
Loading 1506.01396v1…