The SPARSIFY algorithm implemented by the code allows for classical simulation of universal quantum computer sample outcomes. The code sparsifies the stabilizer decomposition of a qubit t-tensored T gate magic state to some additive error. This is accomplished by either independent L1 sampling or with correlated L1 sampling to supplement an independent subset, which offers a more efficient decomposition: for a given t, a sparser decomposition is sufficient with correlated L1 sampling to satisfy a given additive error. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. SAND2021-8296 O
SAND2022-3281 O Weak Simulation sparsifies the stabilizer decomposition of a qubit t-tensored T gate magic state to some additive error. It can accomplish this either by independent L1 sampling like in the popular SPARSIFY algorithm or with correlated L1 sampling, which offers a more efficient decomposition. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.
This software improves upon the Clifford gate+T gate magic state strong simulation algorithm by Brayvi and Gosset. It provides a better stabilizer state decomposition that scales as 2^{0.463t}, an improvement over 2^{0.468t}, for t T gate magic states. This code enables simulations of universal quantum computing with that asymptotic scaling cost. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525 SAND2020-14293 O
Universal quantum circuits can be formulated in the Pauli measurement-based formalism as input T gate magic states, Clifford gates, and then multi-Pauli measurements. This code simulates single-Pauli measurements to show some theoretical bounds on the cost of full multi-Pauli measurements. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. SAND2020-14080 O
This is software in Python that simulates the quantum approximate optimization algorithm (QAOA) as described in https://arxiv.org/abs/1411.4028. The software has customization that speeds up simulation and provides interface to the Rapid Optimization Library (ROL) developed at Sandia. SAND2019-8935 M Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.
Bounding the cost of classically simulating the outcomes of universal quantum circuits to additive error
δ is often called weak simulation and is a direct way to determine when they confer a quantum advantage. Weak simulation of the
T+Clifford gateset is
BQP-complete and is expected to scale exponentially with the number
t of
T gates. We constructively tighten the upper bound on the worst-case
L1 norm sampling cost to next order in
t from
O(ξtδ−2) if
δ2≫ξ−t to
O((ξt−t)δ−2) if
δ2≫(ξt−t)−1, where
ξt=2∼0.228t is the stabilizer extent of the
t-tensored
T gate magic state. We accomplish this by replacing independent
L1 sampling in the popular SPARSIFY algorithm used in many weak simulators with correlated
L1 sampling. As an aside, this result demonstrates that the
T gate magic state's approximate stabilizer state decomposition is not multiplicative with respect to
t, for finite values, despite the multiplicativity of its stabilizer extent. This is the first weak simulation algorithm that has lowered this bound's dependence on finite
t in the worst-case to our knowledge and establishes how to obtain further such reductions in
t.