Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state |ψ_1⟩ ⊗ … ⊗ |ψ_n⟩ where each qubit is in one of two orthogonal states |ψ⟩ or |ψ^⟂⟩, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of 1/2 + Θ(1/√n). Under the promise that at least 2/3 of the input qubits are in the majority state, the fidelity increases to 1 - Θ(1/n) and approaches 1 as n increases.We also consider the more general problem of computing any symmetric and equivariant Boolean function f: {0,1}ⁿ → {0,1} in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size O(n). The time complexity of the algorithm is O(n⁴ log n) where n is the number of input qubits.

We exhibit infinitely many new, constrained inequalities for the von Neumann entropy, and show that they are independent of each other and the known inequalities obeyed by the von Neumann entropy (basically strong subadditivity). The new inequalities were proved originally by Makarychevfor the Shannon entropy, using properties of probability distributions. Our approach extends the proof of the inequalities to the quantum domain, and includes their independence for the quantum and also the classical cases.

We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows

The relative entropy of two distributions of n random variables, and more generally of two n-party quantum states, is an important quantity exhibiting, for example, the extent to which the two distributions/states are different. The relative entropy of the states formed by restricting to a smaller number m of parties is always less than or equal to the relative entropy of the two original n-party states. This is the monotonicity of relative entropy. Using techniques from convex geometry, we prove that monotonicity under restrictions is the only general inequality satisfied by relative entropies. In doing so we make a connection to secret sharing schemes with general access structures: indeed, it turns out that the extremal rays of the cone defined by monotonicity are populated by classical secret sharing schemes. A surprising outcome is that the structure of allowed relative entropy values of subsets of multiparty states is much simpler than the structure of allowed entropy values. And the structure of allowed relative entropy values (unlike that of entropies) is the same for classical probability distributions and quantum states