We study the long-standing open question on the power of unique witnesses in quantum protocols, which asks if $\textsf{UniqueQMA}$, a variant of $\textsf{QMA}$ whose accepting witness space is 1-dimensional, contains $\mathsf{QMA}$ under quantum reductions. This work rules out any black-box reduction from $\mathsf{QMA}$ to $\mathsf{UniqueQMA}$ by showing a quantum oracle separation between $\mathsf{BQP}^\mathsf{UniqueQMA}$ and $\mathsf{QMA}$. This provides a contrast to the classical case, where the Valiant-Vazirani theorem shows a black-box randomized reduction from $\mathsf{UniqueNP}$ to $\mathsf{NP}$, and suggests the need for studying the structure of the ground space of local Hamiltonians in distilling a potential unique witness. Via similar techniques, we show, relative to a quantum oracle, that $\mathsf{QMA}^\mathsf{QMA}$ cannot decide quantum approximate counting, ruling out a quantum analogue of Stockmeyer's algorithm in the black-box setting. We then ask a natural question; what structural properties of the local Hamiltonian problem can we exploit? We introduce a physically motivated candidate by showing that the ground energy of local Hamiltonians that satisfy a computational variant of the eigenstate thermalization hypothesis (ETH) can be estimated through a $\mathsf{UniqueQMA}$ protocol. Our protocol can be viewed as a quantum expander test in a low energy subspace of the Hamiltonian and verifies a unique entangled state across two copies of the subspace. This allows us to conclude that if $\mathsf{UniqueQMA}$ is not equivalent to $\mathsf{QMA}$, then $\mathsf{QMA}$-hard Hamiltonians must violate ETH under adversarial perturbations. This also serves as evidence that chaotic local Hamiltonians, such as the SYK model may be computationally simpler than general local Hamiltonians.

The Gaussian noise stability of a function f: ℝn → {-1,1} is the expected value of f (x) · f (y) over ρ-correlated Gaussian random variables x and y. Borell's inequality states that for —1 ≤ ρ ≤ 0, this is minimized by the mean-zero halfspace f (x) = sign(x1). In this work, we conjecture that a natural generalization of this result holds for functions f: ℝn → Sk-1 which output k-dimensional unit vectors. Our main conjecture, which we call the vector-valued Borell's inequality, asserts that the expectation Ex~ρy 〈f(x), f(y)〉 is minimized by the function f (x) = x≤k/||x≤k||, where x≤k = (x1,…, xk). We give several pieces of evidence in favor of this conjecture, including a proof that it does indeed hold in the special case of n = k.

SUMMARY: Reference genomes are refined to reflect error corrections and other improvements. While this process improves novel data generation and analysis, incorporating data analyzed on an older reference genome assembly requires transforming the coordinates and representations of the data to the new assembly. Multiple tools exist to perform this transformation for coordinate-only data types, but none supports accurate transformation of genome-wide short variation. Here we present GenomeWarp, a tool for efficiently transforming variants between genome assemblies. GenomeWarp transforms regions and short variants in a conservative manner to minimize false positive and negative variants in the target genome, and converts over 99% of regions and short variants from a representative human genome. AVAILABILITY AND IMPLEMENTATION: GenomeWarp is written in Java. All source code and the user manual are freely available at https://github.com/verilylifesciences/genomewarp. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.