Uncloneable Quantum Advice
The famous no-cloning principle has been shown recently to enable a number of uncloneable functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We show the unconditional existence of promise problems admitting uncloneable quantum advice, and the existence of languages with uncloneable advice, assuming the feasibility of quantum copy-protecting certain functions. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) - which concern the computational difficulty of synthesizing sequences of quantum states - can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems.
Our proof technique establishes the existence of ingenerable sequences of finite bit strings - essentially meaning that they cannot be generated by any uniform circuit family. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.
Broadbent, A., Karvonen, M. & Lord, S. (2023). Uncloneable Quantum Advice
PDF
ArXiv
Categorical composable cryptography: extended version
We formalize the key ideas of constructive cryptography in categorical terms. This results in viewing cryptography as a resource theory in the sense of Fritz, Coecke & Spekkens: the resources are cryptographic functionalities and resources conversions are protocols that transform securely such resources to others. Our model is able to incorporate computational security, set-up assumptions and various attack models such as colluding or independently acting subsets of adversaries in a modular, flexible fashion. We also use string diagrams to rederive the security of the one-time pad and no-go results concerning the limits of bipartite and tripartite cryptography, ruling out e.g. composable commitments and broadcasting. On the way, we exhibit two categorical constructions of resource theories that might be of independent interest: one capturing resources shared among n parties and one capturing resource conversions that succeed asymptotically.
Broadbent, A., & Karvonen, M. (2022). Categorical composable cryptography: extended version.
PDF
ArXiv
Inner autoequivalences in general and those of monoidal categories in particular
Our main result states that inner autoequivalences of monoidal categories are essentially the same as conjugations by a weakly invertible element. For this to be a theorem, there needs to be a general theory of inner autoequivalences, and indeed there is: developing that is the other main contribution.
Hofstra, P., & Karvonen, M. (2022). Inner autoequivalences in general and those of monoidal categories in particular.
PDF
ArXiv
Closing Bell: Boxing Black Box Simulations in the Resource Theory of Contextuality
After an exposition of the sheaf-theoretic approach to contextuality, we discuss and answer the following question: given a function that maps empirical models over a scenario S to those over a scenario T, when is this function induced by a mapping between the scenarios? To answer this, we build a new scenario out of S and T, and associate to any such function an empirical model over this. Modulo some technicalities, a function between models is then induced by a map of scenarios iff the corresponding model is noncontextual.
Barbosa, R. S., Karvonen, M., & Mansfield, S. (2023). Closing Bell: Boxing Black Box Simulations in the Resource Theory of Contextuality. In Samson Abramsky on Logic and Structure in Computer Science and Beyond.
PDF
BibTeX
ArXiv
Book Chapter
Categorical composable cryptography
We formalize the simulation paradigm of cryptography in terms of category theory and show that protocols secure against abstract attacks form a symmetric monoidal category, thus giving an abstract model of composable security definitions in cryptography. Our model is able to incorporate computational security, set-up assumptions and various attack models such as colluding or independently acting subsets of adversaries in a modular, flexible fashion. We conclude by using string diagrams to rederive the security of the one-time pad and no-go results concerning the limits of bipartite and tripartite cryptography, ruling out e.g., composable commitments and broadcasting.
Broadbent, A., & Karvonen, M. (2022). Categorical composable cryptography. In Foundations of Software Science and Computation Structures (FoSSaCS) 2022.
PDF
BibTeX
ArXiv
Proceedings
Neither Contextuality nor Nonlocality Admits Catalysts
It turns out that there are no catalysts for contextuality nor for non-locality. This is in contrast with entanglement, for which catalysts famously exist.
Karvonen, M. (2021). Neither Contextuality nor Nonlocality Admits Catalysts. Phys. Rev. Lett. 127, 160402
PDF
BibTeX
ArXiv
Journal
Biproducts without pointedness
Turns out one can define a well-behaved notion of a biproduct in any category without assuming pointedness.
Karvonen, M. (2020). Biproducts without pointedness. Cahiers de topologie et géométrie différentielle catégoriques, Vol LXI, Issue 3, 229-238.
PDF
BibTeX
ArXiv
Journal
A comonadic view of simulation and quantum resources
We simplify and generalize the ideas in the QPL paper below.
Abramsky, S., Barbosa, R. S., Karvonen, M., & Mansfield, S. (2019). A comonadic view of simulation and quantum resources. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE.
PDF
BibTeX
ArXiv
Proceedings
Limits in dagger categories
We define a notion of limit suitable for dagger categories and explore it.
Heunen, C., & Karvonen, M. (2019). Limits in dagger categories. Theory and Applications of Categories, Vol. 34, No. 18, 468-513.
PDF
BibTeX
ArXiv
Journal
Reversible effects as inverse arrows
We study (reversible) side-effects in a reversible programming language. As reversible computing can be modelled by inverse categories, we model side-effects using a notion of arrow suitable for inverse categories. Since inverse categories can be defined as certain dagger categories, we also develop a notion of a dagger arrow.
Heunen, C., Kaarsgaard, R., & Karvonen, M. (2018). Reversible effects as inverse arrows. Proceedings of MFPS 2018. ENTCS, 341, 179-199.
PDF
BibTeX
ArXiv
Proceedings
Categories of Empirical Models
A notion of morphism that is suitable for the sheaf-theoretic approach to contextuality is developed, resulting in a resource theory for contextuality.
Karvonen, M. (2018). Categories of empirical models. Proceedings of QPL 2018, EPTCS 287, pp. 239-252.
PDF
BibTeX
ArXiv
Monads on dagger categories
This is the extended version of the previous conference paper.
Heunen, C., & Karvonen, M. (2016). Monads on dagger categories. Theory and Applications of Categories, Vol. 31, No. 35, 1016-1043.
PDF
BibTeX
ArXiv
Journal
Reversible monadic computing
Heunen, C., & Karvonen, M. (2015). Reversible monadic computing. Electronic Notes in Theoretical Computer Science, 319, 217-237.
PDF
BibTeX
ArXiv
Proceedings
