Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
Conjugate queries can help
9 Pith papers cite this work. Polarity classification is still indexing.
9
Pith papers citing it
abstract
We give a natural problem over input quantum oracles $U$ which cannot be solved with exponentially many black-box queries to $U$ and $U^\dagger$, but which can be solved with constant many queries to $U$ and $U^*$, or $U$ and $U^{\mathrm{T}}$. We also demonstrate a quantum commitment scheme that is secure against adversaries that query only $U$ and $U^\dagger$, but is insecure if the adversary can query $U^*$. These results show that conjugate and transpose queries do give more power to quantum algorithms, lending credence to the idea put forth by Zhandry that cryptographic primitives should prove security against these forms of queries. Our key lemma is that any circuit using $q$ forward and inverse queries to a state preparation unitary for a state $\sigma$ can be simulated to $\varepsilon$ error with $n = \mathcal{O}(q^2/\varepsilon)$ copies of $\sigma$. Consequently, for decision tasks, algorithms using (forward and inverse) state preparation queries only ever perform quadratically better than sample access. We also identify a motif, which we call the "acorn trick", where generically strengthening a quantum resource can be possible if the output is allowed to be random, bypassing no-go theorems for deterministic algorithms. We demonstrate this idea for several settings, including controlization and purification.
citation-role summary
background 2
method 1
citation-polarity summary
fields
quant-ph 9verdicts
UNVERDICTED 9representative citing papers
Optimal algorithms achieve query complexities Θ(d/ε²) for incoherent access, Θ(d/ε) for coherent access, and Θ(√d/ε) for source-code access in quantum channel certification to unitary, exactly matching prior lower bounds.
Introduces the random Stinespring superchannel to convert channel queries into isometry queries, yielding a channel analogue of Uhlmann's theorem and proving optimal channel learning query complexity of Θ(d_A d_B r).
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
Quantum channel tomography query complexity transitions from Heisenberg scaling Θ(r d1 d2 / ε) at dilation rate τ=1 to classical scaling Θ(r d1 d2 / ε²) for τ ≥ 1+Ω(1).
A machine that purifies two quantum inputs of different rank with positive probability cannot be a linear positive map, ruling out universal probabilistic purification from finite copies; approximate strategies exhibit a dimension-dependent trade-off between pure-output and append-environment maps.
Presents a poly-complexity quantum circuit implementing the random dilation superchannel for parallel channel queries, with approximate sequential extension, a no-go theorem for exact sequential dilation, and an application to exponentially improved channel storage-retrieval.
New purification-based reformulations of QCRB and HCRB connect mixed-state metrology bounds to those of purified states, enabling asymptotic attainment of HCRB or 2×QCRB via random channels and individual measurements.
A concise review of sample complexities and methods for tomography and learning in continuous-variable quantum systems, with emphasis on Gaussian versus non-Gaussian states.
citing papers explorer
-
An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
-
Strict Hierarchy for Quantum Channel Certification to Unitary
Optimal algorithms achieve query complexities Θ(d/ε²) for incoherent access, Θ(d/ε) for coherent access, and Θ(√d/ε) for source-code access in quantum channel certification to unitary, exactly matching prior lower bounds.
-
Random Stinespring superchannel: converting channel queries into dilation isometry queries
Introduces the random Stinespring superchannel to convert channel queries into isometry queries, yielding a channel analogue of Uhlmann's theorem and proving optimal channel learning query complexity of Θ(d_A d_B r).
-
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
-
Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition
Quantum channel tomography query complexity transitions from Heisenberg scaling Θ(r d1 d2 / ε) at dilation rate τ=1 to classical scaling Θ(r d1 d2 / ε²) for τ ≥ 1+Ω(1).
-
Probabilistic and approximate universal quantum purification machines
A machine that purifies two quantum inputs of different rank with positive probability cannot be a linear positive map, ruling out universal probabilistic purification from finite copies; approximate strategies exhibit a dimension-dependent trade-off between pure-output and append-environment maps.
-
Random dilation superchannel
Presents a poly-complexity quantum circuit implementing the random dilation superchannel for parallel channel queries, with approximate sequential extension, a no-go theorem for exact sequential dilation, and an application to exponentially improved channel storage-retrieval.
-
Quantum metrology of mixed states via purification
New purification-based reformulations of QCRB and HCRB connect mixed-state metrology bounds to those of purified states, enabling asymptotic attainment of HCRB or 2×QCRB via random channels and individual measurements.
-
Advances in quantum learning theory with bosonic systems
A concise review of sample complexities and methods for tomography and learning in continuous-variable quantum systems, with emphasis on Gaussian versus non-Gaussian states.