8 May 2023 in Nature Physics
11 July 2014 in Information and Inference: A Journal of the IMA
In this paper, we develop a theory of matrix completion for the extreme case of noisy 1-bit observations. Instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question we ask is whether or not it is possible to obtain an accurate estimate of M from this data. In general, this would seem impossible, but we show that the maximum likelihood estimate under a suitable constraint returns an accurate estimate of M when ∥M∥∞ ≤ α and rank(M) ≤ r. If the log-likelihood is a concave function (e.g. the logistic or probit observation models), then we can obtain this maximum likelihood estimate by optimizing a convex program. In addition, we also show that if instead of recovering M we simply wish to obtain an estimate of the distribution generating the 1-bit measurements, then we can eliminate the requirement that M when ∥M∥∞ ≤ α. For both cases, we provide lower bounds showing that these estimates are near-optimal. We conclude with a suite of experiments that both verify the implications of our theorems as well as illustrate some of the practical applications of 1-bit matrix completion. In particular, we compare our programme to standard matrix completion methods on movie rating data in which users submit ratings from 1 to 5. In order to use our program, we quantize this data to a single bit, but we allow the standard matrix completion program to have access to the original ratings (from 1 to 5). Surprisingly, the approach based on binary data performs significantly better.
12 September 2020 in Quantum
Many applications of practical interest rely on time evolution of Hamiltonians that are given by a sum of Pauli operators. Quantum circuits for exact time evolution of single Pauli operators are well known, and can be extended trivially to sums of commuting Paulis by concatenating the circuits of individual terms. In this paper we reduce the circuit complexity of Hamiltonian simulation by partitioning the Pauli operators into mutually commuting clusters and exponentiating the elements within each cluster after applying simultaneous diagonalization. We provide a practical algorithm for partitioning sets of Paulis into commuting subsets, and show that the proposed approach can help to significantly reduce both the number ofoperations and circuit depth for Hamiltonians arising in quantum chemistry. The algorithms for simultaneous diagonalization are also applicable in the context of stabilizer states; in particular we provide novel four- and five-stage representations, each containing only a single stage of conditional gates.
10 December 2024 in Quantum
Error-mitigation techniques such as probabilistic error cancellation and zero-noise extrapolation benefit from accurate noise models. The sparse Pauli-Lindblad noise model is one of the most successful models for those applications. In existing implementations, the model decomposes into a series of simple Pauli channels with one- and two-local terms that follow the qubit topology. While the model has been shown to accurately capture the noise in contemporary superconducting quantum processors for error mitigation, it is important to consider higher-weight terms and effects beyond nearest-neighbor interactions. For such extended models to remain practical, however, we need to ensure that they can be learned efficiently. In this work we present new techniques that accomplish exactly this. We introduce twirling based on Pauli rotations, which enables us to automatically generate single-qubit learning correction sequences and reduce the number of unique fidelities that need to be learned. In addition, we propose a basis-selection strategy that leverages graph coloring and uniform covering arrays to minimize the number of learning bases. Taken together, these techniques ensure that the learning of the extended noise models remains efficient, despite their increased complexity.
18 September 2023 in Physical Review Research
Generating samples from the output distribution of a quantum circuit is a ubiquitous task used as a building block of many quantum algorithms. Here we show how to accomplish this task on a noisy quantum processor lacking full-blown error correction for a special class of quantum circuits dominated by Clifford gates. Our approach is based on coherent Pauli checks (CPCs) that detect errors in a Clifford circuit by verifying commutation rules between random Pauli-type check operators and the considered circuit. Our main contributions are as follows. First, we derive a simple formula for the probability that a Clifford circuit protected by CPCs contains a logical error. In the limit of a large number of checks, the logical error probability is shown to approach the value , where is the number of qubits and is the depolarizing error rate. Our formula agrees nearly perfectly with the numerical simulation results. Second, we show that CPCs are well suited for quantum processors with a limited qubit connectivity. For example, the difference between all-to-all and linear qubit connectivity is only a increase in the number of cnot gates required to implement CPCs. Third, we describe simplified one-sided CPCs, which are well suited for mitigating measurement errors in the single-shot settings. Finally, we report an experimental demonstration of CPCs with up to 10 logical qubits and more than 100 logical cnot gates. Our experimental results show that CPCs provide a marked improvement in the logical error probability for the considered task of sampling the output distribution of quantum circuits.