We investigate the existence of secure bit commitment protocols in the convex framework for probabilistic theories. The theory makes only minimal assumptions, and can be used to formalize quantum theory, classical probability theory, and a host of other possibilities. We prove that in all such theories that are locally non-classical but do not have entanglement, there exists a bit commitment protocol that is exponentially secure in the number of systems used.

We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.

Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical secret key want to exchange a classical message with the guarantee that the message has not been modified or replaced by a dishonest party with control of the communication line. In this paper we study the authentication of messages composed of quantum states. We give a formal definition of authentication in the quantum setting. Assuming A and B have access to an insecure quantum channel and share a secret, classical random key, we provide a non-interactive scheme that enables A to both encrypt and authenticate an m qubit message by encoding it into m+s qubits, where the error probability decreases exponentially in the security parameter s. The scheme requires a secret key of size 2m+O(s). To achieve this, we give a highly efficient protocol for testing the purity of shared EPR pairs. It has long been known that learning information about a general quantum state will necessarily disturb it. We refine this result to show that such a disturbance can be done with few side effects, allowing it to circumvent cryptographic protections. Consequently, any scheme to authenticate quantum messages must also encrypt them. In contrast, no such constraint exists classically. This reasoning has two important consequences: It allows us to give a lower bound of 2m key bits for authenticating m qubits, which makes our protocol asymptotically optimal. Moreover, we use it to show that digitally signing quantum states is impossible.

For the discrete memoryless quantum channel, we show the equivalence of two different notions of quantum channel capacity: that which uses the entanglement fidelity as its criterion for success in transmission, and that which uses the minimum fidelity of pure states in a subspace of the input Hilbert space as its criterion. As a corollary, any source with entropy rate less than the capacity may be transmitted with high entanglement fidelity. We also show that a restricted class of encodings is sufficient to transmit any quantum source which may be transmitted on a given channel. This enables us to simplify a known upper bound for the channel capacity. It also enables us to show that the availability of an auxiliary classical channel from encoder to decoder does not increase the quantum capacity.

This paper documents the discovery of a new, better-than-classical quantum algorithm for the depth-two AND/OR tree problem. We describe the genetic programming system that was constructed specifically for this work, the quantum computer simulator that is used to evaluate the fitness of evolving quantum algorithms, and the newly discovered algorithm.