Chenyi Zhang

Prior work of Beverland et al. has shown that any exact Clifford+T implementation of the n-qubit Toffoli gate must use at least n T gates. Here we show how to get away with exponentially fewer T gates, at the cost of incurring a tiny 1/poly(n) error that can be neglected in most practical situations. More precisely, the n-qubit Toffoli gate can be implemented to within error ϵ in the diamond distance by a randomly chosen Clifford+T circuit with at most O(log(1/ϵ)) T gates. We also give a matching Ω(log(1/ϵ)) lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use Ω(n) T gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the T-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.

We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μ, where the samples come from different random variables with mean close to μ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.

Abstract We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function $f:\R^{n}\to\R$, our quantum algorithm outputs an $\epsilon$-approximate local minimum using $\tilde{O}(\log^{2} n/\epsilon^{1.75})$ queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al.~with $\tilde{O}(\log^{6} n/\epsilon^{1.75})$ queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of $n$ and matches its complexity in terms of $1/\epsilon$. Our quantum algorithm is built upon two techniques: First, we replace the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the polynomial speedup in $n$ for escaping from saddle points. Second, we show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries in nonconvex optimization by quantum evaluation queries with the same complexity, extending the same result from convex optimization due to van Apeldoorn et al. and Chakrabarti et al. Finally, we also perform numerical experiments that support our quantum speedup.

With the rapid development of quantum computing technology, the classical cryptosystem will face a significant threat. It is an urgent security issue to study the security impact of quantum computing on classical cryptosystems and provide reliable cryptographic primitives for the post-quantum era. A powerful way to solve this problem is to quantize the classical cryptanalysis tools and use the improved versions for cryptanalysis. In this paper, we propose a quantum zero correlation analysis algorithm based on the Bernstein-Vazirani and Grover algorithms. It can find zero correlation linear hulls for Feistel and SPN ciphers. We prove the correctness of the algorithm and analyze its complexity. Compared with the classical algorithms, the proposed quantum algorithm has significant advantages when the number of encryption rounds of block ciphers is large. Moreover, compared with the existing quantum zero correlation linear analysis, the proposed algorithm is more efficient and does not depend on the algebraic characteristics of the target cipher, which makes the algorithm has more flexible application scenarios.

In distributed systems, Byzantine consensus serves as a practical approach to addressing the Byzantine general problem. Previous research has exploited quantum resources to develop quantum-detectable Byzantine consensus protocols, aiming to surpass the 1/3 fault-tolerance bound. However, these consensus protocols are designed under the assumption of secure channel. They ignored malicious participants' attacks on the communication process. In this paper, we introduce a new quantum protocol for quantum Byzantine consensus utilizing the full quantum one-way function, which is the foundation for generating verification state in list distribution phase and secure message in agreement phase. By relying on the quantum circuit of the full quantum one-way function, the honest participants are able to reach consensus, while the malicious participants are effectively detected. In order to enhance the scalability of the proposed quantum Byzantine consensus protocol, we categorize the participants into three-member groups when the number of participants is n > 3. Meanwhile, the election of commander is introduced in agreement phase. In the proposed multi-party quantum Byzantine consensus protocol, the full quantum one-way function verifies the honesty of the participants both in list distribution phase and agreement phase. Security analysis demonstrates that the proposed multiparty quantum Byzantine consensus protocol is secure against quantum attacks and the dishonest behaviors of participants.