Papers

2024

1. Space-bounded quantum interactive proof systems

   François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang

   Abstract arXiv ECCC

   We introduce two models of space-bounded quantum interactive proof systems, 𝖰𝖨𝖯𝖫 and 𝖰𝖨𝖯_𝖴𝖫. The 𝖰𝖨𝖯_𝖴𝖫 model, a space-bounded variant of quantum interactive proofs 𝖰𝖨𝖯 introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, 𝖰𝖨𝖯𝖫 allows logarithmically many intermediate measurements per verifier action (with a high-concentration condition on yes instances), making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995).
   
   We characterize the computational power of 𝖰𝖨𝖯𝖫 and 𝖰𝖨𝖯_𝖴𝖫. When the message number \(m\) is polynomially bounded, 𝖰𝖨𝖯_𝖴𝖫⊊𝖰𝖨𝖯𝖫 unless 𝖯=𝖭𝖯:
   - 𝖰𝖨𝖯𝖫 exactly characterizes 𝖭𝖯.
   - 𝖰𝖨𝖯_𝖴𝖫 is contained in 𝖯 and contains 𝖲𝖠𝖢^𝟣∪𝖡𝖰𝖫, where 𝖲𝖠𝖢^𝟣 denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits.
   However, this distinction vanishes when \(m\) is constant. Our results further indicate that intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where 𝖡𝖰𝖫=𝖡𝖰_𝖴𝖫.
   
   We also introduce space-bounded unitary quantum statistical zero-knowledge (𝖰𝖲𝖹𝖪_𝖴𝖫), a specific form of 𝖰𝖨𝖯_𝖴𝖫 proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (𝖰𝖲𝖹𝖪) defined by Watrous (SICOMP 2009). We prove that 𝖰𝖲𝖹𝖪_𝖴𝖫=𝖡𝖰𝖫, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.

2. On estimating the trace of quantum state powers

   Yupan Liu, and Qisheng Wang

   To appear in SODA 2025

   Abstract arXiv ECCC

   We investigate the computational complexity of estimating the trace of quantum state powers \(\mathrm{Tr}(\rho^q)\) for an \(n\)-qubit mixed quantum state \(\rho\), given its state-preparation circuit of size \(\mathrm{poly}(n)\). This quantity is closely related to and often interchangeable with the Tsallis entropy \(\mathrm{S}_q(\rho) = \frac{1 - \mathrm{Tr}(\rho^q)}{q-1}\), where \(q = 1\) corresponds to the von Neumann entropy. For any non-integer \(q \geq 1 + \Omega(1)\), we provide a quantum estimator for \(\mathrm{S}_q(\rho)\) with time complexity \(\mathrm{poly}(n)\), exponentially improving the prior best results of \(\exp(n)\) due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.
   
   Our quantum algorithm reveals a sharp phase transition between the case of \(q=1\) and constant \(q>1\) in the computational complexity of the 𝚀𝚞𝚊𝚗𝚝𝚞𝚖 \(q\)-𝚃𝚜𝚊𝚕𝚕𝚒𝚜 𝙴𝚗𝚝𝚛𝚘𝚙𝚢 𝙳𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚌𝚎 𝙿𝚛𝚘𝚋𝚕𝚎𝚖 (𝚃𝚜𝚊𝚕𝚕𝚒𝚜𝚀𝙴𝙳\(_q\)), particularly deciding whether the difference \(\mathrm{S}_q(\rho_0) - \mathrm{S}_q(\rho_1)\) is at least \(0.001\) or at most \(-0.001\):
   - For any \(1+\Omega(1) \leq q \leq 2\), 𝚃𝚜𝚊𝚕𝚕𝚒𝚜𝚀𝙴𝙳\(_q\) is 𝖡𝖰𝖯-complete, which implies that 𝙿𝚞𝚛𝚒𝚝𝚢 𝙴𝚜𝚝𝚒𝚖𝚊𝚝𝚒𝚘𝚗 is also 𝖡𝖰𝖯-complete.
   - For any \(1 \leq q \leq 1 + \frac{1}{n-1}\), 𝚃𝚜𝚊𝚕𝚕𝚒𝚜𝚀𝙴𝙳\(_q\) is 𝖰𝖲𝖹𝖪-hard, leading to hardness of approximating von Neumann entropy because \({\rm S}_q(\rho) \leq {\rm S}(\rho)\), as long as 𝖡𝖰𝖯⊊𝖰𝖲𝖹𝖪.
   
   The hardness results are derived from reductions based on new inequalities for the quantum \(q\)-Jensen-(Shannon-)Tsallis divergence with \(1\leq q \leq 2\), which are of independent interest.

2023

1. Space-bounded quantum state testing via space-efficient quantum singular value transformation

   François Le Gall, Yupan Liu, and Qisheng Wang

   Abstract arXiv ECCC

   Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary 𝖼𝗈𝖱𝖰𝖫) and two-sided error (𝖡𝖰𝖫), approached from a quantum state testing perspective:
   - The first family of natural complete problems for unitary 𝖼𝗈𝖱𝖰𝖫, i.e., space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance;
   - A new family of natural complete problems for 𝖡𝖰𝖫, i.e., space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and quantum entropy difference.
   
   In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as \(Q_0\) and \(Q_1\), which prepare quantum states \(\rho_0\) and \(\rho_1\), respectively, with access to their ``source code''. Our goal is to decide whether \(\rho_0\) is \(\epsilon_1\)-close to or \(\epsilon_2\)-far from \(\rho_1\) with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, our results reveal that the space-bounded state testing problems all correspond to the same class. Moreover, our algorithms on the trace distance inspire an algorithmic Holevo-Helstrom measurement, implying 𝖰𝖲𝖹𝖪 is in 𝖰𝖨𝖯(𝟤) with a quantum linear-space honest prover. Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gilyén, Su, Low, and Wiebe (STOC 2019), which is of independent interest. Our technique provides a unified approach for designing space-bounded quantum algorithms. Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for special forms of the projected unitary encoding.

2. Quantum state testing beyond the polarizing regime and quantum triangular discrimination

   Yupan Liu

   Abstract arXiv

   The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪) captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, known as the Quantum State Distinguishability Problem (𝚀𝚂𝙳𝙿) introduced by Watrous (FOCS 2002). However, 𝚀𝚂𝙳𝙿 is in 𝖰𝖲𝖹𝖪 merely within the polarizing regime, similar to its classical counterpart shown by Sahai and Vadhan (JACM, 2003) due to the polarization lemma (error reduction for 𝚂𝙳𝙿). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the 𝖲𝖹𝖪 containment for 𝚂𝙳𝙿 beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. This paper introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new 𝖰𝖲𝖹𝖪-complete problems improve 𝖰𝖲𝖹𝖪 containments for 𝚀𝚂𝙳𝙿 beyond the polarizing regime and establish a simple 𝖰𝖲𝖹𝖪-hardness for the quantum entropy difference problem (𝚀𝙴𝙳𝙿) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that 𝚀𝚂𝙳𝙿 with some exponentially small errors is in 𝖯𝖯, while the same problem without error is in 𝖭𝖰𝖯.

3. Quantum Merlin-Arthur proof systems for synthesizing quantum states

   Hugo Delavenne, François Le Gall, Yupan Liu, and Masayuki Miyamoto

   To appear in Quantum

   Abstract arXiv

   Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class 𝖭𝖯, referred to as 𝗌𝗍𝖺𝗍𝖾𝖰𝖬𝖠, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class 𝗌𝗍𝖺𝗍𝖾𝖰𝖨𝖯 recently introduced by Rosenthal and Yuen (ITCS 2022), which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or a bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits (𝗌𝗍𝖺𝗍𝖾𝖡𝖰𝖯) and space-uniform polynomial-space quantum circuits (𝗌𝗍𝖺𝗍𝖾𝖯𝖲𝖯𝖠𝖢𝖤). Furthermore, we establish that the family of 𝖴𝖰𝖬𝖠 witnesses, considered as one of the most natural candidates, is in 𝗌𝗍𝖺𝗍𝖾𝖰𝖬𝖠. Additionally, we demonstrate that 𝗌𝗍𝖺𝗍𝖾𝖰𝖢𝖬𝖠 achieves perfect completeness.

2020

1. \({\sf StoqMA}\) meets distribution testing

   Yupan Liu

   In TQC 2021

   Abstract DOI arXiv Video Slides

   Cubitt and Montanaro (SICOMP, 2016) formulated a quantum version of Schaefer's dichotomy theorem for the local Hamiltonian problem. This quartation theorem categorizes the problem into one of four levels: 𝖯, 𝖭𝖯-complete, 𝖲𝗍𝗈𝗊𝖬𝖠-complete, or QMA-complete. The hierarchy is notable for its inclusion of a mystery class 𝖲𝗍𝗈𝗊𝖬𝖠, introduced by Bravyi, Bessen, and Terhal (2006). In this paper, we establish a link between 𝖲𝗍𝗈𝗊𝖬𝖠 and distribution testing through reversible circuits. Our first result demonstrates that the advantage of 𝖲𝗍𝗈𝗊𝖬𝖠 is due to the optimal non-negative witness. If the optimal witness is restricted to be easy witness, meaning that any quotient on the distribution's coordinates associated with the witness is efficiently computable, then the class eStoqMA is contained in MA. Remarkably, e𝖲𝗍𝗈𝗊𝖬𝖠 includes 𝖲𝗍𝗈𝗊𝖬𝖠 with perfect completeness (𝖲𝗍𝗈𝗊𝖬𝖠\(_1\)), providing an arguably simplified proof for 𝖲𝗍𝗈𝗊𝖬𝖠\(_1\)⊆𝖬𝖠 as shown in Bravyi, Bessen, and Terhal (2006), as well as Bravyi and Terhal (SICOMP, 2010). Our second result is error reduction for 𝖲𝗍𝗈𝗊𝖬𝖠 regarding soundness error, by proving that distinguishing reversible circuits with ancillary random bits is 𝖲𝗍𝗈𝗊𝖬𝖠-complete, whereas distinguishing quantum circuits is 𝖰𝖬𝖠-complete. Our results make progress towards collapsing the hierarchy 𝖬𝖠⊆𝖲𝗍𝗈𝗊𝖬𝖠⊆𝖲𝖡𝖯 in which all classes are contained in 𝖠𝖬 and collapse to 𝖭𝖯 under derandomization assumptions.

2. \(\mathsf{StoqMA}\) vs. \(\mathsf{MA}\): the power of error reduction

   Dorit Aharonov, Alex B. Grilo, and Yupan Liu

   To appear in Quantum

   Abstract arXiv

   𝖲𝗍𝗈𝗊𝖬𝖠 characterizes the computational hardness of stoquastic local Hamiltonians, which is a family of Hamiltonians that does not suffer from the sign problem. Although error reduction is commonplace for many complexity classes, such as 𝖡𝖯𝖯, 𝖡𝖰𝖯, 𝖬𝖠, 𝖰𝖬𝖠, etc., this property remains open for 𝖲𝗍𝗈𝗊𝖬𝖠 since Bravyi, Bessen and Terhal defined this class in 2006. In this note, we show that error reduction for 𝖲𝗍𝗈𝗊𝖬𝖠 will imply that 𝖲𝗍𝗈𝗊𝖬𝖠=𝖬𝖠.

2019

1. Towards a quantum-inspired proof for \({\sf IP} = {\sf PSPACE}\)

   Ayal Green, Guy Kindler, and Yupan Liu

   Quantum Information & Computation

   Abstract DOI arXiv

   We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by [AG17] showing a quantum-inspired interactive protocol (𝖨𝖯) for 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖡𝖰𝖯 where the prover is only assumed to be a 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖡𝖰𝖯 machine, and show that the result can be strengthened to show an 𝖨𝖯 for 𝖭𝖯\(^{\sf P}\)\(^{\sf P}\) with a prover which is only assumed to be an 𝖭𝖯\(^{\sf P}\)\(^{\sf P}\) machine - which was not known before. We also show how the protocol can be used to directly verify 𝖰𝖬𝖠 computations, thus connecting the sum-check protocol by [AAV13] with the result of [AG17, LFKN90]. Our results shed light on a quantum-inspired proof for 𝖨𝖯=𝖯𝖲𝖯𝖠𝖢𝖤, as 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖰𝖬𝖠 captures the full 𝖯𝖲𝖯𝖠𝖢𝖤 power.