pith. machine review for the scientific record. sign in

arxiv: 2602.00255 · v4 · submitted 2026-01-30 · 🪐 quant-ph

Recognition: unknown

Lower bounds on non-local computation from controllable correlation

Richard Cleve , Alex May
Authors on Pith no claims yet

Pith reviewed 2026-05-16 08:58 UTC · model grok-4.3

classification 🪐 quant-ph
keywords non-local quantum computationentanglement costlower boundsCNOT gatecontrollable correlationtwo-qubit unitariesquantum gates
0
0 comments X

The pith

New lower bound techniques resolve the entanglement cost for the CNOT gate in non-local quantum computation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces two new techniques for lower bounding the entanglement cost of implementing any unitary in a non-local quantum computation setting. These techniques rely on quantities called controllable correlation and controllable entanglement that can be computed or bounded for any given unitary. They provide the first known lower bounds for several common two-qubit gates and a tight bound for the CNOT gate that fully determines its minimal entanglement requirement. This advances the characterization of entanglement costs in NLQC, which relate to complexity, cryptography, and gravity.

Core claim

The authors establish that lower bounds on the entanglement cost of non-local unitary computation can be obtained from the controllable correlation and controllable entanglement of the target unitary. For the CNOT gate one technique yields a tight bound, fully resolving its entanglement cost. The resulting bounds apply to Haar-random two-qubit unitaries, to most commonly studied gates including DCNOT, sqrt(SWAP), and the XX interaction, and possess parallel repetition properties while remaining valid in the noisy setting.

What carries the argument

Controllable correlation and controllable entanglement, quantities that measure the maximum correlation or entanglement that can be controlled or extracted in a non-local protocol for a given unitary and thereby yield lower bounds on its entanglement cost.

If this is right

  • Lower bounds can be computed for any two-qubit unitary, and for Haar-random ones the bounds are typically non-trivial.
  • Concrete lower bounds are now known for CNOT, DCNOT, sqrt(SWAP), and the XX interaction.
  • The bounds have parallel repetition properties.
  • The bounds continue to hold when the protocol is subject to noise.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same controllable-correlation method may be adaptable to unitaries on more than two qubits to obtain broader lower bounds.
  • The resolved CNOT cost supplies a concrete benchmark that can be used to test the efficiency of new non-local protocols or cryptographic schemes.
  • Because the bounds apply to random unitaries, they offer a typical-case estimate that could inform average-case analyses in quantum complexity.

Load-bearing premise

That the quantities controllable correlation and controllable entanglement can be evaluated or bounded in a way that yields valid lower bounds on the true minimal entanglement cost for the target unitary.

What would settle it

Discovery of a non-local protocol for the CNOT gate that performs the computation using strictly less entanglement than the lower bound given by the controllable correlation technique.

Figures

Figures reproduced from arXiv: 2602.00255 by Alex May, Richard Cleve.

Figure 1
Figure 1. Figure 1: Local and non-local computations. a) A unitary [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Results of a numerical optimization computing the controllable entanglement and controllable correla [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A non-local quantum computation implementing a unitary [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Histogram showing the value of the controllable correlation lower bound computed for [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
read the original abstract

Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\text{SWAP}}$, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces two new lower bound techniques for the entanglement cost in non-local quantum computation (NLQC) based on controllable correlation and controllable entanglement. These techniques apply to arbitrary unitaries and produce non-trivial lower bounds for Haar-random two-qubit unitaries as well as specific gates including CNOT (with a claimed tight bound that resolves its entanglement cost), DCNOT, √SWAP, and the XX interaction. The resulting bounds possess parallel repetition properties and extend to the noisy setting.

Significance. If the central derivations hold, this constitutes a meaningful advance by supplying general, evaluable lower-bound methods for NLQC entanglement costs where prior techniques were restricted to narrow cases. The tight bound for CNOT is a concrete resolution of an open question for an important gate. The parallel-repetition property and noisy-channel applicability add value for complexity and cryptographic applications. The paper is credited for developing techniques that can be evaluated for any unitary, including random ones.

minor comments (2)
  1. [Abstract and §2] The abstract introduces the terms 'controllable correlation' and 'controllable entanglement' without definitions; the main text should supply their precise mathematical definitions in an early section (e.g., §2) before deriving the lower bounds.
  2. [Results section on specific gates] For the specific gates (CNOT, DCNOT, √SWAP, XX), present the numerical lower-bound values in a compact table together with the corresponding upper bounds from known protocols to make the tightness claim for CNOT immediately verifiable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and the recommendation for minor revision. We appreciate the acknowledgment that the new lower-bound techniques based on controllable correlation and controllable entanglement constitute a meaningful advance, particularly for arbitrary unitaries and the resolution of the CNOT entanglement cost.

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper presents two new lower-bound techniques for entanglement cost in NLQC, defined directly from controllable correlation and controllable entanglement quantities that are evaluated from the target unitary itself. These are applied to arbitrary unitaries (including Haar-random cases and specific gates like CNOT) without any reduction of the reported bounds to fitted parameters, self-definitions, or load-bearing self-citations. The tightness result for CNOT is obtained by direct evaluation of one technique against the unitary's properties, with no evidence that the bound is forced by construction or imported via an unverified ansatz from prior self-work. The argument structure remains independent of the target result, consistent with the abstract's claim that the methods apply generally and resolve CNOT exactly. This is the expected non-finding for a paper whose central claims rest on explicit, externally evaluable quantities rather than internal reparameterization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

Relies on standard quantum-information definitions of entanglement and correlation; introduces controllable correlation and controllable entanglement as new bounding quantities whose precise definitions and independence from the target cost are not visible in the abstract.

axioms (1)
  • standard math Standard axioms of quantum mechanics and the definition of entanglement cost in non-local computation
    Background framework for NLQC and entanglement measures invoked throughout.
invented entities (2)
  • Controllable correlation no independent evidence
    purpose: Quantity used to derive lower bounds on entanglement cost
    New technique introduced in the paper; no independent evidence supplied in abstract.
  • Controllable entanglement no independent evidence
    purpose: Quantity used to derive lower bounds on entanglement cost
    New technique introduced in the paper; no independent evidence supplied in abstract.

pith-pipeline@v0.9.0 · 5446 in / 1301 out tokens · 27037 ms · 2026-05-16T08:58:48.015169+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Entanglement cost in non-local quantum computation

    quant-ph 2026-05 unverdicted novelty 2.0

    A review compiling upper and lower bounds on entanglement cost for non-local quantum computation and its connections to cryptography, complexity, communication, and quantum gravity.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Quantum tagging: Authenti- cating location via quantum information and relativistic signaling constraints.Physi- cal Review A, 84(1):012326, 2011

    Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenti- cating location via quantum information and relativistic signaling constraints.Physi- cal Review A, 84(1):012326, 2011. doi:https://doi.org/10.1103/PhysRevA.84.012326

    work page doi:10.1103/physreva.84.012326 2011

  2. [2]

    Position-based quantum cryptography: Im- possibility and constructions.SIAM Journal on Computing, 43(1):150–178, 2014

    Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Im- possibility and constructions.SIAM Journal on Computing, 43(1):150–178, 2014. doi:https://doi.org/10.1137/130913687

    work page doi:10.1137/130913687 2014

  3. [3]

    Quantum tasks in holography.Journal of High Energy Physics, 2019(10): 1–39, 2019

    Alex May. Quantum tasks in holography.Journal of High Energy Physics, 2019(10): 1–39, 2019. doi:https://doi.org/10.1007/JHEP10(2019)233

    work page doi:10.1007/jhep10(2019)233 2019

  4. [4]

    Holographic scattering requires a connected entanglement wedge.Journal of High Energy Physics, 2020(8):1–34, 2020

    Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge.Journal of High Energy Physics, 2020(8):1–34, 2020. doi:https://doi.org/10.1007/JHEP08(2020)132

    work page doi:10.1007/jhep08(2020)132 2020

  5. [5]

    Non-local computation and the black hole interior.arXiv preprint arXiv:2304.11184, 2023

    Alex May and Michelle Xu. Non-local computation and the black hole interior.arXiv preprint arXiv:2304.11184, 2023. doi:https://doi.org/10.48550/arXiv.2304.11184

    work page doi:10.48550/arxiv.2304.11184 2023

  6. [6]

    Complexity and entanglement in non-local computation and holography

    Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 6:864, 2022. doi:https://doi.org/10.22331/q-2022-11-28-864

    work page doi:10.22331/q-2022-11-28-864 2022

  7. [7]

    The connected wedge theorem and its consequences.Journal of High Energy Physics, 2022(11):1–65, 2022

    Alex May, Jonathan Sorce, and Beni Yoshida. The connected wedge theorem and its consequences.Journal of High Energy Physics, 2022(11):1–65, 2022. doi:https://doi.org/10.1007/JHEP11(2022)153

    work page doi:10.1007/jhep11(2022)153 2022

  8. [8]

    Thegarden- hose model

    HarryBuhrman, SergeFehr, ChristianSchaffner, andFlorianSpeelman. Thegarden- hose model. InProceedings of the 4th conference on Innovations in Theoretical Com- puter Science, pages 145–158, 2013. doi:https://doi.org/10.1145/2422436.2422455

    work page doi:10.1145/2422436.2422455 2013

  9. [9]

    Code-routing: a new attack on position-verification.arXiv preprint arXiv:2202.07812, 2022

    Sam Cree and Alex May. Code-routing: a new attack on position-verification.arXiv preprint arXiv:2202.07812, 2022. doi:https://doi.org/10.48550/arXiv.2202.07812

    work page doi:10.48550/arxiv.2202.07812 2022

  10. [10]

    Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits

    Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. In Anne Broadbent, editor,11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:24, Dagstuhl, Ger- many, 2016. Schloss Dagstuhl–Leibniz-Zentrum ...

    work page doi:10.4230/lipics.tqc.2016.9 2016

  11. [11]

    Relating non-local quantum computation to information theoretic cryptog- raphy.Quantum, 8:1387, 2024

    Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptog- raphy.Quantum, 8:1387, 2024. doi:https://doi.org/10.22331/q-2024-06-27-1387

    work page doi:10.22331/q-2024-06-27-1387 2024

  12. [12]

    Rank lower bounds on non-local quantum computation.arXiv preprint arXiv:2402.18647, 2024

    Vahid R Asadi, Eric Culf, and Alex May. Rank lower bounds on non-local quantum computation.arXiv preprint arXiv:2402.18647, 2024. doi:https://doi.org/10.48550/arXiv.2402.18647

    work page doi:10.48550/arxiv.2402.18647 2024

  13. [13]

    Security of quantum position-verification limits hamiltonian simula- tion via holography.Journal of High Energy Physics, 2024(8):1–40, 2024

    Harriet Apel, Toby Cubitt, Patrick Hayden, Tamara Kohler, and David Pérez- García. Security of quantum position-verification limits hamiltonian simula- tion via holography.Journal of High Energy Physics, 2024(8):1–40, 2024. doi:https://doi.org/10.1007/JHEP08(2024)152

    work page doi:10.1007/jhep08(2024)152 2024

  14. [14]

    Unclon- able secret sharing

    Prabhanjan Ananth, Vipul Goyal, Jiahui Liu, and Qipeng Liu. Unclon- able secret sharing. InInternational Conference on the Theory and Appli- cation of Cryptology and Information Security, pages 129–157. Springer, 2024. doi:https://doi.org/10.1007/978-981-96-0947-5_5

    work page doi:10.1007/978-981-96-0947-5_5 2024

  15. [15]

    Magic and communication complexity.arXiv preprint arXiv:2510.07246, 2025

    Uma Girish, Alex May, Natalie Parham, and Henry Yuen. Magic and communication complexity.arXiv preprint arXiv:2510.07246, 2025

    work page arXiv 2025

  16. [16]

    Linear gate bounds against natural functions for position-verification.Quantum, 9:1604, 2025

    Vahid Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification.Quantum, 9:1604, 2025. doi:https://doi.org/10.22331/q-2025-01-21-1604. 26

    work page doi:10.22331/q-2025-01-21-1604 2025

  17. [17]

    Simplified instantaneous non-local quantum com- putation with applications to position-based cryptography.New Journal of Physics, 13(9):093036, 2011

    Salman Beigi and Robert König. Simplified instantaneous non-local quantum com- putation with applications to position-based cryptography.New Journal of Physics, 13(9):093036, 2011. doi:10.1088/1367-2630/13/9/093036

    work page doi:10.1088/1367-2630/13/9/093036 2011

  18. [18]

    A complexity theory for non-local quantum computation.arXiv preprint arXiv:2505.23893, 2025

    Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen. A complexity theory for non-local quantum computation.arXiv preprint arXiv:2505.23893, 2025. doi:https://doi.org/10.48550/arXiv.2505.23893

    work page doi:10.48550/arxiv.2505.23893 2025

  19. [19]

    A monogamy-of-entanglement game with applications to device-independent quantum cryptography.New Journal of Physics, 15(10):103002, 2013

    Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography.New Journal of Physics, 15(10):103002, 2013. doi:10.1088/1367- 2630/15/10/103002

    work page doi:10.1088/1367- 2013

  20. [20]

    Position-based cryp- tography: Single-qubit protocol secure against multi-qubit attacks.arXiv preprint arXiv:2104.06301, 2021

    Andreas Bluhm, Matthias Christandl, and Florian Speelman. Position-based cryp- tography: Single-qubit protocol secure against multi-qubit attacks.arXiv preprint arXiv:2104.06301, 2021. doi:https://doi.org/10.48550/arXiv.2104.06301

    work page doi:10.48550/arxiv.2104.06301 2021

  21. [21]

    Quantum secure key exchange with position-based credentials.arXiv preprint arXiv:2506.03549, 2025

    Wen Yu Kon, Ignatius William Primaatmaja, Kaushik Chakraborty, and Charles Lim. Quantum secure key exchange with position-based credentials.arXiv preprint arXiv:2506.03549, 2025. doi:https://doi.org/10.48550/arXiv.2506.03549

    work page doi:10.48550/arxiv.2506.03549 2025

  22. [22]

    Quantum position verification in one shot: parallel repetition of thef-BB84 andf-routing protocols.arXiv preprint arXiv:2503.09544, 2025

    Llorenç Escolà-Farràs and Florian Speelman. Quantum position verification in one shot: parallel repetition of thef-BB84 andf-routing protocols.arXiv preprint arXiv:2503.09544, 2025. doi:https://doi.org/10.48550/arXiv.2503.09544

    work page doi:10.48550/arxiv.2503.09544 2025

  23. [23]

    A Tight Lower Bound for the BB84-states Quantum-Position-Verification Protocol

    Jérémy Ribeiro and Frédéric Grosshans. A tight lower bound for the BB84-states quantum-position-verification protocol.arXiv preprint arXiv:1504.07171, 2015. doi:https://doi.org/10.48550/arXiv.1504.07171

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1504.07171 2015

  24. [24]

    On the role of quantum communication and loss in attacks on quantum position verification.arXiv preprint arXiv:2208.04341, 2022

    Rene Allerstorfer, Harry Buhrman, Florian Speelman, and Philip Verduyn Lunel. On the role of quantum communication and loss in attacks on quantum position verification.arXiv preprint arXiv:2208.04341, 2022. doi:https://doi.org/10.48550/arXiv.2208.04341

    work page doi:10.48550/arxiv.2208.04341 2022

  25. [25]

    Bounds on instantaneous nonlocal quantum computation.IEEE Transactions on Information Theory, 66(5):2951–2963, 2019

    Alvin Gonzales and Eric Chitambar. Bounds on instantaneous nonlocal quantum computation.IEEE Transactions on Information Theory, 66(5):2951–2963, 2019

    work page 2019

  26. [26]

    Practical position- based quantum cryptography.Physical Review A, 92(5):052304, 2015

    Kaushik Chakraborty and Anthony Leverrier. Practical position- based quantum cryptography.Physical Review A, 92(5):052304, 2015. doi:https://doi.org/10.1103/PhysRevA.92.052304

    work page doi:10.1103/physreva.92.052304 2015

  27. [27]

    Randomized benchmarking with confidence

    Joel J Wallman and Steven T Flammia. Randomized benchmarking with confidence. New Journal of Physics, 16(10):103032, 2014

    work page 2014

  28. [28]

    Andreas Winter. Tight uniform continuity bounds for quantum entropies: condi- tional entropy, relative entropy distance and energy constraints.Communications in Mathematical Physics, 347(1):291–313, 2016. doi:https://doi.org/10.1007/s00220- 016-2609-8

    work page doi:10.1007/s00220- 2016

  29. [29]

    Entanglement of a Pair of Quantum Bits

    Scott Hill and William K Wootters. Entanglement of a pair of quantum bits.arXiv preprint quant-ph/9703041, 1997. doi:https://doi.org/10.1103/PhysRevLett.78.5022

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.78.5022 1997

  30. [30]

    Entanglement of formation of an arbitrary state of two qubits.Physical Review Letters, 80(10):2245, 1998

    William K Wootters. Entanglement of formation of an arbitrary state of two qubits.Physical Review Letters, 80(10):2245, 1998. doi:https://doi.org/10.1103/PhysRevLett.80.2245

    work page doi:10.1103/physrevlett.80.2245 1998

  31. [31]

    Mixed-state entanglement and quantum error correction.Physical Review A, 54(5): 3824, 1996

    Charles H Bennett, David P DiVincenzo, John A Smolin, and William K Wootters. Mixed-state entanglement and quantum error correction.Physical Review A, 54(5): 3824, 1996. doi:https://doi.org/10.1103/PhysRevA.54.3824

    work page doi:10.1103/physreva.54.3824 1996

  32. [32]

    Continuity bounds for entanglement.Physical review A, 61(6): 064301, 2000

    Michael A Nielsen. Continuity bounds for entanglement.Physical review A, 61(6): 064301, 2000. doi:https://doi.org/10.1103/PhysRevA.61.064301

    work page doi:10.1103/physreva.61.064301 2000

  33. [33]

    Quantum coding.Physical review A, 51(4):2738, 1995

    Benjamin Schumacher. Quantum coding.Physical review A, 51(4):2738, 1995. doi:https://doi.org/10.1103/PhysRevA.51.2738

    work page doi:10.1103/physreva.51.2738 1995

  34. [34]

    Dina Abdelhadi and Joseph M Renes. On the second-order asymptotics of the partially smoothed conditional min-entropy & application to quantum compres- 27 sion.IEEE Journal on Selected Areas in Information Theory, 1(2):416–423, 2020. doi:10.1109/JSAIT.2020.3016899. 28

    work page doi:10.1109/jsait.2020.3016899 2020