Weak approximate unitary designs and applications to quantum encryption
Cécilia Lancien, Christian Majenz
Abstract
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></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>ϵ</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>ϵ</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.