2011

Testing quantum circuits and detecting insecure encryption

Rosgen, Bill

Understand

We show that computational problem of testing the behaviour of quantum circuits is hard for the class of problems known as QMA that can be verified efficiently with a quantum computer.

This result is a generalization of the techniques previously used to prove the hardness of other problem on quantum circuits.
We use this result to show the QMA-hardness of a weak version of the problem of detecting the insecurity of a symmetric-key quantum encryption system, or alternately the problem of determining when a quantum channel is not private.
We also give a QMA protocol for the problem of detecting insecure encryption to show that it is QMA-complete.

Built on

Detection theory and quantum mechanics
C. W. Helstrom · 1967
Earlier work this paper cites.
A continuity property of the entropy density for spin lattice systems
M. Fannes · 1973
Earlier work this paper cites.
Quantum circuits with mixed states
D. Aharonov, A. Kitaev, and N. Nisan · 1998
Earlier work this paper cites.
Forgetting qubits is hot to do
S. Braunstein, H.-K. Lo, and T. Spiller · 1999
Earlier work this paper cites.
Coding theorem and strong converse for quantum channels
Original
A. Winter · 1999
Earlier work this paper cites.
Private quantum channels
A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf · 2000
Earlier work this paper cites.
Quantum fingerprinting
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf · 2001
Earlier work this paper cites.
Authentication of quantum messages
H. Barnum, C. Crépeau, D. Gottesman, A. Smith, and A. Tapp · 2002
Earlier work this paper cites.

Similar

Direct estimations of linear and nonlinear functionals of a quantum state
A. K. Ekert, C. M. Alves, D. K. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek · 2002
Cited alongside, same era.
Classical and Quantum Computation , volume 47 of Graduate Studies in Mathematics
A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi · 2002
Cited alongside, same era.
Optimal encryption of quantum bits
P. O. Boykin and V. Roychowdhury · 2003
Cited alongside, same era.
Small pseudo-random families of matrices: Derandomizing approximate quantum encryption
A. Ambainis and A. Smith · 2004
Cited alongside, same era.
Randomizing quantum states: constructions and applications
P. Hayden, D. Leung, P. W. Shor, and A. Winter · 2004
Cited alongside, same era.
“Non-identity-check” is QMA-complete
D. Janzing, P. Wocjan, and T. Beth · 2005
Cited alongside, same era.
Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
Cited alongside, same era.

Then

On the hardness of distinguishing mixed-state quantum computations
B. Rosgen and J. Watrous · 2005
Later among the works it cites.
The complexity of the local Hamiltonian problem
J. Kempe, A. Kitaev, and O. Regev · 2006
Later among the works it cites.
Consistency of local density matrices is QMA-complete
Y.-K. Liu · 2006
Later among the works it cites.
On the complexity of computing zero-error and Holevo capacity of quantum channels, 2007
Original
S. Beigi and P. W. Shor · 2007
Later among the works it cites.
Computational difficulty of finding matrix product ground states
Original
N. Schuch, I. Cirac, and F. Verstraete · 2008
Later among the works it cites.
Computational complexity of interacting electrons and fundamental limitations of density functional theory
Original
N. Schuch and F. Verstraete · 2009
Later among the works it cites.
Testing non-isometry is QMA-complete
Original
B. Rosgen · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…