A fundamental challenge in quantum information science is certifying that an n-qubit state
ρprepared in the lab closely matches a target state
∣ψ⟩. Previous approaches to this problem often require deep quantum circuits, exponentially many single-qubit measurements, or are limited to specific state families. In this work, we introduce a new method that leverages a connection between state certification and the mixing time of a random walk, allowing almost all n-qubit target states, including those with exponential circuit complexity, to be certified with only
O(n2)single-qubit measurements. Our protocol is broadly compatible with various experimental platforms and has applications in benchmarking quantum systems, optimizing quantum circuits, and efficiently learning and verifying representations of quantum states—such as neural networks and tensor networks—using only single-qubit measurements. Moreover, these verified representations enable the efficient prediction of highly non-local properties of
ρthat would otherwise require an exponential number of measurements.
Negativity in a quasiprobability representation is typically interpreted as an indication of nonclassical behavior. However, this does not preclude states that are non-negative from exhibiting phenomena typically associated with quantum mechanics---the single qubit stabilizer states have non-negative Wigner functions and yet play a fundamental role in many quantum information tasks. We seek to determine what other sets of quantum states and measurements of a qubit can be non-negative in a quasiprobability distribution, and to identify nontrivial groups of unitary transformations that permute the states in such a set. These sets of states and measurements are analogous to the single qubit stabilizer states. We show that no quasiprobability representation of a qubit can be non-negative for more than two bases in any plane of the Bloch sphere. Furthermore, there is a unique set of four bases that can be non-negative in an arbitrary quasiprobability representation of a qubit. We provide an exhaustive list of the sets of single qubit bases that are non-negative in some quasiprobability distribution and are also closed under a group of unitary transformations. This list includes two nontrivial families of three bases that both include the single qubit stabilizer states as a special case. For qudits, we prove that there can be no more than
2d2 states in non-negative bases of a
d-dimensional Hilbert space in any quasiprobability representation. Furthermore, these bases must satisfy certain symmetry constraints, corresponding to requiring the bases to be sufficiently different from each other.
As one might expect, having some way to represent and manipulate qubits is a basic requirement of any quantum computer. For a single qubit the state vector is represented by a 2 × 1 matrix (or vector), and in other areas of quantum mechanics such state vectors are referred to as spinors. Before we move to more complex qubit interactions, it is useful to introduce another representation of a quantum state, known as a density matrix or density operator. The density matrix is a generalization of the state vector representation. Since in quantum computing we actually take measurements, we obtain estimates of the state vector components by taking the averages of large numbers of measurements, rather than doing calculations involving the Pauli matrices.