{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T20:29:25Z","timestamp":1773520165226,"version":"3.50.1"},"reference-count":26,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T00:00:00Z","timestamp":1598572800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Unitary <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>-designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>-designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>d<\/mml:mi><mml:mi>t<\/mml:mi><\/mml:msup><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"normal\">p<\/mml:mi><mml:mi mathvariant=\"normal\">o<\/mml:mi><mml:mi mathvariant=\"normal\">l<\/mml:mi><mml:mi mathvariant=\"normal\">y<\/mml:mi><\/mml:mrow><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>t<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>log<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mi>d<\/mml:mi><mml:mo>,<\/mml:mo><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>\u03f5<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> unitaries from an exact <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>-design provides with positive probability an <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-approximate <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>-design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.<\/jats:p>","DOI":"10.22331\/q-2020-08-28-313","type":"journal-article","created":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T15:03:46Z","timestamp":1598627026000},"page":"313","source":"Crossref","is-referenced-by-count":10,"title":["Weak approximate unitary designs and applications to quantum encryption"],"prefix":"10.22331","volume":"4","author":[{"given":"C\u00e9cilia","family":"Lancien","sequence":"first","affiliation":[{"name":"Institut de Math\u00e9matiques de Toulouse & CNRS, Universit\u00e9 Paul Sabatier, 118 route de Narbonne, F-31062 Toulouse Cedex 9, France."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Majenz","sequence":"additional","affiliation":[{"name":"QuSoft and Centrum Wiskunde & Informatica, Science Park 123, 1098 XG Amsterdam, the Netherlands."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,8,28]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Andris Ambainis, Jan Bouda, and Andreas Winter, ``Nonmalleable encryption of quantum information'' Journal of Mathematical Physics 50, 042106 (2009).","DOI":"10.1063\/1.3094756"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Anura Abeyesinghe, Igor Devetak, Patrick Hayden, and Andreas Winter, ``The mother of all protocols: Restructuring quantum information's family tree'' Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 465, 2537\u20132563 (2009).","DOI":"10.1098\/rspa.2009.0202"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Gorjan Alagic and Christian Majenz ``Quantum Non-malleability and Authentication'' Advances in Cryptology \u2013 CRYPTO 2017 310\u2013341 (2017).","DOI":"10.1007\/978-3-319-63715-0_11"},{"key":"3","unstructured":"Gorjan Alagic, Christian Majenz, and Alexander Russell, ``Efficient simulation of random states and random unitaries'' Cryptology ePrint Archive, Report 2019\/1204 (2019)."},{"key":"4","doi-asserted-by":"publisher","unstructured":"Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald De Wolf, ``Private quantum channels'' Proceedings 41st Annual Symposium on Foundations of Computer Science 547\u2013553 (2000).","DOI":"10.1109\/SFCS.2000.892142"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Guillaume Aubrun ``On almost randomizing channels with a short Kraus decomposition'' Communications in Mathematical Physics 288, 1103\u20131116 (2009).","DOI":"10.1007\/s00220-008-0695-y"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and Alain Tapp, ``Authentication of quantum messages'' The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 449\u2013458 (2002).","DOI":"10.1109\/SFCS.2002.1181969"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Mario Berta, Matthias Christandl, and Renato Renner, ``The quantum reverse Shannon theorem based on one-shot information theory'' Communications in Mathematical Physics 306, 579\u2013615 (2011).","DOI":"10.1007\/s00220-011-1309-7"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o, Aram W. Harrow, and Micha\u0142 Horodecki, ``Local Random Quantum Circuits are Approximate Polynomial-Designs'' Communications in Mathematical Physics 346, 397\u2013434 (2016).","DOI":"10.1007\/s00220-016-2706-8"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Eiichi Bannai, Gabriel Navarro, Noelia Rizo, and Pham Huu Tiep, ``Unitary $t$-groups'' Journal of the Mathematical Society of Japan 72, 909\u2013921 (2020).","DOI":"10.2969\/jmsj\/82228222"},{"key":"10","unstructured":"Matthias Christandl ``The structure of bipartite quantum states - Insights from group theory and cryptography'' thesis (2006)."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Fr\u00e9d\u00e9ric Dupuis, Mario Berta, J\u00fcrg Wullschleger, and Renato Renner, ``One-Shot Decoupling'' Communications in Mathematical Physics 328, 251\u2013284 (2014).","DOI":"10.1007\/s00220-014-1990-4"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine, ``Exact and approximate unitary 2-designs and their application to fidelity estimation'' Physical Review A 80, 012304 (2009).","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"13","unstructured":"William Fultonand Joe Harris ``Representation theory: a first course'' Springer (2013)."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Patrick Hayden, Micha\u0142 Horodecki, Andreas Winter, and Jon Yard, ``A Decoupling Approach to the Quantum Capacity'' Open Systems & Information Dynamics 15, 7\u201319 (2008).","DOI":"10.1142\/S1230161208000043"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Patrick Hayden, Debbie Leung, Peter W. Shor, and Andreas Winter, ``Randomizing Quantum States: Constructions and Applications'' Communications in Mathematical Physics 250, 371\u2013391 (2004).","DOI":"10.1007\/s00220-004-1087-6"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Micha\u0142 Horodecki, Jonathan Oppenheim, and Andreas Winter, ``Quantum state merging and negative information'' Communications in Mathematical Physics 269, 107\u2013136 (2007).","DOI":"10.1007%2Fs00220-006-0118-x"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Zhengfeng Ji, Yi-Kai Liu, and Fang Song, ``Pseudorandom Quantum States'' Advances in Cryptology \u2013 CRYPTO 2018 126\u2013152 (2018).","DOI":"10.1007\/978-3-319-96878-0_5"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Daniel Kane ``Small designs for path-connected spaces and path-connected homogeneous spaces'' Transactions of the American Mathematical Society 367, 6387\u20136414 (2015).","DOI":"10.1090\/tran\/6250"},{"key":"19","unstructured":"C\u00e9cilia Lancien and Andreas Winter ``Approximating quantum channels by completely positive maps with small Kraus rank'' Preprint (2017)."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Christian Majenz, Mario Berta, Fr\u00e9d\u00e9ric Dupuis, Renato Renner, and Matthias Christandl, ``Catalytic Decoupling of Quantum Information'' Physical Review Letters 118, 080503 (2017).","DOI":"10.1103\/PhysRevLett.118.080503"},{"key":"21","unstructured":"Christian Majenz, Christian Schaffner, and Jeroen Wier, ``Non-malleability for quantum public-key encryption'' Cryptology ePrint Archive, Report 2019\/496 (2019)."},{"key":"22","doi-asserted-by":"publisher","unstructured":"Oleg Szehr, Fr\u00e9d\u00e9ric Dupuis, Marco Tomamichel, and Renato Renner, ``Decoupling with unitary approximate two-designs'' New Journal of Physics 15, 053022 (2013).","DOI":"10.1088\/1367-2630\/15\/5\/053022"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Paul D. Seymourand Thomas Zaslavsky ``Averaging sets: A generalization of mean values and spherical designs'' Advances in Mathematics 52, 213\u2013240 (1984).","DOI":"10.1016\/0001-8708(84)90022-7"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Zak Webb ``The Clifford group forms a unitary 3-design'' Quantum Information and Computation 16, 1379\u20131400 (2016).","DOI":"10.26421\/QIC16.15-16"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Huangjun Zhu ``Multiqubit Clifford groups are unitary 3-designs'' Physical Review A 96, 062336 (2017).","DOI":"10.1103\/PhysRevA.96.062336"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-08-28-313\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T15:03:49Z","timestamp":1598627029000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-08-28-313\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,28]]},"references-count":26,"URL":"https:\/\/doi.org\/10.22331\/q-2020-08-28-313","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,28]]},"article-number":"313"}}