Resource costs of unconstrained summoning: efficient protocols, lower bounds, and the quantum-versus-classical token comparison

In relativistic quantum information theory, an unconstrained summoning task requires an agency with spacetime-distributed agents to propagate an unknown quantum state to a return point determined by classical inputs received at other spacetime points, where the inputs are otherwise unconstrained. Kent (2018) proved that every classically possible unconstrained summoning task is also possible in quantum theory, but the constructive protocols — chains of teleportations implementing distributed nonlocal computation, combined with quantum secret sharing — were explicitly offered as feasibility results only: they consume pre-shared entanglement that grows very rapidly with the number of input points, exponentially so in the quantum-money examples. The open problem left there is to quantify and minimize the resources (pre-shared entanglement, classical communication, quantum memory, computation) required by general unconstrained summoning tasks; prove matching lower bounds; and determine, within a common resource and security model, whether quantum summoning can ever outperform classical token schemes such as S-money in resource cost. No prior work is known that optimizes or bounds the resources of unconstrained summoning or settles the quantum-versus-classical comparison; the problem remains open.

Background

Relativistic quantum information theory studies tasks carried out by agencies whose agents occupy different spacetime points and can communicate only at or below light speed, so that each agent may act only on information in the past light cone of its location. A canonical task is summoning, introduced via Kent's no-summoning theorem (2013) and developed by Hayden and May (2016). In a summoning task, an agency Alice receives an unknown quantum state $\psi$ from a second agency Bob at a start point $P$; later, at a set of input points, Bob reveals classical information; and by pre-agreed rules this information determines at which point of a pre-agreed set of return points Alice must produce $\psi$. Alice succeeds only if the state appears at the designated return point(s) and nowhere it should not. Because quantum information cannot be copied (the no-cloning theorem) and cannot outrun light, many summoning tasks are impossible; for instance, returning the state at whichever of two spacelike separated points is requested is impossible unless the request lies in the common causal past of both.

Early summoning results restricted the classical inputs — for example, single bits at fixed call points, each paired with a return point; the region between a call point and its return point, where a call can be both learned and acted upon, is called a causal diamond. Kent (2018) introduced unconstrained summoning: the classical inputs may take any values, with no promise about them (they may be chosen adversarially), the sets of input and return points are finite and fixed in advance, and the rules may designate one return point, at most one, or a subset of several. A task is classically possible if some deterministic algorithm, given the same inputs but a known classical state, always delivers that state to the right point. Kent proved the equivalence: every classically possible unconstrained summoning task is quantum-possible, and conversely any task solvable by a deterministic quantum algorithm is classically possible. The proof combines two constructions: distributed nonlocal computation in the sense of Vaidman, in which the state is pushed through a chain of quantum teleportations (teleportation transfers an unknown quantum state using one pre-shared entangled pair — one ebit — plus two classical bits of measurement data) spanning the input points, with all classical teleportation data broadcast so the state can be reconstructed at the correct return point; and quantum secret sharing (Gottesman 2000), which encodes an unknown state into shares so that any authorized subset of shares can reconstruct it while unauthorized subsets learn nothing.

The catch is resources. Kent states explicitly that he is concerned only with feasibility in principle and not with optimization: the iterated-teleportation constructions need quantities of pre-shared entanglement that grow very rapidly with the number of input points — in the quantum-money examples of the companion S-money paper, exponentially in the number of network sites — together with near-perfect teleportation. That companion proposal (Kent 2019) defines S-money: purely classical virtual tokens whose validity is fixed by classical data coordinated under relativistic signalling constraints, implementable with quantum key distribution but no long-lived quantum memory, and able to emulate any deterministic summoning task solvable by quantum money tokens. This raises the practical question of whether quantum summoning can ever justify its entanglement cost.

Adjacent results suggest both that efficiency gains are possible and that resource costs may be intrinsically large. For summoning restricted to causal diamonds, Wu, Khalid and Sanders (2018) gave a Calderbank-Shor-Steane (CSS) quantum error-correcting code that halves the number of physical qubits per encoded qubit relative to the previous scheme and reduces the encoding gate complexity from $O(N^3)$ to $O(N^2)$ for $N$ diamonds. Hayden and May (2019) characterized localize-exclude and state-assembly tasks — spacetime analogues of secret sharing — and constructed the first schemes whose qubit count is polynomial in the number of authorized sets, while noting the classical communication may be exponential. On the other side, in position-based cryptography, whose attacks rest on the same Vaidman-type nonlocal computation, executing the required attack is known to be possible with entangled states whose size is exponential in the input size (Buhrman et al. 2014), a warning that the entanglement demands of nonlocal computation can be genuinely large.

Problem Statement

For unconstrained summoning tasks as defined by Kent (2018) — a finite set of input points and a finite set of return points fixed in advance; classical inputs $m_i$ at the input points, each an integer in a finite range of size $n_i$ known in advance, whose values determine, by a pre-agreed rule $Q$, the required return point(s) (one, at most one, or several), the inputs being otherwise unconstrained; and a task that is classically possible — quantify and minimize the resources required to complete the task in quantum theory. The problem has three connected open directions, all in service of one objective, a resource theory of unconstrained summoning; resolving any one of the three directions below, with the relevant resource and security model stated explicitly, constitutes a resolution of the task:

(1) Efficient protocols. Find protocols for general classically possible unconstrained summoning tasks whose pre-shared entanglement, classical communication, quantum memory (under an explicitly stated convention, e.g. peak stored qubits or qubit-time), and computational cost — measured in the worst case over input tuples — scale polynomially in the full size data of the task: the numbers of input and return points, the input ranges $\{n_i\}$, and the dimension of the summoned state. This improves on the known iterated-teleportation and quantum-secret-sharing constructions, whose entanglement requirements grow exponentially in natural examples such as the quantum-money summoning tasks analyzed in Kent's S-money paper.

(2) Lower bounds and optimality. For precisely defined task families on which correct protocols genuinely require distributed quantum resources — in particular, not families in which the summoned state can simply be physically transported to the designated return point, where the optimal pre-shared entanglement cost is trivially zero — and for resource measures whose dependence on the task size data (numbers of input and return points, input ranges $\{n_i\}$, and the dimension of the summoned state) is explicitly stated (for example, ebits of pre-shared entanglement distributed among agent locations), prove lower bounds on what any correct protocol must consume, thereby establishing optimality or quantifying the gap for the protocols of (1).

(3) Quantum versus classical tokens. Within the scope of this problem, the flexibility question is already settled by the cited sources: Kent's equivalence theorem and the S-money analysis establish that classical S-money-type schemes can emulate any deterministic summoning task solvable with quantum money, and that any unconstrained-input task solvable by a deterministic quantum algorithm is classically possible. The open question is therefore one of cost. Within an explicitly stated common model of resources and security, determine whether quantum summoning — for example, summoning quantum money tokens — offers an advantage in resource cost over classical token schemes of the S-money type for some unconstrained summoning task, or whether classical schemes always match quantum summoning at no greater resource cost.

A further direction noted by Kent (2018) is the extension of both the feasibility and the resource analysis to tasks with infinite sets of input and return points; it is recorded as an interesting possibility but is not part of this problem. The extension to unbounded classical inputs (such as real-valued inputs) is not part of the open problem: Kent's results already cover general classical inputs, the finite bounds in his definitions being a notational simplification only.

References

1. Adrian Kent, Unconstrained summoning for relativistic quantum information processing, Physical Review A 98, 062332 (2018), DOI 10.1103/PhysRevA.98.062332, https://doi.org/10.1103/PhysRevA.98.062332 (arXiv:1806.01736, https://arxiv.org/abs/1806.01736)
2. Adrian Kent, A no-summoning theorem in relativistic quantum theory, Quantum Information Processing 12, 1023-1032 (2013), DOI 10.1007/s11128-012-0431-6, https://doi.org/10.1007/s11128-012-0431-6 (arXiv:1101.4612, https://arxiv.org/abs/1101.4612)
3. Patrick Hayden and Alex May, Summoning information in spacetime, or where and when can a qubit be?, Journal of Physics A: Mathematical and Theoretical 49, 175304 (2016), DOI 10.1088/1751-8113-49-17-175304, https://doi.org/10.1088/1751-8113-49-17-175304 (arXiv:1210.0913, https://arxiv.org/abs/1210.0913)
4. Emily Adlam and Adrian Kent, Quantum paradox of choice: More freedom makes summoning a quantum state harder, Physical Review A 93, 062327 (2016), DOI 10.1103/PhysRevA.93.062327, https://doi.org/10.1103/PhysRevA.93.062327 (arXiv:1509.04226, https://arxiv.org/abs/1509.04226)
5. Adrian Kent, Quantum tasks in Minkowski space, Classical and Quantum Gravity 29, 224013 (2012), DOI 10.1088/0264-9381/29/22/224013, https://doi.org/10.1088/0264-9381/29/22/224013
6. Lev Vaidman, Instantaneous measurement of nonlocal variables, Physical Review Letters 90, 010402 (2003), DOI 10.1103/PhysRevLett.90.010402, https://doi.org/10.1103/PhysRevLett.90.010402
7. Daniel Gottesman, Theory of quantum secret sharing, Physical Review A 61, 042311 (2000), DOI 10.1103/PhysRevA.61.042311, https://doi.org/10.1103/PhysRevA.61.042311
8. Adrian Kent, S-money: virtual tokens for a relativistic economy, Proceedings of the Royal Society A 475, 20190170 (2019), DOI 10.1098/rspa.2019.0170, https://doi.org/10.1098/rspa.2019.0170 (arXiv:1806.05884, https://arxiv.org/abs/1806.05884)
9. Ya-Dong Wu, Abdullah Khalid, and Barry C. Sanders, Efficient code for relativistic quantum summoning, New Journal of Physics 20, 063052 (2018), DOI 10.1088/1367-2630/aaccae, https://doi.org/10.1088/1367-2630/aaccae (arXiv:1711.10594, https://arxiv.org/abs/1711.10594)
10. Patrick Hayden and Alex May, Localizing and excluding quantum information; or, how to share a quantum secret in spacetime, Quantum 3, 196 (2019), DOI 10.22331/q-2019-10-24-196, https://doi.org/10.22331/q-2019-10-24-196 (arXiv:1806.04154, https://arxiv.org/abs/1806.04154)
11. Kfir Dolev, Alex May, and Kianna Wan, Distributing bipartite quantum systems under timing constraints, Journal of Physics A: Mathematical and Theoretical 54, 145301 (2021), DOI 10.1088/1751-8121/abe5ce, https://doi.org/10.1088/1751-8121/abe5ce (arXiv:2011.00936, https://arxiv.org/abs/2011.00936)
12. Adrian Kent, Summoning, no-signalling and relativistic bit commitments, arXiv:1804.05246 (2019), https://arxiv.org/abs/1804.05246
13. Alex May, Quantum tasks in holography, Journal of High Energy Physics 2019, 233 (2019), DOI 10.1007/JHEP10(2019)233, https://doi.org/10.1007/JHEP10(2019)233
14. Damián Pitalúa-García, One-out-of-m spacetime-constrained oblivious transfer, Physical Review A 100, 012302 (2019), DOI 10.1103/PhysRevA.100.012302, https://doi.org/10.1103/PhysRevA.100.012302 (arXiv:1907.02475, https://arxiv.org/abs/1907.02475)
15. Adrian Kent and Damián Pitalúa-García, Flexible quantum tokens in spacetime, arXiv:1908.08143 (2020), https://arxiv.org/abs/1908.08143
16. Adrian Kent, David Lowndes, Damián Pitalúa-García, and John Rarity, Practical quantum tokens without quantum memories and experimental tests, arXiv:2104.11717 (2022), https://arxiv.org/abs/2104.11717
17. Nadezhda P. Kukharchyk, Holger Boche, Christian Deppe, Kirill G. Fedorov, Martin E. Garcia, Ilja Gerhardt, Rudolf Gross, Thomas Halfmann, Hans Huebl, David Hunger, Wolfgang Kilian, Roman Kolesov, Juliane Krämer, Alexander Kubanek, Kai Müller, Boris Naydenov, Janis Nötzel, Anna P. Ovvyan, Wolfram H. P. Pernice, Gregor Pieplow, Cyril Popov, Tim Schröder, Kilian Singer, and Janik Wolters, Practical quantum tokens: challenges and perspectives, arXiv:2602.10621 (2026), https://arxiv.org/abs/2602.10621
18. Lana Bozanic, Alex May, and Stanley Miao, Entanglement summoning from entanglement sharing, arXiv:2601.15112 (2026), https://arxiv.org/abs/2601.15112
19. Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner, Position-based quantum cryptography: Impossibility and constructions, SIAM Journal on Computing 43, 150-178 (2014), DOI 10.1137/130913687, https://doi.org/10.1137/130913687