Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
We introduce the 1/2BQP_1 restricted model, where a quantum server provides random computational-basis inputs revealed post-execution and a single output bit, to enable public quantum computation while limiting cryptanalytic capabilities. This model is conjectured to prevent polynomial-time classical clients from factoring RSA moduli, even with arbitrary circuits and system sizes, by making quantum factoring stages classically simulable and obstructing rational reconstruction attacks. The model retains DQC1 applications and proposes a candidate for separating 1/2BQP_1 from DQC1 via classical testing of quantum spin dynamics predictions.
A single output bit from a quantum computer, combined with random inputs, may be enough to unlock quantum advantage for scientific tasks without enabling cryptanalysis.
Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power. We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit. This interface permits arbitrary circuits and system sizes. We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli. The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions. We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics. We argue security in two steps. First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call. This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions. Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit. Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades. Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.