Source-linked AI summary
Learning stabilizer states by Bell sampling
Ashley Montanaro
TL;DR
The paper addresses identifying an unknown n-qubit stabilizer state from copies of the state. Bell sampling produces outcome differences that reveal the stabilizer subspace, followed by Pauli-eigenbasis measurements to determine signs. The algorithm fails with probability at most 2^-n.
Problem
The paper addresses identifying an unknown n-qubit stabilizer state from copies of the state.
Source: LEARNING STABILIZER STATES · p. 2Method
Bell sampling produces outcome differences that reveal the stabilizer subspace, followed by Pauli-eigenbasis measurements to determine signs.
Source: Preliminaries · p. 1, LEARNING STABILIZER STATES · p. 2Results
The algorithm fails with probability at most 2^-n.
Source: LEARNING STABILIZER STATES · p. 2Takeaways & Limitations
The algorithm identifies the state by recovering its stabilizer subspace and the signs of its Pauli generators.
Source: LEARNING STABILIZER STATES · p. 2
Abstract
from arXiv · showhide
We show that measuring pairs of qubits in the Bell basis can be used to obtain a simple quantum algorithm for efficiently identifying an unknown stabilizer state of n qubits. The algorithm uses O(n) copies of the input state and fails with exponentially small probability.
Preliminaries
Bell sampling measures corresponding qubit pairs in the Bell basis, producing a 2n-bit outcome. The preliminaries relate Bell-basis probabilities to overlaps involving Pauli operators and the complex conjugate of the input state.
Preliminaries
- The vec map sends |x⟩⟨y| to |x⟩|y⟩ and preserves inner products, with |σi⟩ defined from vec(σi)/2.The text identifies the Bell basis as an ordered basis of C4 and denotes its vectors using the Pauli matrices.Source: Preliminaries · p. 1
- Bell sampling measures each corresponding pair AiBi in the Bell basis and returns a 2n-bit string.The Bell-basis measurement can be implemented with a circuit followed by computational-basis measurement.Source: Preliminaries · p. 1
- For two copies of |ψ⟩, the squared overlap with a Bell-basis vector is expressed through ⟨ψ|σr|ψ∗⟩.Here |ψ∗⟩ is the computational-basis complex conjugate of |ψ⟩.Source: Preliminaries · pp. 1–2
LEARNING STABILIZER STATES
Bell sampling yields an algorithm for identifying an unknown n-qubit stabilizer state using 5n+2 copies, with O(n3) runtime and exponentially small failure probability. It recovers the stabilizer subspace from differences of Bell outcomes, then measures Pauli eigenvalues to determine the remaining signs.
LEARNING STABILIZER STATES
- Stabilizer states admit a form supported on an affine subspace, with linear and quadratic phase polynomials over F2.The discussion relates the linear phase to a product over a selected subset of coordinates and describes Algorithm 1 as a generalization of Rötteler's [10] result for degree-2 Boolean functions.Source: LEARNING STABILIZER STATES · p. 2
- A stabilizer state is specified by its commuting Pauli subgroup; measuring a basis of T in the corresponding Pauli eigenbases determines the signs needed to identify the state.The subgroup has size 2^n, and each of its elements has the state as a +1 or −1 eigenstate.Source: LEARNING STABILIZER STATES · p. 2
- Bell-sampling outcomes are uniform on a coset of the stabilizer subspace T, so differences from a reference outcome are uniform in T and can span it.The algorithm takes 2n such differences and determines a basis for their span.Source: LEARNING STABILIZER STATES · p. 2
- The algorithm runs in O(n3) time (improvable to O(nω), where ω < 2.373) and fails with probability at most 2^-n, by a union bound over dimension-(n−1) subspaces.Runtime is dominated by basis determination via Gaussian elimination; writing the output alone requires Ω(n2) time.Source: LEARNING STABILIZER STATES · p. 2