Peter Shor

Non-Entangled Product States Exhibit Quantum Nonlocality in Local Distinguishability

Researchers demonstrate an orthogonal set of product states for two qutrits that cannot be perfectly distinguished by separated observers using local operations and classical communication (LOCC), despite being non-entangled. A finite gap exists between mutual information from joint measurements and LOCC-restricted measurements on these states. This implies separable quantum channels unrealizable by LOCC, with extensions to three-qubit states classified by local preparation and measurement costs.

Remote State Preparation Halves Classical Communication Cost vs. Teleportation

Remote state preparation (RSP) achieves the same goal as quantum teleportation—transmitting a quantum state—but requires only prior entanglement and one bit of classical communication per qubit asymptotically when the sender knows the state classically. This is half the two bits per qubit needed for teleportation. RSP costs decrease further for known entangled states and exhibits entanglement-classical communication tradeoffs analyzable via quantum channel capacities.

Numerical and Bounded Solutions for Capacities of Noisy Bosonic Broadband Channels

The paper analyzes communication capacities of bosonic broadband channels under loss, white noise, and thermal noise. It delivers a numerical solution for the entanglement-assisted capacity. For classical and quantum capacities, it establishes upper and lower bounds.

Fault-Tolerant Quantum Error Correction via Systematic Procedure for Existing Codes

DiVincenzo and Shor present a simple, systematic error detection and correction procedure applicable to recently developed quantum error-correcting codes, demonstrated explicitly for a 1-to-5 qubit encoding. The resulting quantum networks are fault-tolerant, capable of successful operation despite errors during correction. This construction leverages a new group-theoretic framework unifying known quantum codes.

Lower Bound of 1/16 Bias Proven for Bit-Commitment Quantum Coin Flipping, with 1/4 Achieved via Cheating

Nayak and Shor prove a 1/16 lower bound on bias for quantum coin flipping protocols using bit-commitment frameworks, covering nearly all known protocols. They analyze a multi-round protocol sequence designed to reduce bias but demonstrate an intricate cheating strategy achieving 1/4 bias. This suggests 1/4 may be optimal for such protocols, though their lower bound was later superseded by Kitaev; the work highlights need for advanced proof techniques.

Prior Entanglement Dramatically Boosts Classical Capacity of Noisy Quantum Channels

Prior shared entanglement between sender and receiver can multiply the classical capacity of noisy quantum channels by an arbitrarily large factor relative to unassisted capacity. This enhancement peaks for highly noisy channels with positive classical but zero quantum capacity. Exact formulas are derived for entanglement-assisted capacity of depolarizing and erasure channels in d dimensions; simulations of such channels require equivalent forward classical communication, preserving causality.

Shor's Quantum Error Correction Enables Fault-Tolerant Computation with Logarithmic Error Tolerance

Shor's scheme constructs polynomial-size quantum circuits tolerant to O(1/(log t)^c) inaccuracy and decoherence per gate for t-gate computations, improving over prior O(1/t) bounds. This is achieved by integrating quantum error-correcting codes, previously used for storage and transmission, into the computational process. The approach counters decoherence and gate errors that accumulate in long quantum computations.

Arctic Circle Theorem: Central Disorder in Aztec Diamond Domino Tilings Converges to Circle

In random domino tilings of large Aztec diamonds, the central region of coexisting tile orientations forms a shape arbitrarily close to a circle of radius n/sqrt(2), while outer regions exhibit uniform alignment. This Arctic Circle Theorem is proven using interacting particle systems, specifically a classification of stationary behaviors in a totally asymmetric one-dimensional exclusion process. The result holds for all but a negligible proportion of tilings as n grows.

Shor's Linear Programming Proposal for Computing Quantum Channel Capacities

Peter Shor surveys the known results on information-transmitting capacities of quantum channels, including classical, quantum, and entanglement-assisted variants. He proposes a method to calculate some of these capacities using linear programming techniques. The work, presented as an invited talk, spans 26 pages with 3 figures and was later published in Mathematical Programming.

Lifted Trine States Require Six POVM Projectors for Optimal Accessible Information

Shor introduces lifted trine states, a symmetric trio of qutrit states with distinctive properties. For their equal-probability ensemble, the POVM achieving maximum accessible information demands six projectors. This construction disproves Levitin's conjecture on minimal POVM elements matching the source rank.

Nonadditivity of Bipartite Distillable Entanglement Proven via Bound Entangled Werner States Conjecture

Assuming a conjecture that certain Werner states are undistillable, Shor, Smolin, and Terhal demonstrate that the tensor product of two bipartite states—each with zero distillable entanglement—possesses nonzero distillable entanglement. Their example combines a bound entangled state from an unextendible product basis with a conjectured undistillable Werner state. This nonadditivity implies distillable entanglement is not convex.

Unextendible Product Bases Enable New Constructions of Bound Entanglement with Full Orthogonality Graph Characterization

The paper advances unextendible product bases (UPBs) and uncompletable product bases, introducing a construction for bound entangled states using product bases completable only in locally extended Hilbert spaces. It defines orthogonality graphs for complete UPB characterization in two qutrits and generalizes UPBs to high dimensions and multipartite systems. Additionally, it provides a separability condition for distinguishing orthogonal product states and proves bound entanglement does not enhance distillable entanglement beyond regularized entanglement of formation.

Webinar | Quantum Foundations to Quantum Futures: A Live Conversation With Peter Shor (Qblox)

Steven Chu and Peter Shor: How can quantum tech help climate (The Quantum Kid)

Shor's Algorithm: Quantum Advantage in Integer Factorization

Peter Shor's algorithm leverages quantum mechanics to efficiently factor large integers, a task intractable for classical computers beyond approximately 300 digits. The algorithm's core innovation lies in using the quantum Fourier transform to identify the periodicity of a modular exponentiation sequence, thereby enabling the factorization of N. This capability poses a significant threat to current classical cryptographic systems like RSA.

Graph Representation Unifies Stabilizer Code Construction, Analysis, and Efficient Decoding

Stabilizer codes are represented as structured graphs, bijectively linked to stabilizer tableaus via ZX Calculus for efficient computation. This enables code construction through graph properties, yielding families like [[n, Θ(n/log n), Θ(log n)]] and [[n, Ω(n^{4/5}), Θ(n^{1/5})]] codes. Graph-based analysis extends the quantum Gilbert-Varshamov bound to distance-rate-weight trade-offs and unifies key algorithms—distance approximation, generator selection, decoding—as graph optimization games, with a greedy decoder correcting all recoverable errors for graphs with cycles ≥13.

Quantum Analog of LPN: Learning Stabilizers with Noise Introduces Hard Decoding Problem for Stabilizer Codes

The Learning Stabilizers with Noise (LSN) problem is introduced as the quantum counterpart to the classical Learning Parity with Noise (LPN), involving decoding random stabilizer codes under local depolarizing noise. Polynomial and exponential-time quantum algorithms solve LSN across noise regimes from extremely low to threshold levels. LSN is at least as hard as LPN via reduction, with worst-case to average-case hardness and placement in a unitary synthesis complexity class; applications include quantum bit commitment and limits on learning quantum data.

Novel Algorithms Solve Short Vector Problem in Code-Lifted Lattices with Tunable Approximation via Iteration Control

Introduces algorithms for finding short vectors in lattices from co-dimension k codes over Z_P^d by projecting initial vectors onto dual codewords, sorting projections, and applying pairwise Euclidean reduction for monotonic convergence to zero. For fixed P and d, large input sets enable minimizing iterations to control output length growth geometrically, yielding an approximation scheme for SVP without near-exact SVP reductions, even in high dimensions like 8000. Generalizes to co-dimension k via k-party reductions, providing polynomial-time algorithms with improving approximations as k increases.

Phase Transitions Enhance Topological Gates in Non-Abelian Quantum Computation

The paper defines an anyon tunneling map φ between subphases of the quantum double model D(G) for finite groups G, linking it to Floquet codes and extending the Abelian Floquet code to non-Abelian cases. Phase transitions in temporal and spatial directions increase the diversity of topological gates for modular tensor categories. This approach augments topological quantum computation with subphases and transitions.

ZX Calculus Enables Canonical Compilation of Clifford Encoders for Stabilizer Codes

The paper introduces a quantum compilation algorithm that converts Clifford encoders for stabilizer codes into a unique canonical form within the ZX calculus. It proves the canonicity and efficient reducibility of any such encoder to this form. The resulting ZX diagrams visualize information propagation and entanglement, aiding graph-theoretic design of new stabilizer codes.

Shor's Personal Recollections on Quantum Factoring, Error Correction, and Fault Tolerance Origins

Peter Shor recounts his memories of quantum computation's early development, focusing on discovering the quantum factoring algorithm, quantum error-correcting codes, and fault-tolerant quantum computing. The paper is a 10-page write-up of talks delivered at QC40 (40th anniversary of the 1981 Physics of Computation Conference) and the 2022 Solvay Conference. It provides firsthand historical insights into these pivotal quantum computing milestones from a key pioneer.

Peter Shor Withdraws Quantum Money Paper Due to Critical Calculation Error

Peter Shor and co-authors withdrew their arXiv paper proposing publicly verifiable quantum money via Gaussian superpositions over random lattices. The withdrawal stems from an incorrect calculation of Gaussian ball shifts on page 4. Private communication indicates fundamental flaws in similar quantum money constructions, rendering the scheme unviable.

LOCC Outperforms Bell Pairs for Distinguishing Quantum Product States

Alice and Bob, spatially separated observers, aim to identify a quantum state from multiple possibilities by maximizing correct guessing probability and information gain. LOCC protocols enable optimal discrimination between two product states, surpassing simultaneous measurements. LOCC proves more effective than shared Bell pairs in nearly all cases for distinguishing product states.

New Measures Bound Forward Classical Capacity of Bipartite Quantum Channels

Researchers introduce multiple measures of forward classical communication for bipartite quantum channels, which specialize to known bounds on point-to-point quantum channel classical capacity from prior work. These measures serve as upper bounds on the forward classical capacity of bipartite channels and, in the point-to-point reduction, on classical capacity assisted by classical feedback. Select measures are computable via semi-definite programming, enabling practical evaluation.

OTOC Saturates Faster than Entanglement Entropy in Bottleneck Graphs

In random quantum circuits on graphs with tight bottlenecks like trees, OTOC saturation occurs asymptotically faster than entanglement entropy saturation, decoupling the timescales of these scrambling probes. This counters expectations that mixing time scales with graph diameter. The result rigorously supports slow black hole scrambling, linking to the information paradox, and generalizes OTOC bounds from lattices to arbitrary graphs.

Classical Feedback Does Not Increase Quantum Channel Capacity Beyond Maximum Output Entropy

The classical capacity of any quantum channel with free classical feedback is upper-bounded by the channel's maximum average output entropy. This bound implies no capacity gain from feedback for quantum erasure channels and, under energy constraints, for pure-loss bosonic channels. The proof leverages a novel information measure that is non-increasing under one-way LOCC from receiver to sender and bounded by the channel's maximum output entropy.

Strong Fast Scrambling Conjecture Conflicts with Black Hole Physics and Relativity

Peter Shor analyzes a strengthened version of the fast scrambling conjecture, positing black holes scramble information in O(M log M) time. This version clashes with established black hole properties, implying either superluminal information transfer, non-Hawking radiation carriers, or excessive information in Hawking radiation beyond thermodynamic limits. Such fast scrambling outside the stretched horizon necessitates relativity violations or non-standard physics near the photon sphere.

Resource Theory Quantifies Non-Gaussian Operations with Monotone and Two-Class Classification

Establishes a resource theory for continuous-variable quantum information where Gaussian operations are free and non-Gaussian operations are resources. Defines an entanglement-assisted non-Gaussianity generating power monotone, non-increasing under free super-operations, analytically computable for conditional unitaries. Classifies non-Gaussian operations into finite non-Gaussianity (e.g., photon-number subtraction/addition, Gaussian-dilatable channels) and diverging non-Gaussianity (e.g., binary phase-shift, Kerr nonlinearity) classes, proving not all non-Gaussian channels are Gaussian-dilatable.

Quantum Channels Exhibit Superadditivity in Multi-Resource Trade-off Capacities Despite Additive Single Resources

Quantum channels can display superadditivity in double or triple resource trade-off capacities even when single or double resource capacities are additive. Examples include superadditive classical-quantum capacity for channels with additive classical and quantum capacities. Proof-of-principle conditions are provided, with explicit constructions in most cases, contrasting with prior results where additivity in certain pairs implies triple additivity.

Uncertainty about Physical Processes Amplifies Information's Energetic Value Beyond kT ln 2

Standard information-energy tradeoffs assign kT ln 2 as the fundamental cost per bit exchanged with a thermal reservoir. However, when uncertainty exists about the specific physical process occurring, the energetic value of resolving that information exceeds kT ln 2 per bit. This effect arises in scenarios where information clarifies unpredictable process dynamics, enabling more efficient energy management in acquisition, processing, and erasure.

Optimal Initial States Maximize Free Energy Harvesting in Driven Classical and Quantum Systems

The paper derives conditions for maximizing free energy gain—and thus extractable work—in classical and quantum systems driven by their environment, accounting for preparation costs of the initial state. Necessary and sufficient conditions determine when varying the initial state increases gain, with explicit formulae quantifying improvements over suboptimal states. Optimal state search exhibits easy (high-temperature preparation/extraction) and hard (low-temperature) regimes, demonstrated on an information engine model.

Limited Entanglement Assistance Induces Superadditivity in Additive Classical Quantum Channels

Researchers construct a quantum channel with additive unassisted classical capacity, yet its classical capacity with limited entanglement assistance exhibits superadditivity. This occurs because full entanglement assistance yields an additive capacity, but restricting entanglement across channel uses enables gains from tensoring multiple channels. The result highlights non-intuitive roles of partial entanglement in quantum communication capacities.

Generalized Lattice DFT on Systematic Normal Form Lattices Enables Efficient Approximation and Quantum Sampling

Eldar and Shor define a Discrete Fourier Transform (DFT) on Euclidean lattices in R^n, generalizing the standard DFT on Z^n, applicable specifically to lattices in Systematic Normal Form (SysNF). SysNF lattices, defined by a single homogeneous modular equation with number-theoretic properties, form a dense subset of all n-dimensional lattices and allow efficient approximation of any lattice L. This enables efficient DFT computation on lattices near any L, proven via quantum computing arguments, and yields a quantum algorithm for sampling smooth discrete distributions on lattices, extending discrete Gaussian sampling.

Polylog-Sparse Quantum LDPC Codes Achieve Capacity on Noisy Erasure Channels

Lloyd, Shor, and Thompson construct [[n, k, d]] quantum stabilizer codes that approach the capacity of the quantum erasure channel for erasure probabilities ≥0.33. These codes use polylog-sparse generators with individual weights |S_i| ≤ log^{2+ζ}(n) for any ζ>0, with high probability. The construction demonstrates tightness of Delfosse et al.'s result, enabling capacity-achieving codes with near-constant weights.

PR-Boxes Enable Superior Capacity in Noisy Two-Sender Two-Receiver Interference Channels Over Quantum Entanglement

PR-boxes, representing super-quantum non-local correlations that violate Bell/CHSH inequalities while respecting no-signaling, enhance capacities of specific two-sender two-receiver interference channels beyond quantum entanglement-assisted strategies. In one channel, a shared PR-box enables perfect communication without sender coordination, unachievable classically or with entanglement. A parameterized family of channels shows a strict hierarchy: super-quantum > entanglement-assisted > classical capacities for certain noise levels.

Withdrawn Quantum Algorithm Targets LWE Lattice Decoding Variant Critical to Post-Quantum Crypto Security

Eldar and Shor propose a quantum algorithm using Systematic Normal Form (SysNF) lattices to solve a bounded-distance-decoding variant: distinguish if a vector v is at distance [a/2, a] or ≤ b from lattice L, with a = λ₁(L)/n¹³ and b = λ₁(L)/n¹⁷. This efficiently approximates the decision boundary near the shortest vector length. Achieving a = b = λ₁(L)/√n would undermine LWE cryptosystem security against quantum attacks; the paper was withdrawn shortly after submission.

Additive Capacity Formula for Classical Communication over Noisy Quantum Channels with Receiver-Side Noisy Entanglement

The paper derives an additive capacity formula for classical information transmission over noisy quantum channels using separable sender encoding and receiver-provided noisy entanglement via mixed signal-ancilla states purified by a witness. This formula quantifies the utility of limited or noisy entanglement assistance and simplifies to a closed form for generalized covariant channels. It also upper bounds coherent attack information gain in two-way QKD protocols and implies collective Gaussian attacks are optimal for Gaussian protocols.

Systematic Normal Form Enables Efficient Canonical Representation and Reduction for Arbitrary Lattices

Eldar and Shor introduce the systematic normal form (SNF), a new canonical lattice representation where every lattice has an efficiently computable nearby SNF lattice. Lattice problems solved on the SNF can be efficiently translated back to the original lattice, establishing direct connections to problems like SIS and Approximate GCD. As a key application, SNF yields simplified worst-to-average-case lattice reductions that improve on Ajtai's template in simplicity.

Universal Quantum Computing via Propagating Spin Packets in XY Heisenberg Chains

Proposes a time-independent universal quantum computing scheme using XY Heisenberg spin chains, where qubits are encoded as propagating packets that interact to execute computation. A circuit with g gate blocks on m qubits requires chains of length O(g^{3+δ} m^{3+δ}) for any δ > 0. Achieves vanishingly small error through this "Quantum Plinko Machine" architecture.

Graphs Disconnectable by Few Vertices Enable Efficient Quantum Network Control

Quantum networks modeled by graphs disconnectable into small components by removing a vanishingly small fraction of vertices are efficiently controllable. Universal quantum computation can be performed via a control sequence polynomial in network size while manipulating only a vanishing fraction of subsystems. Finite-dimensional lattices, percolation clusters, and random graphs satisfy this property; moreover, ground state estimation for their Hamiltonians has polynomial classical complexity.

Power-Law Violation of Area Law in Critical Spin Chains via Generalized Motzkin Models

Movassagh and Shor generalize the spin-1 Bravyi-Shor model to integer spin-s chains, constructing local, translationally invariant, frustration-free Hamiltonians with unique ground states represented as superpositions of s-colored Motzkin walks. These models exhibit critical signatures with energy gap scaling as n^{-c} for c ≥ 2, ruling out conformal field theory descriptions. Half-chain entanglement entropy scales as √n to leading order, violating the area law by a power law rather than logarithmic factor.

Three Strategies Boost Quantum Adiabatic Algorithm Success on Hard MAX 2-SAT Instances

Numerical study on 20-qubit Quantum Adiabatic Algorithm applied to random MAX 2-SAT instances with unique optimal assignments shows three strategies improving success probability on hardest cases: shorter total evolution time, excited-state initialization, and inserting a random local Hamiltonian mid-evolution. Success measured by probability of reaching the unique satisfying assignment. These counterintuitive methods consistently enhance performance for challenging instances in the ensemble.

Relativistic QKD Encodes Multiple Bits per Photon for Faster Key Rates

Cotler and Shor propose a relativistic orthogonal states QKD protocol that uses quantum mechanics and special relativity to encode multiple bits on a single photon's spatio-temporal modes. With a single-photon source, it achieves key generation rates exceeding the source's repetition rate, surpassing existing protocols. The protocol includes a security proof and supports implementation over line-of-sight or fiber optic channels.

First Bounds on CHSH_q Game Link Quantum Protocols to Szemerédi-Trotter Incidence Geometry

The paper establishes the first asymptotic and explicit bounds on both classical and entangled values for the CHSH_q game, a finite-field generalization of the CHSH inequality where players output elements in F_q to satisfy a + b = xy. It reveals a novel connection between this quantum game and geometric incidence theory via the Szemerédi-Trotter theorem. Additionally, it resolves a pairwise independent variant of Information Causality posed by Pawlowski and Winter, yielding a concise proof for the entangled value upper bound.

Concatenated Ternary Codes Yield Superior Nonlinear and Linear Constructions for Asymmetric Channels

New generalized concatenation methods construct nonlinear single-error-correcting codes for binary asymmetric channels using ternary outer codes, outperforming some Varshamov-Tenengol'ts-Constantin-Rao codes in many cases. For nonbinary asymmetric channels, the approach yields linear codes superior to those correcting equivalent symmetric errors. These results show that optimal linear codes for nonbinary asymmetric channels exceed symmetric channel performance, unlike the binary case.

Quantum Adiabatic Algorithm Fails on Random 3-Regular 3-XORSAT and Max-Cut Instances

The quantum adiabatic algorithm (QAA) with stoquastic interpolating Hamiltonians fails to efficiently solve random instances of 3-regular 3-XORSAT and 3-regular Max-Cut on hypergraphs. These clause-based problems share similar cost functions defined on 3-regular hypergraphs, differing only in clause arity (three variables for 3-XORSAT, two for Max-Cut). Analysis via sign-problem-free quantum Monte Carlo and quantum cavity methods reveals distinct failure mechanisms for each problem.

Frustration-Free Spin-1 Chains Achieve Criticality with Highly Entangled Ground States

Researchers construct the first translation-invariant, frustration-free quantum spin-1 chain with nearest-neighbor interactions featuring a unique, highly entangled ground state resembling a uniform superposition of balanced parentheses strings. The entanglement entropy of half the chain scales as (log n)/2 + O(1), indicating critical behavior, while the energy gap above the ground state is polynomial in 1/n. This contrasts with spin-1/2 FF chains, which have unentangled product ground states, and relies on new statistics of Dyck paths for the gap proof.

Unstructured Random Hamiltonians Reveal Exponential Gap Closure and Localization in Quantum Adiabatic Evolution

Analysis of the quantum adiabatic algorithm Hamiltonian with a random unstructured cost function yields exact ground state energy in the infinite-bit limit. The minimum spectral gap closes exponentially with bit count, accompanied by a localization transition in the ground state. No excited states approach the ground state near evolution's end, though applicability to structured random problems like SAT remains unclear.

Quantum Double Model Boundaries Reveal Indistinguishable Anyons in S3 and Semidirect Product Groups

The paper extends Kitaev's quantum double model to surfaces with boundaries by defining boundary conditions and characterizing anyon condensations, where specific quasi-particle excitations vanish at the boundary. It analyzes domain walls between quantum double phases of different finite groups to study anyon tunneling, yielding necessary and sufficient conditions for two groups to produce identical anyon types. As an application, it demonstrates indistinguishable chargeon and fluxion in the S3 quantum double, generalizing to semidirect products of additive and multiplicative groups of finite fields.

Knot Diagrams Enable Unclonable Quantum Money via Alexander Polynomial Equivalence

Proposes a quantum money scheme using superpositions of knot diagrams that encode oriented links sharing the same Alexander polynomial. The mint produces an unclonable quantum state verifiable by anyone with a quantum computer. Security holds against computationally bounded adversaries due to the hardness of distinguishing non-equivalent knot representations.