Quantum state testing beyond the polarizing regime and quantum
triangular discrimination
- URL: http://arxiv.org/abs/2303.01952v3
- Date: Thu, 28 Sep 2023 13:11:34 GMT
- Title: Quantum state testing beyond the polarizing regime and quantum
triangular discrimination
- Authors: Yupan Liu
- Abstract summary: We introduce proper quantum analogs for time-bounded distribution testing problems with respect to triangular discrimination and the Jensen-Shannon divergence.
These new $mathsfQSZK$-complete problems improve $mathsfQSZK$ containments for QSDP beyond the polarizing regime.
We establish a simple $mathsfQSZK$-hardness for the quantum entropy difference problem.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$)
captures computational difficulties of the time-bounded quantum state testing
problem with respect to the trace distance, known as the Quantum State
Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However,
QSDP is in $\mathsf{QSZK}$ merely within the constant polarizing regime,
similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due
to the polarization lemma (error reduction for SDP).
Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the
$\mathsf{SZK}$ containment for SDP beyond the polarizing regime via the
time-bounded distribution testing problems with respect to the triangular
discrimination and the Jensen-Shannon divergence. Our work 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
$\mathsf{QSZK}$-complete problems improve $\mathsf{QSZK}$ containments for QSDP
beyond the polarizing regime and establish a simple $\mathsf{QSZK}$-hardness
for the quantum entropy difference problem (QEDP) defined by Ben-Aroya,
Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some
exponentially small errors is in $\mathsf{PP}$, while the same problem without
error is in $\mathsf{NQP}$.
Related papers
- Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local
Hamiltonians [0.0]
We show that non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant.
We also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false.
arXiv Detail & Related papers (2024-03-07T19:00:06Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$.
In particular, we design global protocols for small set expansion, unique games, and PCP verification.
We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z) - Flying-cat parity checks for quantum error correction [0.0]
Long range, multi-qubit parity checks have applications in both quantum error correction and measurement-based entanglement generation.
We consider "flying-cat" parity checks based on an entangling operation that is quantum non-demolition (QND) for Schr"odinger's cat states $vertalpharanglepm vert-alpharangle$.
arXiv Detail & Related papers (2024-02-26T20:18:21Z) - $\mathcal{PT}$-symmetric mapping of three states and its implementation on a cloud quantum processor [0.9599644507730107]
We develop a new $mathcalPT$-symmetric approach for mapping three pure qubit states.
We show consistency with the Hermitian case, conservation of average projections on reference vectors, and Quantum Fisher Information.
Our work unlocks new doors for applying $mathcalPT$-symmetry in quantum communication, computing, and cryptography.
arXiv Detail & Related papers (2023-12-27T18:51:33Z) - Cubic* criticality emerging from a quantum loop model on triangular lattice [5.252398154171938]
We show that the triangular lattice quantum loop model (QLM) hosts a rich ground state phase diagram with nematic, vison plaquette (VP) crystals, and the $mathbb$ quantum spin liquid (QSL) close to the Rokhsar-Kivelson quantum critical point.
These solutions are of immediate relevance to both statistical and quantum field theories, as well as the rapidly growing experiments in Rydberg atom arrays and quantum moir'e materials.
arXiv Detail & Related papers (2023-09-11T18:00:05Z) - Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
We propose an arguably new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem.
We provide unified proof for some known lower bounds, including those for phase/amplitude estimation and Hamiltonian simulation.
arXiv Detail & Related papers (2023-08-03T14:41:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z) - Using Quantum Metrological Bounds in Quantum Error Correction: A Simple
Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates.
Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
arXiv Detail & Related papers (2020-04-24T17:58:10Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
Decision problem version of estimating Shannon entropy is the Entropy Difference (ED)
analogous problem with quantum circuits (QED)
We show that relative to an oracle, these problems cannot be as hard as their counterparts with exponentially larger circuits.
arXiv Detail & Related papers (2020-02-27T15:32:08Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.