Among initialization schemes for ensemble quantum computation beginning at thermal equilibrium, the scheme proposed by Schulman and Vazirani [in Proceedings of the 31st ACM Symposium on Theory of Computing (STOC'99) (ACM Press, New York, 1999), pp. 322--329] is known for the simple quantum circuit to redistribute the biases (polarizations) of qubits and small time complexity. However, our numerical simulation shows that the number of qubits initialized by the scheme is rather smaller than expected from the von Neumann entropy because of an increase in the sum of the binary entropies of individual qubits, which indicates a growth in the total classical correlation. This result---namely, that there is such a significant growth in the total binary entropy---disagrees with that of their analysis.
Among initialization schemes for ensemble quantum computation beginning at thermal equilibrium, the scheme proposed by Schulman and Vazirani [in Proceedings of the 31st ACM Symposium on Theory of Computing (STOC'99) (ACM Press, New York, 1999), pp. 322--329] is known for the simple quantum circuit to redistribute the biases (polarizations) of qubits and small time complexity. However, our numerical simulation shows that the number of qubits initialized by the scheme is rather smaller than expected from the von Neumann entropy because of an increase in the sum of the binary entropies of individual qubits, which indicates a growth in the total classical correlation. This result---namely, that there is such a significant growth in the total binary entropy---disagrees with that of their analysis.
Global unitary transformations (OPTSWAPS) that optimally increase the bias of any mixed computation qubit in a quantum system -- represented by a diagonal density matrix -- towards a particular state of the computational basis which, in effect, increases its purity are presented. Quantum circuits that achieve this by implementing the above data compression technique -- a generalization of the 3B-Comp used before -- are described. These circuits enable purity increment in the computation qubit by maximally transferring part of its von Neumann or Shannon entropy to any number of surrounding qubits and are valid for the complete range of initial biases. Using the optswaps, a practicable new method that algorithmically achieves hierarchy-dependent cooling of qubits to their respective limits in an engineered quantum register opened to the heat-bath is delineated. In addition to multi-qubit purification and satisfying two of DiVincenzo's criteria for quantum computation in some architectures, the implications of this work for quantum data compression and quantum thermodynamics are discussed.
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any m-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by Ω(m1). For more than two decades the best known coin-flipping protocols against dishonest majority had bias Θ(mℓ), where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(m1). In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than 32 of the parties can be corrupted. Still, for the case of 32 (or more) corrupted parties, the best known protocol had bias Θ(mℓ). In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an m-round, three-party coin-flipping protocol, with bias mO(log3m). Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned Θ(mℓ)-bias protocol.
The scaling of NMR ensemble computers is currently one of the main obstacles to building larger-scale quantum computing devices. To achieve scalability, one needs a large number of highly polarized spins in liquid nuclear-spin systems at finite temperature. In quantum computing terminology, such spin-half states are (almost) pure qubit states. Producing highly polarized spins (almost pure qubit states) out of non-polarized spins (non-pure qubit states) is sometimes called "purification". From a thermodynamic point of view, purification can be viewed as cooling spins to a very low temperature. In this preliminary work, we study the optimality of purification as a tradeoff between the number of cooled spins and the closeness of their quantum state to the ideal pure state.
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and it will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting [L. J. Schulman, Communication on noisy channels: A coding theorem for computation, in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 1992, pp. 724--733], [L. J. Schulman, Deterministic coding for interactive communication, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM, 1993, pp. 747--756]. We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Under adversarial noise, our strategy can withstand, for arbitrarily small ε>0, error rates as high as 1/2−ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no preshared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no preshared entanglement over some quantum channels with quantum capacity CQ=0, proving that CQ is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and these results hold in particular in the quantum communication complexity settings of the Yao and Cleve--Buhrman models.
Abstract The problem of learning Boolean linear functions from quantum examples w.r.t. the uniform distribution can be solved on a quantum computer using the Bernstein–Vazirani algorithm (Bernstein and Vazirani, in: Kosaraju (ed) Proceedings of the twenty-fifth annual ACM symposium on theory of computing, ACM, New York, 1993. 10.1145/167088.167097 ). A similar strategy can be applied in the case of noisy quantum training data, as was observed in Grilo et al. (Learning with errors is easy with quantum samples, 2017). However, extensions of these learning algorithms beyond the uniform distribution have not yet been studied. We employ the biased quantum Fourier transform introduced in Kanade et al. (Learning dnfs under product distributions via μ μ -biased quantum Fourier sampling, 2018) to develop efficient quantum algorithms for learning Boolean linear functions on n bits from quantum examples w.r.t. a biased product distribution. Our first procedure is applicable to any (except full) bias and requires O(ln(n)) O(ln(n)) quantum examples. The number of quantum examples used by our second algorithm is independent of n, but the strategy is applicable only for small bias. Moreover, we show that the second procedure is stable w.r.t. noisy training data and w.r.t. faulty quantum gates. This also enables us to solve a version of the learning problem in which the underlying distribution is not known in advance. Finally, we prove lower bounds on the classical and quantum sample complexities of the learning problem. Whereas classically, Ω(n) Ω(n) examples are necessary independently of the bias, we are able to establish a quantum sample complexity lower bound of Ω(ln(n)) Ω(ln(n)) only under an assumption of large bias. Nevertheless, this allows for a discussion of the performance of our suggested learning algorithms w.r.t. sample complexity. With our analysis, we contribute to a more quantitative understanding of the power and limitations of quantum training data for learning classical functions.