6 papers
The NPA hierarchy does not always attain the commuting operator value
Marco Fanizza, Larissa Kroell, Arthur Mehta +4
We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. Specifically, there is a computable mapping from T…
Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
Kiera Hutton, Arthur Mehta, Andrej Vukovic
We prove that deciding whether a classical-quantum (C-Q) channel can exactly preserve a single classical bit is QCMA-complete. This "bit-preservation" problem is a special case of…
A classical proof of quantum knowledge for multi-prover interactive proof systems
Anne Broadbent, Alex B. Grilo, Nagisa Hara +1
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs play an important…
Unclonable Functional Encryption
Arthur Mehta, Anne Müller
In a functional encryption (FE) scheme, a user that holds a ciphertext and a function key can learn the result of applying the function to the plaintext message. Security requires…
Positivity is undecidable in tensor products of free algebras
Arthur Mehta, William Slofstra, Yuming Zhao
It is well known that an element of the algebra of noncommutative *-polynomials is positive in all *-representations if and only if it is a sum of squares. This provides an effecti…
New Approaches to Complexity via Quantum Graphs
Eric Culf, Arthur Mehta
Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. Defining well-fo…