Qisheng Wang

Dr. Qisheng Wang

School of Informatics, University of Edinburgh, Edinburgh, City of Edinburgh, UK
orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
5 September 2022 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Qisheng WangQisheng Wang
Qisheng Wang
ZZZhicheng Zhang
Zhicheng Zhang
Kean ChenKean Chen
Kean Chen
JGJi Guan
Ji Guan
WFWang Fang
Wang Fang
MYMingsheng Ying
Mingsheng Ying
For two unknown mixed quantum states $\rho $ and $\sigma $ in an $N$ -dimensional Hilbert space, computing their fidelity $F(\rho,\sigma)$ is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in ${\mathrm{ poly}}(\log (N), r, 1/\varepsilon)$ time, where $r$ is the lower rank of $\rho $ and $\sigma $ , and $\varepsilon $ is the desired precision, provided that the purifications of $\rho $ and $\sigma $ are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in $N$ .

13 May 2024 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
Qisheng WangQisheng Wang
Qisheng Wang
JGJi Guan
Ji Guan
JLJunyi Liu
Junyi Liu
ZZZhicheng Zhang
Zhicheng Zhang
MYMingsheng Ying
Mingsheng Ying
We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, for N -dimensional quantum states of rank r , our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error ε have time complexity of Õ( r /ε 2 ), Õ( r 5 /ε 6 ) and Õ( r 6.5 /ε 7.5 ), respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity Ω( N ), and the prior best one for fidelity has time complexity Õ( r 12.5 /ε 13.5 ). The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.

2 October 2023 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Qisheng WangQisheng Wang
Qisheng Wang
ZZZhicheng Zhang
Zhicheng Zhang
In quantum information, trace distance is a basic metric of distinguishability between quantum states. However, there is no known efficient approach to estimate the value of trace distance in general. In this paper, we propose efficient quantum algorithms for estimating the trace distance within additive error $\varepsilon $ between mixed quantum states of rank $r$ . Specifically, we first provide a quantum algorithm using $r \cdot \widetilde O \left ({1/\varepsilon ^{2}}\right)$ queries to the quantum circuits that prepare the purifications of quantum states. Then, we modify this quantum algorithm to obtain another algorithm using $\widetilde O \left ({r^{2}/\varepsilon ^{5}}\right)$ samples of quantum states, which can be applied to quantum state certification. These algorithms have query/sample complexities that are independent of the dimension $N$ of quantum states, and their time complexities only incur an extra $O \left ({\log \left ({N}\right)}\right)$ factor. In addition, we show that the decision version of low-rank trace distance estimation is $\mathsf {BQP}$ -complete.

15 January 2024 in Quantum
Verified
Journal Article
Open access
PDF file
ZZZhicheng Zhang
Zhicheng Zhang
Qisheng WangQisheng Wang
Qisheng Wang
MYMingsheng Ying
Mingsheng Ying
We study how parallelism can speed up quantum simulation. A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians with good sparse structures, called uniform-structured Hamiltonians, including various Hamiltonians of practical interest like local Hamiltonians and Pauli sums. Given the oracle access to the target sparse Hamiltonian, in both query and gate complexity, the running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence polylog ⁡ log ⁡ ( 1 / ϵ ) on the simulation precision ϵ . This presents an exponential improvement over the dependence polylog ⁡ ( 1 / ϵ ) of previous optimal sparse Hamiltonian simulation algorithm without parallelism. To obtain this result, we introduce a novel notion of parallel quantum walk, based on Childs' quantum walk. The target evolution unitary is approximated by a truncated Taylor series, which is obtained by combining these quantum walks in a parallel way. A lower bound Ω ( log ⁡ log ⁡ ( 1 / ϵ ) ) is established, showing that the ϵ -dependence of the gate depth achieved in this work cannot be significantly improved.Our algorithm is applied to simulating three physical models: the Heisenberg model, the Sachdev-Ye-Kitaev model and a quantum chemistry model in second quantization. By explicitly calculating the gate complexity for implementing the oracles, we show that on all these models, the total gate depth of our algorithm has a polylog ⁡ log ⁡ ( 1 / ϵ ) dependence in the parallel setting.

31 March 2023 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Kean ChenKean Chen
Kean Chen
Qisheng WangQisheng Wang
Qisheng Wang
PLPeixun Long
Peixun Long
MYMingsheng Ying
Mingsheng Ying
Estimating the unitarity of an unknown quantum channel E provides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that use O (ϵ –2 ) and O ( √ d ∙ϵ –2 ) calls to E with coherent and incoherent accesses, respectively, where d is the dimension of the system that E acts on and ϵ is the required precision. We further show that both the d -dependence and ϵ-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound Ω( √ d ), improving the prior best lower bound Ω( ∛ d ) by Aharonov et al. (Nat. Commun. 2022) and Chen et al. (FOCS 2021).

4 October 2021 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Verified
Journal Article
Closed access
Qisheng WangQisheng Wang
Qisheng Wang
RLRiling Li
Riling Li
MYMingsheng Ying
Mingsheng Ying
We define a formal framework for equivalence checking of sequential quantum circuits. The model we adopt is a quantum state machine, which is a natural quantum generalization of Mealy machines. A major difficulty in checking quantum circuits (but not present in checking classical circuits) is that the state spaces of quantum circuits are continuums. This difficulty is resolved by our main theorem showing that equivalence checking of two quantum Mealy machines can be done with input sequences that are taken from some chosen basis (which are finite) and have a length quadratic in the dimensions of the state Hilbert spaces of the machines. Based on this theoretical result, we develop an (and to the best of our knowledge, the first) algorithm for checking equivalence of sequential quantum circuits with running time $\mathcal {O}(2^{3m+5l}(2^{3m}{\,+\,}2^{3l}))$ , where $m$ and $l$ denote the numbers of input and internal qubits, respectively. The complexity of our algorithm is comparable with that of the known algorithms for checking classical sequential circuits in the sense that both are exponential in the number of (qu)bits. Several case studies and experiments are presented.