Peter Shor

Quantum Channel Capacity for Joint Classical-Quantum Transmission

Devetak and Shor derive an expression for the admissible rate pairs enabling simultaneous transmission of classical and quantum information over a quantum channel, generalizing the individual classical and quantum capacities. The formula requires regularization over multiple channel uses but simplifies to a single-letter expression for generalized dephasing channels. Analogous regularized formulae are conjectured for public-private capacities and distillable common randomness with entanglement in bipartite states.

Entanglement-Assisted Classical Capacity of Quantum Channels Equals Input + Output Entropies Minus Joint Entropy

The entanglement-assisted classical capacity of a quantum channel is the maximum over input states ρ of H(ρ) + H(channel(ρ)) - H(ρ, channel(ρ)), where the joint entropy uses an entangled purification. This formula mirrors the classical channel capacity expression. The paper computes this for the qubit amplitude damping channel and the bosonic channel with amplification/attenuation and Gaussian noise, and proves that shared randomness makes all classical DMCs of equal capacity asymptotically simulable with unit efficiency.

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.

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.

Short quantum messages in interactive proofs are eliminable, yielding standard QMA and BQP power

Three variants of quantum interactive proof systems restrict message lengths to logarithmic size: verifier-first short-to-long, logarithmic total multi-round, and verifier-polynomial-random-to-prover-short-quantum. Short messages can be eliminated in all cases without loss of expressive power, reducing to QMA for the first variant and BQP for the others. Proofs leverage quantum state tomography and the finite quantum de Finetti theorem.

Indistinguishable Chargeon-Fluxion Pairs Exist in Quantum Doubles of Semidirect Products of Finite Field Groups

The paper examines auto-equivalences of the modular tensor category of representations of a finite group's quantum double that permute simple objects via charge conjugation followed by transposing a chargeon-fluxion pair. It proves such auto-equivalences exist precisely when the group is a semidirect product of the additive and multiplicative groups of a finite field, as exemplified by S_3. Conversely, these transpositions form modular invariants if and only if the group is isomorphic to that of a finite near-field.

Conditions for Unfrustrated Qudit Chains with Non-Translational Ground States

The paper derives conditions under which chains of d-dimensional qudits with generic, translationally non-invariant nearest-neighbor interactions are unfrustrated, meaning ground states coincide with common ground states of all local Hamiltonian terms. These states are represented using the Matrix Product States (MPS) framework. Numerical imaginary time evolution in MPS reveals parameter ranges where ground states exhibit high entanglement, challenging MPS approximations.