Author name cluster

Jiaqing Jiang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

STOC Conference 2025 Conference Paper

Positive Bias Makes Tensor-Network Contraction Tractable

Jiaqing Jiang
Jielun Chen
Norbert Schuch
Dominik Hangleiter

Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d ≳ n , a small positive mean value ≳ 1/ d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/ poly ( n ) multiplicative approximation. At the same time exactly contracting such tensor networks remains #P-hard, like for the zero-mean case. The mean value 1/ d matches the phase transition point observed in previous work. Our proof makes use of Barvinok’s method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least StoqMA-hard. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is BPP-complete. This result compares to Arad and Landau’s result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is BQP-complete. Our work thus identifies new parameter regimes in terms of the positivity of the tensor entries in which tensor networks can be (nearly) efficiently contracted.

Details

SODA Conference 2020 Conference Paper

Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis

Jiaqing Jiang
Xiaoming Sun 0001
Shang-Hua Teng
Bujiao Wu
Kewen Wu 0001
Jialin Zhang 0001

Due to the decoherence of the state-of-the-art physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore and Nilsson [1] demonstrated that additional qubits (or ancillae ) could be used to design “shallow” parallel circuits for quantum operators. They proved that any n -qubit CNOT circuit could be parallelized to O (log n ) depth, with O ( n 2 ) ancillae. However, the near-term quantum technologies can only support limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any m ≥ 0, any n -qubit CNOT circuit can be parallelized to depth, with m ancillae. We show that this bound is tight by a counting argument, and further show that even with arbitrary two-qubit quantum gates to approximate CNOT circuits, the depth lower bound still meets our construction, illustrating the robustness of our result. Our work improves upon two previous results, one by Moore and Nilsson [1] for O (log n )-depth quantum synthesis, and one by Patel, Markov, and Hayes [2] for m =0: for the former, we reduce the need for ancillae by a factor of log 2 n by showing that m = O ( n 2 / log 2 n ) additional qubits — which is asymptotically optimal — suffice to build O (log n )-depth, O ( n 2 / log n )-size CNOT circuits; for the later, we reduce the depth by a factor of n to the asymptotically optimal bound. Our results can be directly extended to stabilizer circuits using an earlier result by Aaronson and Gottesman [3]. In addition, we provide relevant hardness evidence for synthesis optimization of CNOT circuits in term of both size and depth.

Details

AAAI Conference 2020 Conference Paper

Revisiting Online Quantum State Learning

Feidiao Yang
Jiaqing Jiang
Jialin Zhang
Xiaoming Sun

In this paper, we study the online quantum state learning problem which is recently proposed by Aaronson et al. (2018). In this problem, the learning algorithm sequentially predicts quantum states based on observed measurements and losses and the goal is to minimize the regret. In the previous work, the existing algorithms may output mixed quantum states. However, in many scenarios, the prediction of a pure quantum state is required. In this paper, we ﬁrst propose a Follow-the-Perturbed-Leader (FTPL) algorithm that can guarantee to predict pure quantum states. Theoretical analysis shows that our algorithm can achieve an O( √ T) expected regret under some reasonable settings. In the case that the pure state prediction is not mandatory, we propose another deterministic learning algorithm which is simpler and more efﬁcient. The algorithm is based on the online gradient descent (OGD) method and can also achieve an O( √ T) regret bound. The main technical contribution of this result is an algorithm of projecting an arbitrary Hermitian matrix onto the set of density matrices with respect to the Frobenius norm. We think this subroutine is of independent interest and can be widely used in many other problems in the quantum computing area. In addition to the theoretical analysis, we evaluate the algorithms with a series of simulation experiments. The experimental results show that our FTPL method and OGD method outperform the existing RFTL approach proposed by Aaronson et al. (2018) in almost all settings. In the implementation of the RFTL approach, we give a closed-form solution to the algorithm. This provides an efﬁcient, accurate, and completely executable solution to the RFTL method.

PDF Details