PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Reverse Shannon Theorem

Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, Andreas Winter

arXiv:0912.5537v5quant-phcs.IT

TL;DR

The paper determines the resources needed to simulate discrete memoryless quantum channels across tensor-power and general sources, including ordinary and feedback settings. It establishes asymptotic resource characterizations, a strong converse for entanglement-assisted capacity, and limitations from regularization and missing embezzling states.

  • Problem

    Efficient quantum-channel simulation depends on the source and may require auxiliary resources beyond standard noiseless communication and ebits.

  • Method

    The paper combines resource characterizations for ordinary and feedback simulations with analyses of tensor-power and correlated or entangled general sources.

  • Results

    The results establish necessary and sufficient asymptotic resources for feedback simulation on tensor-power sources and prove a strong converse for the entanglement-assisted communication rate.

  • Takeaways & Limitations

    Efficient simulation can require entanglement spread, environment division, or additional communication when protocols operate on general sources or use superposed entanglement amounts.

  • Takeaways & Limitations

    Some no-feedback results are only regularized coding theorems and weak converses, and the additivity question for entanglement of purification remains open.

Abstract

from arXiv · show

Dual to the usual noisy channel coding problem, where a noisy (classical or quantum) channel is used to simulate a noiseless one, reverse Shannon theorems concern the use of noiseless channels to simulate noisy ones, and more generally the use of one noisy channel to simulate another. For channels of nonzero capacity, this simulation is always possible, but for it to be efficient, auxiliary resources of the proper kind and amount are generally required. In the classical case, shared randomness between sender and receiver is a sufficient auxiliary resource, regardless of the nature of the source, but in the quantum case the requisite auxiliary resources for efficient simulation depend on both the channel being simulated, and the source from which the channel inputs are coming. For tensor power sources (the quantum generalization of classical IID sources), entanglement in the form of standard ebits (maximally entangled pairs of qubits) is sufficient, but for general sources, which may be arbitrarily correlated or entangled across channel inputs, additional resources, such as entanglement-embezzling states or backward communication, are generally needed. Combining existing and new results, we establish the amounts of communication and auxiliary resources needed in both the classical and quantum cases, the tradeoffs among them, and the loss of simulation efficiency when auxiliary resources are absent or insufficient. In particular we find a new single-letter expression for the excess forward communication cost of coherent feedback simulations of quantum channels (i.e. simulations in which the sender retains what would escape into the environment in an ordinary simulation), on non-tensor-power sources in the presence of unlimited ebits but no other auxiliary resource. Our results on tensor power sources establish a strong converse to the entanglement-assisted capacity theorem.

C. Overview of results

The paper shows that efficient quantum channel simulation depends on both the channel and input source, requiring additional resources for general inputs. It combines resource characterizations, tradeoffs, feedback results, and applications to establish stronger simulation and converse statements.

  • Classical and quantum settings: Classical channels are characterized by capacity under shared randomness, whereas quantum channels have multiple inequivalent capacities and require richer resource descriptions.The paper frames channels and auxiliary resources as asymptotic communication resources and transformations between them.
  • Motivation: Quantum reverse Shannon simulation cannot generally use only QE(N) forward qubits and shared ebits for arbitrary inputs.The proposed analogy with the classical theorem fails in general, although it holds for important special cases.
  • Resource requirements: Tensor-power inputs ρ^⊗n and channels whose output entropy is determined by the environment are important cases where efficient simulation is possible with standard resources.For general channels on non-tensor-power inputs, additional resources beyond ordinary entanglement are required.
  • Resource requirements: Entanglement-embezzling states, additional forward communication, or backward classical or quantum communication can supply the extra resources needed for general-input simulation.These resources address the need to preserve coherence when different inputs require different amounts of entanglement.
  • Entanglement spread: For tensor-power sources, the required entanglement spread is O(√n), making its additional cost negligible through initially generous entanglement and later return of unused ebits.For non-tensor-power inputs, spread may be O(n), so other methods are needed to avoid increasing forward communication substantially.
  • Feedback simulations: Feedback simulations can yield resource equivalences, with asymptotically necessary and sufficient qubit and ebit rates determined by state redistribution.The feedback simulation is asymptotically reversible, and the noiseless classical-channel case reduces to the cobit resource equality.
  • Applications: The results also support rate-distortion theorems, strong converses for entanglement-assisted capacities, and coordination-capacity interpretations of reverse Shannon theorems.Rate-distortion replaces blockwise channel fidelity with an average distortion condition, which is less stringent.

II. STATEMENT OF RESULTS

The paper presents the parties, subsystems, and resource flows for classical and quantum channel simulation. It distinguishes ordinary from feedback simulations and emphasizes parallel operation over multiple inputs for efficient high-fidelity simulation.

  • Figure 1: Figure 1 contrasts classical and quantum channel parties and subsystems with their respective standard-resource simulation diagrams.Classical simulation uses shared random bits and forward classical communication; quantum simulation uses shared entanglement and forward quantum communication.
  • Simulation setting: Efficient simulation generally requires encoders and decoders to operate in parallel on multiple inputs.This supports simulation of multiple channel uses with high efficiency and fidelity.
  • Notation: The paper uses uppercase symbols for both random variables or quantum subsystems and their relevant distributions or density matrices.For example, H(B) denotes entropy of the relevant marginal state, while I(E;B) denotes quantum mutual information.
  • Figure 1: Dashed arrows identify additional data flows in feedback simulations, where systems are sent to Alice.The figure places classical and quantum channels in the top panels and their simulations in the bottom panels.

A. Classical Reverse Shannon Theorem

The classical reverse Shannon theorem characterizes channel-simulation costs through tradeoffs between forward communication, shared randomness, and feedback. For known sources, limited shared randomness enables nontrivial communication tradeoffs, while arbitrary-source results depend on worst-case input distributions.

  • For feedback simulation on a known source with sufficient shared randomness, c ≥ I(X;Y) and c + r ≥ H(Y).
  • With abundant shared randomness, feedback simulation requires no more communication than ordinary non-feedback simulation, but limited randomness can make non-feedback simulation cheaper.
  • For known-source non-feedback simulation, achievable costs satisfy c ≥ I(X;W) and c + r ≥ I(XY;W) for some W with I(X;Y|W) = 0.
  • Without shared randomness, the known-source non-feedback condition becomes c ≥ I(XY;W) for some W satisfying I(X;Y|W) = 0.
  • For arbitrary sources with feedback and shared randomness, c ≥ C(N) and r ≥ max_p H(Y) − max_p I(X;Y), with the maxima potentially attained by different input distributions.
  • Low-randomness simulations split the process into two stages, allowing part of the first stage’s randomness to be recycled or derandomized; non-feedback tradeoffs are therefore generally nontrivial.

B. Quantum Reverse Shannon Theorem (QRST)

The quantum reverse Shannon results characterize communication and auxiliary-resource costs for simulating quantum channels across tensor-power and arbitrary inputs, with feedback and non-feedback variants. They identify entanglement spread as a source of excess communication and give a single-letter formula for its deficit.

  • Tensor-power sources: For known tensor-power inputs, feedback simulation has necessary and sufficient qubit–ebit tradeoffs determined by mutual-information and entropy quantities.The formulation also establishes asymptotic reversibility of the associated state redistribution.
  • Tensor-power sources: With no entanglement, non-feedback simulation on known tensor-power inputs is obtained as a special case of the general resource characterization.Its communication cost is connected to the regularized entanglement of purification.
  • Arbitrary sources: For arbitrary inputs, efficient feedback simulation may require embezzling states, backward communication, or other auxiliary resources beyond ordinary ebits.Ordinary ebits can require asymptotically more communication than the channel capacity because simulations must preserve coherence across differing entanglement requirements.
  • Limitations: The known-input non-feedback qubit-cost tradeoff lacks a general single-letter formula or additivity theorem.The relevant entanglement-of-purification quantity may require regularization, and its additivity remains open.
  • Spread deficit: The spread deficit Δsim(N) captures the excess communication required for arbitrary-input feedback simulation with unlimited ebits but no stronger auxiliary resource.It is single-letter because each term in its expression is additive, enabling explicit evaluation through convex optimization.
  • Spread deficit: For covariant channels, Δsim(N)=0, whereas nonsymmetric channels can have nonzero deficit; amplitude damping provides an explicit example.For the variable-entropy channel Md, CE(Md)=1 while Δsim(Md)=log(d+1)−1, so spread can dominate simulation cost as d grows.
  • Non-feedback simulation: Non-feedback simulation can avoid the spread penalty for amplitude-damping and variable-entropy channels by damaging or measuring the environment.This collapses superpositions between different entanglement amounts, allowing simulation at the entanglement-assisted capacity rate.

C. Entanglement spread

Entanglement spread captures why general quantum inputs can require resources beyond ordinary ebits. The section defines this spread, relates it to communication costs, and identifies settings where spread-generating resources are necessary or unnecessary.

  • Entanglement spread: General inputs can contain coherent superpositions of different entanglement amounts, creating an entanglement-spread requirement.The spread is informally the difference between the largest and smallest relevant entanglement values.
  • Entanglement spread: Δ(ψ_A) = H0(ψ_A) − H∞(ψ_A) gives a general definition of entanglement spread for bipartite pure states.Here H0 is the logarithm of the reduced-state rank and H∞ is the negative logarithm of its largest eigenvalue.
  • Communication cost: Creating states with entanglement spread from ebits requires communication constrained by the spread measure.The paper states this through Theorem 5 and its smoothed version.
  • Resource tradeoffs: A deficit in ebits for coherent feedback simulation must be compensated by an equal increase in forward qubit communication.This identifies a direct communication–entanglement tradeoff.
  • When spread is unnecessary: For certain channels, efficient non-feedback simulations remain possible with ordinary ebits because Eve’s average state determines the output entropy uniquely.The paper gives amplitude damping and variable-entropy channels as examples.
  • When spread is necessary: More complicated channels can require embezzling states or backward communication even for non-feedback simulation.These resources generate the entanglement spread needed by the simulation.

A. Overview

The classical reverse Shannon construction uses shared randomness and communication to simulate a noisy channel, with a two-stage factorization exposing a tradeoff between these resources. The unweighted case is implemented through random partitions or intermediate states.

  • Overview: The classical reverse Shannon proof extends earlier high-randomness results to low-randomness cases of Theorem 1.The section reviews prior proofs and supplies the extension.
  • Graph intuition: A regular bipartite graph provides a toy model of a uniform channel, with neighbors defining the possible outputs for each input.This graph picture supplies the intuition for the protocol.
  • Direct simulation: Lemma 7 uses a shared random partition of outputs; Alice sends a within-block index, and Bob reconstructs the corresponding output.The protocol approximately simulates the channel while dividing resources between communication and shared randomness.
  • Two-stage simulation: A two-stage decomposition N = N2 ◦ N1 introduces an intermediate variable W, allowing Bob to generate the second-stage randomness locally.This can reduce shared randomness at the cost of additional communication.
  • Two-stage simulation: Lemma 8 chooses shared random subsets of W, sends an index for an intermediate state, and lets Bob apply N2 locally.The resulting protocol simulates the original channel through the intermediate channel.
  • Guarantee: The construction succeeds with high probability, achieving total variation error at most ϵ for every input.The stated success probability is at least 1 − 2|EXY|e^(−γϵ^2/32).

B. Proof of unweighted classical reverse Shannon theorem

The proof of the unweighted classical reverse Shannon theorem uses concentration of random intersections in regular graphs. Hoeffding bounds and union bounds establish the uniform approximation needed by the simulation protocol.

  • Concentration tool: The proofs of Lemmas 7 and 8 rely on Hoeffding bounds for the hypergeometric distribution.These bounds control random neighborhood intersections.
  • Lemma 7: For Lemma 7, the expected intersection size between an input neighborhood and a random output block is γ.Applying the hypergeometric bound to these intersections yields concentration around γ.
  • Lemma 8: For Lemma 8, intersections between input neighborhoods and random intermediate subsets likewise have expectation γ.A one-sided concentration bound controls all relevant input–subset pairs simultaneously.
  • Global guarantee: A union bound over all input–output edges gives simultaneous high-probability control of the required intersection estimates.The proof then combines the concentration events to establish the simulation guarantee.
  • Conclusion: The concentration estimates imply the claimed approximation, completing the proof of Lemma 8.The final comparison uses the preceding intersection identities and bounds.

C. Classical types

The method of types converts block-length channel simulation into a finite collection of type-conditioned unweighted graph simulations. Typicality and entropy continuity then show that both simulation error and inefficiency vanish asymptotically.

  • Type reduction: Alice communicates a joint type using O(log(n)) bits, after which the remaining conditional simulation is unweighted.For three variables, the joint type is over X, W, and Y.
  • Types: A type records symbol frequencies, and its normalized form is the empirical distribution.The number of possible types is bounded polynomially in n.
  • Type-conditioned channels: For memoryless channels, the probability of an output sequence conditioned on an input sequence depends only on their joint type.This permits channel simulation to be analyzed within type classes.
  • Shared-randomness protocol: With shared randomness, Alice partitions outputs of a fixed type and sends a representative using the unweighted protocol.The protocol uses n(H(Y) − C) + o(n) shared-randomness bits and nC + o(n) communication bits in the final step.
  • Asymptotics: As n grows, typicality and the Fannes-Audenaert inequality make both error and inefficiency vanish.The cited bounds control deviations in mutual information and conditional entropy.
  • Two-stage extension: The same construction for a factorized channel tracks the joint type of X, W, and Y before applying Lemma 8.This extends the type method to the two-stage resource tradeoff.

D. Converses

The converse arguments establish lower bounds on communication and shared randomness for reverse Shannon simulations, with strong converses in coding-theorem cases.

  • D. Converses: Communication must be at least C(N), or I(X;Y)p for inputs restricted to distribution p.Otherwise simulation combined with noisy-channel coding would produce more noisy-channel uses from fewer noiseless uses.
  • D. Converses: C + R ≥ H(Y) for feedback simulation, because Bob’s output must be determined by communication and shared randomness.
  • D. Converses: Non-feedback converses use I(XY;W) ≤ C + R, I(X;W) ≤ C, and the Markov chain X−W−Y.The shared randomness and message are combined into W, while conditional independence limits the information carried by the communication.
  • D. Converses: The converse bounds remain meaningful for negative R, representing protocols that generate shared randomness.
  • D. Converses: Coding-theorem converses generally yield strong converses, with fidelity decreasing exponentially below the required communication or randomness rate.
  • D. Converses: Flat-isometry simulation consumes log(DK) ebits and sends log(DM) qubits for maximally mixed input, with Haar-random decoding achieving the stated guarantee with high probability.The flat-isometry definition requires maximally mixed marginals, and the protocol is depicted in Fig. 9.

B. Tensor power inputs

For tensor-power inputs, Schur-Weyl type decompositions reduce quantum channel simulation to flat sub-channels, while typical spectra determine asymptotic costs and introduce sublinear entanglement spread.

  • B. Tensor power inputs: N^⊗n on ρ^⊗n is analyzed by decomposing the channel into quantum types and flat sub-channels.The protocol is presented as a warm-up for the general-input case.
  • B. Tensor power inputs: O(log n) qubits transmit the type information, leaving a flat spectrum within each type class.For fixed dimension, the number of types is polynomial in n.
  • B. Tensor power inputs: Typical triples have exponentially concentrated weight, with subspace dimensions exp(n(H(A)σ ±δ′′)), exp(n(H(B)σ ±δ′′)), and exp(n(H(E)σ ±δ′′)).Ignoring atypical types incurs error at most exp(−nδ′).
  • B. Tensor power inputs: The flat-subchannel construction requires 1/2 I(B;E) ebits per use of N.
  • B. Tensor power inputs: O(nδ) entanglement spread handles type-dependent ebit requirements, costing O(nδ) extra qubits and hence a vanishing asymptotic rate increase.The varying register dimension prevents using one fixed entangled-state size across all branches.
  • B. Tensor power inputs: Noncommuting input states require nondestructive eigenbasis estimation and coherent uncomputation before the tensor-power protocol can be applied.The required techniques are delicate even for unknown-state quantum data compression.

2) Decomposition of memoryless quantum channels:

Schur-Weyl duality decomposes memoryless quantum channels into superpositions of flat sub-channels indexed by quantum types, enabling flat-spectrum simulation methods.

  • 2) Decomposition of memoryless quantum channels:: N^⊗n splits into a map from type registers τA to τB, τE, and µ, followed by a map from permutation registers pA, µ to pB, pE.The τ registers represent marginal quantum types, while µ captures the joint component.
  • 2) Decomposition of memoryless quantum channels:: Permutation-sector maps commute with Sn and are proportional to flat isometries.Schur’s Lemma implies maximally mixed reduced states on the relevant permutation irreps.
  • 2) Decomposition of memoryless quantum channels:: The quantum types τA, τB, and τE are analogues of classical joint types, with all but poly(n) dimensions described by flat isometries.
  • 2) Decomposition of memoryless quantum channels:: Only a small set of typical triples of representation labels has non-negligible weight for large n.These triples correspond to spectral triples that can arise from a single channel use.
  • 2) Decomposition of memoryless quantum channels:: Joint typicality remains nontrivial because input and output Schur projectors need not commute.

D. Reduction to the flat spectrum case

The reduction to flat-spectrum simulation symmetrizes general inputs, decomposes the channel into flat components, discards atypical sectors, and accounts for resource variation across coherent branches.

  • D. Reduction to the flat spectrum case: General inputs can be replaced by Sn-invariant inputs using sublinear shared randomness.Sampling permutations from a smaller distribution reduces the required randomness to O(log(n/ϵ)) rbits while controlling error.
  • D. Reduction to the flat spectrum case: The proof pastes together simulations of different flat channels using entanglement spread.
  • D. Reduction to the flat spectrum case: The channel decomposes into a τA-to-(τB,τE,µ) map followed by a flat permutation-register map, with τB sent using O(log n) qubits.The flat map is then compressed using the flat-isometry simulation lemma.
  • D. Reduction to the flat spectrum case: For unknown general sources, coherent resource preparation can use extra forward communication, an embezzling state, or backward communication.Extra forward communication can become Ω(n) qubits, while the other methods avoid that specific increase.
  • D. Reduction to the flat spectrum case: For known tensor-power sources, the protocol coherently simulates Bob’s p register using about 1/2 nI(R;B) qubits and returns O(√n) unused ebit halves.Alice retains the τE and pE registers for coherent feedback simulation.
  • D. Reduction to the flat spectrum case: When feedback is unnecessary, Eve’s output can be split between Alice and Bob, and some superpositions across τA can be broken.Alice may estimate the relevant output state to O(n^-1/2) accuracy and communicate the estimate using o(n) communication.
  • D. Reduction to the flat spectrum case: The output estimate may not uniquely determine the channel output or the entanglement rate, requiring a superposition over compatible source states.

Inefficiencies and errors:

The protocols analyze how controlled inefficiencies affect simulation error, with the dominant bound scaling exponentially in nδ^2. Embezzling-state assistance can achieve this error rate but may require an exponentially large entangled ancilla.

  • Inefficiencies and errors:: O(nδ) inefficiency is permitted at each protocol step, and the resulting simulation errors are analyzed.The protocol-specific error sources include splitting, typicality restrictions, and input/output permutations.
  • Inefficiencies and errors:: log(m) rbits suffice for input permutation and output unpermutation when m = O(nδ + log(n)), changing the error by only a constant factor.This controls the communication needed for the permutation operations.
  • Inefficiencies and errors:: n exp(nδ) qubits are required in an embezzling state to achieve error exp(−nδ).The ancilla size is described as exorbitant, though irrelevant in some strong-converse arguments.
  • Inefficiencies and errors:: Strong converses link the entanglement-assisted capacity to optimal forward communication while non-IID simulations may require embezzling states or extra communication to create entanglement spread.The extra communication may be directed forward or backward.

1) Strong converse for forward communication:

Coding theorems constrain channel simulations through a guessing bound: insufficient forward communication forces exponentially small success, yielding strong converses for entanglement-assisted rates.

  • 1) Strong converse for forward communication:: The guessing bound states that m forward cbits, even with arbitrary back communication and entanglement, transmit m + k bits with success probability at most 2^−k.This principle is used to convert coding theorems into simulation converses.
  • 1) Strong converse for forward communication:: A coding theorem at rate C−δ implies that any simulation using fewer than the corresponding forward resources must have error approaching one exponentially.The argument permits auxiliary resources consistent with the guessing bound, including unlimited embezzling states and backward quantum communication.
  • 1) Strong converse for forward communication:: CE is the optimal cbit rate for simulation in the strong-converse sense, even when arbitrary entangled states and back communication are free.The simulation and coding error bounds both scale as exp(−nδ^2/8 log2(d)) up to sublinear terms.
  • 1) Strong converse for forward communication:: The strong converse extends beyond earlier results restricted to product-state inputs or particular channel classes.The cited prior results addressed Holevo or ordinary classical capacity rather than the broader setting established here.
  • 1) Strong converse for forward communication:: For a known IID input, using 1/2(I(R; B) − δ)[q →q] forces fidelity f ≤ 2^−nδ/2 + 2^−nδ′.The bound follows by combining the simulation with teleportation and a coding protocol, then applying causality.

2) Converses for the use of entanglement and back communication, based on spread:

Entanglement spread governs converse bounds for feedback simulations: without suitable spread, maximally entangled states require extra communication, while no-feedback cases admit only regularized weak converses.

  • 2) Converses for the use of entanglement and back communication, based on spread:: Coherent-feedback simulations impose stronger protocol constraints than ordinary simulations, making their converse bounds easier to prove.The analysis therefore begins with coherent feedback, corresponding to part (d) of Theorem 3.
  • 2) Converses for the use of entanglement and back communication, based on spread:: With only maximally entangled states, creating the necessary entanglement spread requires additional forward or backward communication.The converse establishes a larger total communication cost when embezzling states are unavailable.
  • 2) Converses for the use of entanglement and back communication, based on spread:: CE(N)+∆sim(N) is the spread rate created by the channel on the constructed input and is shown to be optimal.The construction uses an input superposition whose branches generate different entanglement amounts.
  • 2) Converses for the use of entanglement and back communication, based on spread:: Communication ≥n(CE(N)+∆sim(N)−o(1)) is required for error below a sufficiently small constant when unlimited ebits are used.The result establishes an error jump at the optimal rate but is not a strong converse for every error threshold below one.
  • 2) Converses for the use of entanglement and back communication, based on spread:: Without feedback, additivity is lost, so only regularized coding theorems and weak converses are established.The analysis treats the environment as consisting of systems discarded by Alice and Bob.

3) The clueless Eve channel:

The clueless Eve channel is constructed so different inputs produce different receiver entropies without revealing that variation to the environment, making standard-ebit simulation inefficient on some non-tensor-power inputs. A converse argues that either entanglement spread or mutual information must be large, forcing substantial communication.

  • Channel construction: The clueless Eve channel gives different inputs different receiver entropies while leaking no corresponding information to the environment.This hidden entropy variation can decohere superpositions during standard-ebit simulation.
  • Capacity and simulation cost: The channel has entanglement-assisted classical capacity CE(Nd) = 2QE(Nd) = 1 independent of d.Nevertheless, its ebit-assisted simulation cost can exceed its entanglement-assisted capacity on some non-tensor-power inputs.
  • Simulation obstruction: Using around n/2 forward qubits and k ordinary ebits, the simulation leaves Alice’s environment with markedly different entropy depending on the input term.For An = 0, the entropy is at most k + n/2; for An ≠ 0, it is at least k + n log(d) − n/2.
  • Converse argument: The converse shows that either the purified simulated state has high spread or it has high mutual information between R and B^nE_B.Their sum is at least H(R) = 1 + 1/2n log d, while each quantity is bounded by 2q, yielding the communication lower bound.
  • Approximate simulation: The ε > 0 extension is difficult because spread is unstable under small perturbations and the local environment dimensions are unbounded.The proof addresses the dimension issue with the Alicki-Fannes inequality, which depends on |R| rather than |E_A|.

V. CONCLUSION

The paper establishes resource requirements and tradeoffs for classical and quantum channel simulation across tensor-power and general sources, using a framework built from state splitting, entanglement spread, and environment division. It also identifies strong-converse implications and several unresolved technical boundaries.

  • V. CONCLUSION: The results establish necessary and sufficient noiseless-resource amounts for simulating discrete memoryless quantum channels, including classical channels as a special case.They cover ordinary and coherent-feedback simulations on both tensor-power and correlated or entangled general sources.
  • V. CONCLUSION: The technical framework combines state splitting, entanglement spread, and division of the simulated environment between sender and receiver.These ingredients support low-entanglement versions of the quantum reverse Shannon theorem.
  • V. CONCLUSION: Open problems include additivity and regularization for low-entanglement simulations, while one quantum lemma provides only average-case bounds.Shared randomness can address the average-case issue catalytically, but a more direct proof remains desirable.
Loading 0912.5537v5…