Characterising memory in quantum channel discrimination via constrained separability problems
Summarize this article with:
AbstractQuantum memories are a crucial precondition in many protocols for processing quantum information. A fundamental problem that illustrates this statement is given by the task of channel discrimination, in which an unknown channel drawn from a known random ensemble should be determined by applying it for a single time. In this paper, we characterise the quality of channel discrimination protocols when the quantum memory, quantified by the auxiliary dimension, is limited. This is achieved by formulating the problem in terms of separable quantum states with additional affine constraints that all of their factors in each separable decomposition obey. We discuss the computation of upper and lower bounds to the solutions of such problems which allow for new insights into the role of memory in channel discrimination. In addition to the single-copy scenario, this methodological insight allows to systematically characterise quantum and classical memories in adaptive channel discrimination protocols. Especially, our methods enabled us to identify channel discrimination scenarios where classical or quantum memory is required, and to identify the hierarchical and non-hierarchical relationships within adaptive channel discrimination protocols.Featured image: Any causally ordered quantum channel discrimination protocol acting on two uses of a channel $\mathcal{C}$ can be characterised by a state preparation $\rho$, an intermediate quantum instrument $\mathcal{K}_j$, and a final quantum measurement $M^{i\mid j}$, whose setting may depend on the intermediate outcome. While the quantum memory used in the protocol is quantified by the dimensionality of the state and the final measurement, the corresponding classical memory is encoded in the number of outcomes of the intermediate instrument.Popular summaryQuantum technologies often rely on storing information encoded in quantum states in so-called quantum memories, but in practice such quantum memories are always limited. In particular, it is challenging to build memories that coherently store quantum states in a high dimension. A key question is how these limitations affect what quantum protocols can achieve. We address this question using the fundamental task of channel discrimination, where one must identify an unknown physical process from a known set using only a single or limited number of applications. We develop a general framework to quantify how well channel discrimination can be performed when the available memory — classical or quantum — has restricted size. Our approach leads to practical computational methods that provide rigorous bounds on the best achievable performance under these constraints. By applying these tools to both single- and multi-step scenarios, including adaptive strategies, we identify situations where the presence of quantum memory is essential and clarify how the coherent transfer of quantum information enables improved discrimination. Overall, our results provide a systematic way to understand the role of memory resources in quantum information processing.► BibTeX data@article{Ohst2026characterising, doi = {10.22331/q-2026-01-28-1988}, url = {https://doi.org/10.22331/q-2026-01-28-1988}, title = {Characterising memory in quantum channel discrimination via constrained separability problems}, author = {Ohst, Ties-Albrecht and Zhang, Shijun and Nguyen, Hai Chau and Pl{\'{a}}vala, Martin and Quintino, Marco T{\'{u}}lio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1988}, month = jan, year = {2026} }► References [1] N. G. van Kampen. ``Stochastic processes in physics and chemistry''. Elsevier. (2007). https://doi.org/10.1016/B978-0-444-52965-7.X5000-4 [2] Heinz-Peter Breuer and Francesco Petruccione. ``The Theory of Open Quantum Systems''.
Oxford University Press. (2007). https://doi.org/10.1093/acprof:oso/9780199213900.001.0001 [3] Li Li, Michael J. W. Hall, and Howard M. Wiseman. ``Concepts of quantum non-Markovianity: A hierarchy''. Physics Reports 759, 1–51 (2018). arXiv:1712.08879. https://doi.org/10.1016/j.physrep.2018.07.001 arXiv:1712.08879 [4] Inés de Vega and Daniel Alonso. ``Dynamics of non-Markovian open quantum systems''. Reviews of Modern Physics 89, 015001 (2017). arXiv:1511.06994. https://doi.org/10.1103/RevModPhys.89.015001 arXiv:1511.06994 [5] Simon Milz and Kavan Modi. ``Quantum Stochastic Processes and Quantum non-Markovian Phenomena''. PRX Quantum 2, 030201 (2021). arXiv:2012.01894. https://doi.org/10.1103/PRXQuantum.2.030201 arXiv:2012.01894 [6] Philip Taranto, Felix A. Pollock, Simon Milz, Marco Tomamichel, and Kavan Modi. ``Quantum Markov Order''. Phys. Rev. Lett. 122, 140401 (2019). arXiv:1805.11341. https://doi.org/10.1103/PhysRevLett.122.140401 arXiv:1805.11341 [7] Felix A. Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi. ``Operational Markov Condition for Quantum Processes''. Phys. Rev. Lett. 120, 040405 (2018). arXiv:1801.09811. https://doi.org/10.1103/PhysRevLett.120.040405 arXiv:1801.09811 [8] Lucas B. Vieira and Costantino Budroni. ``Temporal correlations in the simplest measurement sequences''. Quantum 6, 623 (2022). arXiv:2104.02467. https://doi.org/10.22331/q-2022-01-18-623 arXiv:2104.02467 [9] Dennis Kretschmann and Reinhard F. Werner. ``Quantum channels with memory''. Phys. Rev. A 72, 062323 (2005). arXiv:quant-ph/0502106. https://doi.org/10.1103/PhysRevA.72.062323 arXiv:quant-ph/0502106 [10] Philip Taranto. ``Memory effects in quantum processes''. International Journal of Quantum Information 18, 1941002–574 (2020). arXiv:1909.05245. https://doi.org/10.1142/S0219749919410028 arXiv:1909.05245 [11] Heinz-Peter Breuer, Elsi-Mari Laine, Jyrki Piilo, and Bassano Vacchini. ``Colloquium: Non-Markovian dynamics in open quantum systems''. Reviews of Modern Physics 88, 021002 (2016). arXiv:1505.01385. https://doi.org/10.1103/RevModPhys.88.021002 arXiv:1505.01385 [12] Lucas B. Vieira, Simon Milz, Giuseppe Vitagliano, and Costantino Budroni. ``Witnessing environment dimension through temporal correlations''. Quantum 8, 1224 (2024). arXiv:2305.19175. https://doi.org/10.22331/q-2024-01-10-1224 arXiv:2305.19175 [13] Denis Rosset, Francesco Buscemi, and Yeong-Cherng Liang. ``Resource theory of quantum memories and their faithful verification with minimal assumptions''. Phys. Rev. X 8, 021033 (2018). arXiv:1710.04710. https://doi.org/10.1103/PhysRevX.8.021033 arXiv:1710.04710 [14] R. Koenig, U. Maurer, and R. Renner. ``On the power of quantum memory''. IEEE Transactions on Information Theory 51, 2391–2401 (2005). arXiv:quant-ph/0305154. https://doi.org/10.1109/tit.2005.850087 arXiv:quant-ph/0305154 [15] Simon Milz, Dario Egloff, Philip Taranto, Thomas Theurer, Martin B. Plenio, Andrea Smirne, and Susana F. Huelga. ``When Is a Non-Markovian Quantum Process Classical?''. Physical Review X 10, 041049 (2020). arXiv:1907.05807. https://doi.org/10.1103/PhysRevX.10.041049 arXiv:1907.05807 [16] Christina Giarmatzi and Fabio Costa. ``Witnessing quantum memory in non-markovian processes''. Quantum 5, 440 (2021). arXiv:1811.03722. https://doi.org/10.22331/q-2021-04-26-440 arXiv:1811.03722 [17] Marcello Nery, Marco Túlio Quintino, Philippe Allard Guérin, Thiago O. Maciel, and Reinaldo O. Vianna. ``Simple and maximally robust processes with no classical common-cause or direct-cause explanation''. Quantum 5, 538 (2021). arXiv:2101.11630. https://doi.org/10.22331/q-2021-09-09-538 arXiv:2101.11630 [18] Philip Taranto, Marco Túlio Quintino, Mio Murao, and Simon Milz. ``Characterising the Hierarchy of Multi-time Quantum Processes with Classical Memory''. Quantum 8, 1328 (2024). arXiv:2307.11905. https://doi.org/10.22331/q-2024-05-02-1328 arXiv:2307.11905 [19] Charles H. Bennett and Stephen J. Wiesner. ``Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states''. Phys. Rev. Lett. 69, 2881–2884 (1992). https://doi.org/10.1103/PhysRevLett.69.2881 [20] Khabat Heshami, Duncan G. England, Peter C. Humphreys, Philip J. Bustard, Victor M. Acosta, Joshua Nunn, and Benjamin J. Sussman. ``Quantum memories: emerging applications and recent advances''. Journal of Modern Optics 63, 2005–2028 (2016). arXiv:1511.04018. https://doi.org/10.1080/09500340.2016.1148212 arXiv:1511.04018 [21] Giulio Chiribella, Giacomo M. D'Ariano, and Paolo Perinotti. ``Memory effects in quantum channel discrimination''. Phys. Rev. Lett. 101, 180501 (2008). arXiv:0803.3237. https://doi.org/10.1103/PhysRevLett.101.180501 arXiv:0803.3237 [22] William Matthews, Marco Piani, and John Watrous. ``Entanglement in channel discrimination with restricted measurements''. Phys. Rev. A 82, 032302 (2010). arXiv:1004.0888. https://doi.org/10.1103/PhysRevA.82.032302 arXiv:1004.0888 [23] Daniel Puzzuoli and John Watrous. ``Ancilla dimension in quantum channel discrimination''.
Annales Henri Poincaré 18, 1153–1184 (2016). arXiv:1604.08197. https://doi.org/10.1007/s00023-016-0537-y arXiv:1604.08197 [24] Marco Piani and John Watrous. ``All entangled states are useful for channel discrimination''. Phys. Rev. Lett. 102, 250501 (2009). arXiv:0901.2118. https://doi.org/10.1103/PhysRevLett.102.250501 arXiv:0901.2118 [25] Anna Jenčová and Martin Plávala. ``Conditions for optimal input states for discrimination of quantum channels''. Journal of Mathematical Physics 57 (2016). arXiv:1603.01437. https://doi.org/10.1063/1.4972286 arXiv:1603.01437 [26] Mario Berta, Francesco Borderi, Omar Fawzi, and Volkher B. Scholz. ``Semidefinite programming hierarchies for constrained bilinear optimization''. Mathematical Programming 194, 781–829 (2021). arXiv:1810.12197. https://doi.org/10.1007/s10107-021-01650-1 arXiv:1810.12197 [27] Stanisław Kurdziałek, Piotr Dulian, Joanna Majsak, Sagnik Chakraborty, and Rafał Demkowicz-Dobrzański. ``Quantum metrology using quantum combs and tensor network formalism''. New Journal of Physics 27, 013019 (2025). https://doi.org/10.1088/1367-2630/ada8d1 [28] D. Cavalcanti, L. Guerini, R. Rabelo, and P. Skrzypczyk. ``General Method for Constructing Local Hidden Variable Models for Entangled Quantum States''. Phys. Rev. Lett. 117, 190401 (2016). arXiv:1512.00277. https://doi.org/10.1103/PhysRevLett.117.190401 arXiv:1512.00277 [29] Flavien Hirsch, Marco Túlio Quintino, Tamás Vértesi, Matthew F. Pusey, and Nicolas Brunner. ``Algorithmic construction of local hidden variable models for entangled quantum states''. Phys. Rev. Lett. 117, 190402 (2016). arXiv:1512.00262. https://doi.org/10.1103/PhysRevLett.117.190402 arXiv:1512.00262 [30] H. Chau Nguyen, Huy-Viet Nguyen, and Otfried Gühne. ``Geometry of Einstein-Podolsky-Rosen correlations''. Phys. Rev. Lett. 122, 240401 (2019). arXiv:1808.09349. https://doi.org/10.1103/PhysRevLett.122.240401 arXiv:1808.09349 [31] Ties-A. Ohst, Xiao-Dong Yu, Otfried Gühne, and H. Chau Nguyen. ``Certifying quantum separability with adaptive polytopes''. SciPost Phys. 16, 063 (2024). arXiv:2210.10054. https://doi.org/10.21468/SciPostPhys.16.3.063 arXiv:2210.10054 [32] Jonathan Steinberg, H. Chau Nguyen, and Matthias Kleinmann. ``Certifying the activation of bell nonlocality with finite data''. Phys. Rev. A 111, 012205 (2025). https://doi.org/10.1103/PhysRevA.111.012205 [33] Aram W. Harrow, Avinatan Hassidim, Debbie W. Leung, and John Watrous. ``Adaptive versus nonadaptive strategies for quantum channel discrimination''. Physical Review A 81 (2010). arXiv:0909.0256. https://doi.org/10.1103/physreva.81.032339 arXiv:0909.0256 [34] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. ``Strict Hierarchy between Parallel, Sequential, and Indefinite-Causal-Order Strategies for Channel Discrimination''. Phys. Rev. Lett. 127, 200504 (2021). arXiv:2011.08300. https://doi.org/10.1103/PhysRevLett.127.200504 arXiv:2011.08300 [35] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. ``Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies''. Journal of Mathematical Physics 63, 042203 (2022). arXiv:2105.13369. https://doi.org/10.1063/5.0075919 arXiv:2105.13369 [36] Mark M. Wilde, Mario Berta, Christoph Hirche, and Eneet Kaur. ``Amortized channel divergence for asymptotic quantum channel discrimination''. Letters in Mathematical Physics 110, 2277–2336 (2020). arXiv:1808.01498. https://doi.org/10.1007/s11005-020-01297-7 arXiv:1808.01498 [37] Farzin Salek, Masahito Hayashi, and Andreas Winter. ``Usefulness of adaptive strategies in asymptotic quantum channel discrimination''. Physical Review A 105 (2022). arXiv:2011.06569. https://doi.org/10.1103/physreva.105.022419 arXiv:2011.06569 [38] Yonglong Li, Christoph Hirche, and Marco Tomamichel. ``Sequential quantum channel discrimination''. In 2022 IEEE International Symposium on Information Theory (ISIT). Page 270–275. IEEE (2022). https://doi.org/10.1109/isit50566.2022.9834768 [39] Charlotte Bäcker, Konstantin Beyer, and Walter T. Strunz. ``Local disclosure of quantum memory in non-markovian dynamics''. Phys. Rev. Lett. 132, 060402 (2024). arXiv:2310.01205. https://doi.org/10.1103/PhysRevLett.132.060402 arXiv:2310.01205 [40] Aram W. Harrow. ``The church of the symmetric subspace'' (2013). arXiv:1308.6595. arXiv:1308.6595 [41] Man-Duen Choi. ``Positive linear maps on C*-algebras''. Canadian Journal of Mathematics 24, 520–529 (1972). https://doi.org/10.4153/cjm-1972-044-5 [42] A. Jamiołkowski. ``Linear transformations which preserve trace and positive semidefiniteness of operators''. Reports on Mathematical Physics 3, 275–278 (1972). https://doi.org/10.1016/0034-4877(72)90011-0 [43] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. ``Theoretical framework for quantum networks''. Phys. Rev. A 80, 022339 (2009). arXiv:0904.4483. https://doi.org/10.1103/PhysRevA.80.022339 arXiv:0904.4483 [44] Mário Ziman. ``Process positive-operator-valued measure: A mathematical framework for the description of process tomography experiments''. Phys. Rev. A 77, 062112 (2008). arXiv:0802.3862. https://doi.org/10.1103/PhysRevA.77.062112 arXiv:0802.3862 [45] R. F. Werner and A. S. Holevo. ``Counterexample to an additivity conjecture for output purity of quantum channels''. Journal of Mathematical Physics 43, 4353–4357 (2002). arXiv:quant-ph/0203003. https://doi.org/10.1063/1.1498491 arXiv:quant-ph/0203003 [46] Stephen Boyd and Lieven Vandenberghe. ``Convex optimization''.
Cambridge University Press. (2004). https://doi.org/10.1017/CBO9780511804441 [47] Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. ``Complete family of separability criteria''. Phys. Rev. A 69, 022308 (2004). arXiv:quant-ph/0308032. https://doi.org/10.1103/PhysRevA.69.022308 arXiv:quant-ph/0308032 [48] Ties-A. Ohst. ``Git repository: Quantum channel discrimination with limited memory''. https://gitlab.com/TiesA/quantum-channel-discrimination-with-limited-memory (2024). https://gitlab.com/TiesA/quantum-channel-discrimination-with-limited-memory [49] Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. ``On the necessary and sufficient conditions for separability of mixed quantum states''. Phys. Lett. A 223, 1 (1996). arXiv:quant-ph/9605038. https://doi.org/10.1016/S0375-9601(96)00706-2 arXiv:quant-ph/9605038 [50] Jessica Bavaresco, Patryk Lipka-Bartosik, Pavel Sekatski, and Mohammad Mehboudi. ``Designing optimal protocols in Bayesian quantum parameter estimation with higher-order operations''. Phys. Rev. Res. 6, 023305 (2024). arXiv:2311.01513. https://doi.org/10.1103/PhysRevResearch.6.023305 arXiv:2311.01513 [51] Otfried Gühne and Géza Tóth. ``Entanglement detection''. Phys. Rep. 474, 1–75 (2009). arXiv:0811.2803. https://doi.org/10.1016/j.physrep.2009.02.004 arXiv:0811.2803 [52] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. ``Quantum entanglement''. Rev. Mod. Phys. 81, 865–942 (2009). arXiv:quant-ph/0702225. https://doi.org/10.1103/RevModPhys.81.865 arXiv:quant-ph/0702225 [53] Leonid Gurvits. ``Classical complexity and quantum entanglement''. Journal of Computer and System Sciences 69, 448–484 (2004). arXiv:quant-ph/0303055. https://doi.org/10.1016/j.jcss.2004.06.003 arXiv:quant-ph/0303055 [54] Carlton M. Caves, Christopher A. Fuchs, and Rüdiger Schack. ``Unknown quantum states: The quantum de Finetti representation''. Journal of Mathematical Physics 43, 4537–4559 (2002). arXiv:quant-ph/0104088. https://doi.org/10.1063/1.1494475 arXiv:quant-ph/0104088 [55] Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner. ``One-and-a-half quantum de Finetti theorems''. Communications in Mathematical Physics 273, 473–498 (2007). arXiv:quant-ph/0602130. https://doi.org/10.1007/s00220-007-0189-3 arXiv:quant-ph/0602130 [56] Guillaume Aubrun, Alexander Müller-Hermes, and Martin Plávala. ``Monogamy of entanglement between cones''. Mathematische AnnalenPages 1–19 (2024). arXiv:2206.11805. https://doi.org/10.1007/s00208-024-02935-4 arXiv:2206.11805 [57] Fabio Costa, Jonathan Barrett, and Sally Shrapnel. ``A de Finetti theorem for quantum causal structures''. Quantum 9, 1628 (2025). https://doi.org/10.22331/q-2025-02-11-1628 [58] Paula Belzig. ``Studying Stabilizer de Finetti Theorems and Possible Applications in Quantum Information Processing'' (2024). arXiv:2403.10592. arXiv:2403.10592 [59] Kenji Nakahira. ``Quantum process discrimination with restricted strategies''. Phys. Rev. A 104, 062609 (2021). arXiv:2104.09038. https://doi.org/10.1103/PhysRevA.104.062609 arXiv:2104.09038 [60] Michael Horodecki, Peter W. Shor, and Mary Beth Ruskai. ``Entanglement breaking channels''. Reviews in Mathematical Physics 15, 629–641 (2003). arXiv:quant-ph/0302031. https://doi.org/10.1142/s0129055x03001709 arXiv:quant-ph/0302031 [61] G. Chiribella, G. M. D'Ariano, P. Perinotti, and M. F. Sacchi. ``Maximum likelihood estimation for a group of physical transformations''. International Journal of Quantum Information 04, 453–472 (2006). arXiv:quant-ph/0507007. https://doi.org/10.1142/S0219749906002018 arXiv:quant-ph/0507007 [62] Jean-Pierre Serre. ``Linear representations of finite groups''.
Springer New York. (1977). https://doi.org/10.1007/978-1-4684-9458-7 [63] Jochen Gorski, Frank Pfeuffer, and Kathrin Klamroth. ``Biconvex sets and optimization with biconvex functions: a survey and extensions''. Mathematical Methods of Operations Research 66, 373–407 (2007). https://doi.org/10.1007/s00186-007-0161-1 [64] T.S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall. ``The double description method''. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games II.
Princeton University Press (1953). [65] Asher Peres. ``Separability criterion for density matrices''. Phys. Rev. Lett. 77, 1413–1415 (1996). arXiv:quant-ph/9604005. https://doi.org/10.1103/PhysRevLett.77.1413 arXiv:quant-ph/9604005 [66] Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki. ``Separability of mixed states: necessary and sufficient conditions''. Physics Letters A 223, 1–8 (1996). arXiv:quant-ph/9605038. https://doi.org/10.1016/s0375-9601(96)00706-2 arXiv:quant-ph/9605038 [67] Xiao-Dong Yu, Timo Simnacher, H. Chau Nguyen, and Otfried Gühne. ``Quantum-inspired hierarchy for rank-constrained optimization''. PRX Quantum 3, 010340 (2022). arXiv:2012.00554. https://doi.org/10.1103/PRXQuantum.3.010340 arXiv:2012.00554 [68] Nicholas M Katz. ``A conjecture in the arithmetic theory of differential equations''. Bulletin de la Société Mathématique de France 110, 203–239 (1982). https://doi.org/10.24033/bsmf.1960 [69] Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain. ``Symmetric tensors and symmetric tensor rank''. SIAM Journal on Matrix Analysis and Applications 30, 1254–1279 (2008). arXiv:0802.1681. https://doi.org/10.1137/060661569 arXiv:0802.1681 [70] Jürgen Eckhoff. ``Helly, Radon, and Carathéodory type theorems''. Page 389–448. Elsevier. (1993). https://doi.org/10.1016/b978-0-444-89596-7.50017-1Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-28 10:11:00: Could not fetch cited-by data for 10.22331/q-2026-01-28-1988 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-28 10:11:01: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractQuantum memories are a crucial precondition in many protocols for processing quantum information. A fundamental problem that illustrates this statement is given by the task of channel discrimination, in which an unknown channel drawn from a known random ensemble should be determined by applying it for a single time. In this paper, we characterise the quality of channel discrimination protocols when the quantum memory, quantified by the auxiliary dimension, is limited. This is achieved by formulating the problem in terms of separable quantum states with additional affine constraints that all of their factors in each separable decomposition obey. We discuss the computation of upper and lower bounds to the solutions of such problems which allow for new insights into the role of memory in channel discrimination. In addition to the single-copy scenario, this methodological insight allows to systematically characterise quantum and classical memories in adaptive channel discrimination protocols. Especially, our methods enabled us to identify channel discrimination scenarios where classical or quantum memory is required, and to identify the hierarchical and non-hierarchical relationships within adaptive channel discrimination protocols.Featured image: Any causally ordered quantum channel discrimination protocol acting on two uses of a channel $\mathcal{C}$ can be characterised by a state preparation $\rho$, an intermediate quantum instrument $\mathcal{K}_j$, and a final quantum measurement $M^{i\mid j}$, whose setting may depend on the intermediate outcome. While the quantum memory used in the protocol is quantified by the dimensionality of the state and the final measurement, the corresponding classical memory is encoded in the number of outcomes of the intermediate instrument.Popular summaryQuantum technologies often rely on storing information encoded in quantum states in so-called quantum memories, but in practice such quantum memories are always limited. In particular, it is challenging to build memories that coherently store quantum states in a high dimension. A key question is how these limitations affect what quantum protocols can achieve. We address this question using the fundamental task of channel discrimination, where one must identify an unknown physical process from a known set using only a single or limited number of applications. We develop a general framework to quantify how well channel discrimination can be performed when the available memory — classical or quantum — has restricted size. Our approach leads to practical computational methods that provide rigorous bounds on the best achievable performance under these constraints. By applying these tools to both single- and multi-step scenarios, including adaptive strategies, we identify situations where the presence of quantum memory is essential and clarify how the coherent transfer of quantum information enables improved discrimination. Overall, our results provide a systematic way to understand the role of memory resources in quantum information processing.► BibTeX data@article{Ohst2026characterising, doi = {10.22331/q-2026-01-28-1988}, url = {https://doi.org/10.22331/q-2026-01-28-1988}, title = {Characterising memory in quantum channel discrimination via constrained separability problems}, author = {Ohst, Ties-Albrecht and Zhang, Shijun and Nguyen, Hai Chau and Pl{\'{a}}vala, Martin and Quintino, Marco T{\'{u}}lio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1988}, month = jan, year = {2026} }► References [1] N. G. van Kampen. ``Stochastic processes in physics and chemistry''. Elsevier. (2007). https://doi.org/10.1016/B978-0-444-52965-7.X5000-4 [2] Heinz-Peter Breuer and Francesco Petruccione. ``The Theory of Open Quantum Systems''.
Oxford University Press. (2007). https://doi.org/10.1093/acprof:oso/9780199213900.001.0001 [3] Li Li, Michael J. W. Hall, and Howard M. Wiseman. ``Concepts of quantum non-Markovianity: A hierarchy''. Physics Reports 759, 1–51 (2018). arXiv:1712.08879. https://doi.org/10.1016/j.physrep.2018.07.001 arXiv:1712.08879 [4] Inés de Vega and Daniel Alonso. ``Dynamics of non-Markovian open quantum systems''. Reviews of Modern Physics 89, 015001 (2017). arXiv:1511.06994. https://doi.org/10.1103/RevModPhys.89.015001 arXiv:1511.06994 [5] Simon Milz and Kavan Modi. ``Quantum Stochastic Processes and Quantum non-Markovian Phenomena''. PRX Quantum 2, 030201 (2021). arXiv:2012.01894. https://doi.org/10.1103/PRXQuantum.2.030201 arXiv:2012.01894 [6] Philip Taranto, Felix A. Pollock, Simon Milz, Marco Tomamichel, and Kavan Modi. ``Quantum Markov Order''. Phys. Rev. Lett. 122, 140401 (2019). arXiv:1805.11341. https://doi.org/10.1103/PhysRevLett.122.140401 arXiv:1805.11341 [7] Felix A. Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi. ``Operational Markov Condition for Quantum Processes''. Phys. Rev. Lett. 120, 040405 (2018). arXiv:1801.09811. https://doi.org/10.1103/PhysRevLett.120.040405 arXiv:1801.09811 [8] Lucas B. Vieira and Costantino Budroni. ``Temporal correlations in the simplest measurement sequences''. Quantum 6, 623 (2022). arXiv:2104.02467. https://doi.org/10.22331/q-2022-01-18-623 arXiv:2104.02467 [9] Dennis Kretschmann and Reinhard F. Werner. ``Quantum channels with memory''. Phys. Rev. A 72, 062323 (2005). arXiv:quant-ph/0502106. https://doi.org/10.1103/PhysRevA.72.062323 arXiv:quant-ph/0502106 [10] Philip Taranto. ``Memory effects in quantum processes''. International Journal of Quantum Information 18, 1941002–574 (2020). arXiv:1909.05245. https://doi.org/10.1142/S0219749919410028 arXiv:1909.05245 [11] Heinz-Peter Breuer, Elsi-Mari Laine, Jyrki Piilo, and Bassano Vacchini. ``Colloquium: Non-Markovian dynamics in open quantum systems''. Reviews of Modern Physics 88, 021002 (2016). arXiv:1505.01385. https://doi.org/10.1103/RevModPhys.88.021002 arXiv:1505.01385 [12] Lucas B. Vieira, Simon Milz, Giuseppe Vitagliano, and Costantino Budroni. ``Witnessing environment dimension through temporal correlations''. Quantum 8, 1224 (2024). arXiv:2305.19175. https://doi.org/10.22331/q-2024-01-10-1224 arXiv:2305.19175 [13] Denis Rosset, Francesco Buscemi, and Yeong-Cherng Liang. ``Resource theory of quantum memories and their faithful verification with minimal assumptions''. Phys. Rev. X 8, 021033 (2018). arXiv:1710.04710. https://doi.org/10.1103/PhysRevX.8.021033 arXiv:1710.04710 [14] R. Koenig, U. Maurer, and R. Renner. ``On the power of quantum memory''. IEEE Transactions on Information Theory 51, 2391–2401 (2005). arXiv:quant-ph/0305154. https://doi.org/10.1109/tit.2005.850087 arXiv:quant-ph/0305154 [15] Simon Milz, Dario Egloff, Philip Taranto, Thomas Theurer, Martin B. Plenio, Andrea Smirne, and Susana F. Huelga. ``When Is a Non-Markovian Quantum Process Classical?''. Physical Review X 10, 041049 (2020). arXiv:1907.05807. https://doi.org/10.1103/PhysRevX.10.041049 arXiv:1907.05807 [16] Christina Giarmatzi and Fabio Costa. ``Witnessing quantum memory in non-markovian processes''. Quantum 5, 440 (2021). arXiv:1811.03722. https://doi.org/10.22331/q-2021-04-26-440 arXiv:1811.03722 [17] Marcello Nery, Marco Túlio Quintino, Philippe Allard Guérin, Thiago O. Maciel, and Reinaldo O. Vianna. ``Simple and maximally robust processes with no classical common-cause or direct-cause explanation''. Quantum 5, 538 (2021). arXiv:2101.11630. https://doi.org/10.22331/q-2021-09-09-538 arXiv:2101.11630 [18] Philip Taranto, Marco Túlio Quintino, Mio Murao, and Simon Milz. ``Characterising the Hierarchy of Multi-time Quantum Processes with Classical Memory''. Quantum 8, 1328 (2024). arXiv:2307.11905. https://doi.org/10.22331/q-2024-05-02-1328 arXiv:2307.11905 [19] Charles H. Bennett and Stephen J. Wiesner. ``Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states''. Phys. Rev. Lett. 69, 2881–2884 (1992). https://doi.org/10.1103/PhysRevLett.69.2881 [20] Khabat Heshami, Duncan G. England, Peter C. Humphreys, Philip J. Bustard, Victor M. Acosta, Joshua Nunn, and Benjamin J. Sussman. ``Quantum memories: emerging applications and recent advances''. Journal of Modern Optics 63, 2005–2028 (2016). arXiv:1511.04018. https://doi.org/10.1080/09500340.2016.1148212 arXiv:1511.04018 [21] Giulio Chiribella, Giacomo M. D'Ariano, and Paolo Perinotti. ``Memory effects in quantum channel discrimination''. Phys. Rev. Lett. 101, 180501 (2008). arXiv:0803.3237. https://doi.org/10.1103/PhysRevLett.101.180501 arXiv:0803.3237 [22] William Matthews, Marco Piani, and John Watrous. ``Entanglement in channel discrimination with restricted measurements''. Phys. Rev. A 82, 032302 (2010). arXiv:1004.0888. https://doi.org/10.1103/PhysRevA.82.032302 arXiv:1004.0888 [23] Daniel Puzzuoli and John Watrous. ``Ancilla dimension in quantum channel discrimination''.
Annales Henri Poincaré 18, 1153–1184 (2016). arXiv:1604.08197. https://doi.org/10.1007/s00023-016-0537-y arXiv:1604.08197 [24] Marco Piani and John Watrous. ``All entangled states are useful for channel discrimination''. Phys. Rev. Lett. 102, 250501 (2009). arXiv:0901.2118. https://doi.org/10.1103/PhysRevLett.102.250501 arXiv:0901.2118 [25] Anna Jenčová and Martin Plávala. ``Conditions for optimal input states for discrimination of quantum channels''. Journal of Mathematical Physics 57 (2016). arXiv:1603.01437. https://doi.org/10.1063/1.4972286 arXiv:1603.01437 [26] Mario Berta, Francesco Borderi, Omar Fawzi, and Volkher B. Scholz. ``Semidefinite programming hierarchies for constrained bilinear optimization''. Mathematical Programming 194, 781–829 (2021). arXiv:1810.12197. https://doi.org/10.1007/s10107-021-01650-1 arXiv:1810.12197 [27] Stanisław Kurdziałek, Piotr Dulian, Joanna Majsak, Sagnik Chakraborty, and Rafał Demkowicz-Dobrzański. ``Quantum metrology using quantum combs and tensor network formalism''. New Journal of Physics 27, 013019 (2025). https://doi.org/10.1088/1367-2630/ada8d1 [28] D. Cavalcanti, L. Guerini, R. Rabelo, and P. Skrzypczyk. ``General Method for Constructing Local Hidden Variable Models for Entangled Quantum States''. Phys. Rev. Lett. 117, 190401 (2016). arXiv:1512.00277. https://doi.org/10.1103/PhysRevLett.117.190401 arXiv:1512.00277 [29] Flavien Hirsch, Marco Túlio Quintino, Tamás Vértesi, Matthew F. Pusey, and Nicolas Brunner. ``Algorithmic construction of local hidden variable models for entangled quantum states''. Phys. Rev. Lett. 117, 190402 (2016). arXiv:1512.00262. https://doi.org/10.1103/PhysRevLett.117.190402 arXiv:1512.00262 [30] H. Chau Nguyen, Huy-Viet Nguyen, and Otfried Gühne. ``Geometry of Einstein-Podolsky-Rosen correlations''. Phys. Rev. Lett. 122, 240401 (2019). arXiv:1808.09349. https://doi.org/10.1103/PhysRevLett.122.240401 arXiv:1808.09349 [31] Ties-A. Ohst, Xiao-Dong Yu, Otfried Gühne, and H. Chau Nguyen. ``Certifying quantum separability with adaptive polytopes''. SciPost Phys. 16, 063 (2024). arXiv:2210.10054. https://doi.org/10.21468/SciPostPhys.16.3.063 arXiv:2210.10054 [32] Jonathan Steinberg, H. Chau Nguyen, and Matthias Kleinmann. ``Certifying the activation of bell nonlocality with finite data''. Phys. Rev. A 111, 012205 (2025). https://doi.org/10.1103/PhysRevA.111.012205 [33] Aram W. Harrow, Avinatan Hassidim, Debbie W. Leung, and John Watrous. ``Adaptive versus nonadaptive strategies for quantum channel discrimination''. Physical Review A 81 (2010). arXiv:0909.0256. https://doi.org/10.1103/physreva.81.032339 arXiv:0909.0256 [34] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. ``Strict Hierarchy between Parallel, Sequential, and Indefinite-Causal-Order Strategies for Channel Discrimination''. Phys. Rev. Lett. 127, 200504 (2021). arXiv:2011.08300. https://doi.org/10.1103/PhysRevLett.127.200504 arXiv:2011.08300 [35] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. ``Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies''. Journal of Mathematical Physics 63, 042203 (2022). arXiv:2105.13369. https://doi.org/10.1063/5.0075919 arXiv:2105.13369 [36] Mark M. Wilde, Mario Berta, Christoph Hirche, and Eneet Kaur. ``Amortized channel divergence for asymptotic quantum channel discrimination''. Letters in Mathematical Physics 110, 2277–2336 (2020). arXiv:1808.01498. https://doi.org/10.1007/s11005-020-01297-7 arXiv:1808.01498 [37] Farzin Salek, Masahito Hayashi, and Andreas Winter. ``Usefulness of adaptive strategies in asymptotic quantum channel discrimination''. Physical Review A 105 (2022). arXiv:2011.06569. https://doi.org/10.1103/physreva.105.022419 arXiv:2011.06569 [38] Yonglong Li, Christoph Hirche, and Marco Tomamichel. ``Sequential quantum channel discrimination''. In 2022 IEEE International Symposium on Information Theory (ISIT). Page 270–275. IEEE (2022). https://doi.org/10.1109/isit50566.2022.9834768 [39] Charlotte Bäcker, Konstantin Beyer, and Walter T. Strunz. ``Local disclosure of quantum memory in non-markovian dynamics''. Phys. Rev. Lett. 132, 060402 (2024). arXiv:2310.01205. https://doi.org/10.1103/PhysRevLett.132.060402 arXiv:2310.01205 [40] Aram W. Harrow. ``The church of the symmetric subspace'' (2013). arXiv:1308.6595. arXiv:1308.6595 [41] Man-Duen Choi. ``Positive linear maps on C*-algebras''. Canadian Journal of Mathematics 24, 520–529 (1972). https://doi.org/10.4153/cjm-1972-044-5 [42] A. Jamiołkowski. ``Linear transformations which preserve trace and positive semidefiniteness of operators''. Reports on Mathematical Physics 3, 275–278 (1972). https://doi.org/10.1016/0034-4877(72)90011-0 [43] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. ``Theoretical framework for quantum networks''. Phys. Rev. A 80, 022339 (2009). arXiv:0904.4483. https://doi.org/10.1103/PhysRevA.80.022339 arXiv:0904.4483 [44] Mário Ziman. ``Process positive-operator-valued measure: A mathematical framework for the description of process tomography experiments''. Phys. Rev. A 77, 062112 (2008). arXiv:0802.3862. https://doi.org/10.1103/PhysRevA.77.062112 arXiv:0802.3862 [45] R. F. Werner and A. S. Holevo. ``Counterexample to an additivity conjecture for output purity of quantum channels''. Journal of Mathematical Physics 43, 4353–4357 (2002). arXiv:quant-ph/0203003. https://doi.org/10.1063/1.1498491 arXiv:quant-ph/0203003 [46] Stephen Boyd and Lieven Vandenberghe. ``Convex optimization''.
Cambridge University Press. (2004). https://doi.org/10.1017/CBO9780511804441 [47] Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. ``Complete family of separability criteria''. Phys. Rev. A 69, 022308 (2004). arXiv:quant-ph/0308032. https://doi.org/10.1103/PhysRevA.69.022308 arXiv:quant-ph/0308032 [48] Ties-A. Ohst. ``Git repository: Quantum channel discrimination with limited memory''. https://gitlab.com/TiesA/quantum-channel-discrimination-with-limited-memory (2024). https://gitlab.com/TiesA/quantum-channel-discrimination-with-limited-memory [49] Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. ``On the necessary and sufficient conditions for separability of mixed quantum states''. Phys. Lett. A 223, 1 (1996). arXiv:quant-ph/9605038. https://doi.org/10.1016/S0375-9601(96)00706-2 arXiv:quant-ph/9605038 [50] Jessica Bavaresco, Patryk Lipka-Bartosik, Pavel Sekatski, and Mohammad Mehboudi. ``Designing optimal protocols in Bayesian quantum parameter estimation with higher-order operations''. Phys. Rev. Res. 6, 023305 (2024). arXiv:2311.01513. https://doi.org/10.1103/PhysRevResearch.6.023305 arXiv:2311.01513 [51] Otfried Gühne and Géza Tóth. ``Entanglement detection''. Phys. Rep. 474, 1–75 (2009). arXiv:0811.2803. https://doi.org/10.1016/j.physrep.2009.02.004 arXiv:0811.2803 [52] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. ``Quantum entanglement''. Rev. Mod. Phys. 81, 865–942 (2009). arXiv:quant-ph/0702225. https://doi.org/10.1103/RevModPhys.81.865 arXiv:quant-ph/0702225 [53] Leonid Gurvits. ``Classical complexity and quantum entanglement''. Journal of Computer and System Sciences 69, 448–484 (2004). arXiv:quant-ph/0303055. https://doi.org/10.1016/j.jcss.2004.06.003 arXiv:quant-ph/0303055 [54] Carlton M. Caves, Christopher A. Fuchs, and Rüdiger Schack. ``Unknown quantum states: The quantum de Finetti representation''. Journal of Mathematical Physics 43, 4537–4559 (2002). arXiv:quant-ph/0104088. https://doi.org/10.1063/1.1494475 arXiv:quant-ph/0104088 [55] Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner. ``One-and-a-half quantum de Finetti theorems''. Communications in Mathematical Physics 273, 473–498 (2007). arXiv:quant-ph/0602130. https://doi.org/10.1007/s00220-007-0189-3 arXiv:quant-ph/0602130 [56] Guillaume Aubrun, Alexander Müller-Hermes, and Martin Plávala. ``Monogamy of entanglement between cones''. Mathematische AnnalenPages 1–19 (2024). arXiv:2206.11805. https://doi.org/10.1007/s00208-024-02935-4 arXiv:2206.11805 [57] Fabio Costa, Jonathan Barrett, and Sally Shrapnel. ``A de Finetti theorem for quantum causal structures''. Quantum 9, 1628 (2025). https://doi.org/10.22331/q-2025-02-11-1628 [58] Paula Belzig. ``Studying Stabilizer de Finetti Theorems and Possible Applications in Quantum Information Processing'' (2024). arXiv:2403.10592. arXiv:2403.10592 [59] Kenji Nakahira. ``Quantum process discrimination with restricted strategies''. Phys. Rev. A 104, 062609 (2021). arXiv:2104.09038. https://doi.org/10.1103/PhysRevA.104.062609 arXiv:2104.09038 [60] Michael Horodecki, Peter W. Shor, and Mary Beth Ruskai. ``Entanglement breaking channels''. Reviews in Mathematical Physics 15, 629–641 (2003). arXiv:quant-ph/0302031. https://doi.org/10.1142/s0129055x03001709 arXiv:quant-ph/0302031 [61] G. Chiribella, G. M. D'Ariano, P. Perinotti, and M. F. Sacchi. ``Maximum likelihood estimation for a group of physical transformations''. International Journal of Quantum Information 04, 453–472 (2006). arXiv:quant-ph/0507007. https://doi.org/10.1142/S0219749906002018 arXiv:quant-ph/0507007 [62] Jean-Pierre Serre. ``Linear representations of finite groups''.
Springer New York. (1977). https://doi.org/10.1007/978-1-4684-9458-7 [63] Jochen Gorski, Frank Pfeuffer, and Kathrin Klamroth. ``Biconvex sets and optimization with biconvex functions: a survey and extensions''. Mathematical Methods of Operations Research 66, 373–407 (2007). https://doi.org/10.1007/s00186-007-0161-1 [64] T.S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall. ``The double description method''. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games II.
Princeton University Press (1953). [65] Asher Peres. ``Separability criterion for density matrices''. Phys. Rev. Lett. 77, 1413–1415 (1996). arXiv:quant-ph/9604005. https://doi.org/10.1103/PhysRevLett.77.1413 arXiv:quant-ph/9604005 [66] Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki. ``Separability of mixed states: necessary and sufficient conditions''. Physics Letters A 223, 1–8 (1996). arXiv:quant-ph/9605038. https://doi.org/10.1016/s0375-9601(96)00706-2 arXiv:quant-ph/9605038 [67] Xiao-Dong Yu, Timo Simnacher, H. Chau Nguyen, and Otfried Gühne. ``Quantum-inspired hierarchy for rank-constrained optimization''. PRX Quantum 3, 010340 (2022). arXiv:2012.00554. https://doi.org/10.1103/PRXQuantum.3.010340 arXiv:2012.00554 [68] Nicholas M Katz. ``A conjecture in the arithmetic theory of differential equations''. Bulletin de la Société Mathématique de France 110, 203–239 (1982). https://doi.org/10.24033/bsmf.1960 [69] Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain. ``Symmetric tensors and symmetric tensor rank''. SIAM Journal on Matrix Analysis and Applications 30, 1254–1279 (2008). arXiv:0802.1681. https://doi.org/10.1137/060661569 arXiv:0802.1681 [70] Jürgen Eckhoff. ``Helly, Radon, and Carathéodory type theorems''. Page 389–448. Elsevier. (1993). https://doi.org/10.1016/b978-0-444-89596-7.50017-1Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-28 10:11:00: Could not fetch cited-by data for 10.22331/q-2026-01-28-1988 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-28 10:11:01: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.