29 problems

A quantum circuit is a sequence of quantum gates, with its depth and number of gates measuring the elapsed circuit time and circuit size, respectively. The Brown–Susskind conjectur…

AdS/CFT complexity conjecture. Certain quantum states arising in the AdS/CFT theory have high state complexity, and the growth of this complexity is related to the growth of gravit…

Apte–Parekh–Sud conjectures. For every such graph $G$ and every $0\leq k\leq n$,

Geometric complexity conjecture. In holographic theories of gravity, the complexity of evolving TFD states should be geometrized, possibly as the volume of distinguished spacelike…

Near-tightness conjecture. For a class of well-structured families of states, $C_R(\rho)$ is also bounded from above by $C_{\mathrm{opt}}(\rho)$; equivalently, there is an upper bo…

Near-tightness conjecture. For a given hardware capability $\Gamma_R$, there exist constants $a(\Gamma_R)$ and $b(\Gamma_R)$ depending only on $\Gamma_R$ such that

RCC–Krylov correspondence conjecture. For certain chaotic systems, RCC and Krylov complexity may exhibit a monotonic or order-preserving correspondence.

Let $U_{NK}$ be the top-left $N\times K$ submatrix of an $M\times M$ Haar-random unitary matrix. Let $Z=Z_{N,K}$ be a random matrix distributed according to either…

CoRE-hardness conjecture. Deciding which of these two cases holds is $\mathrm{coRE}$-hard; equivalently, $\mathrm{MIP}^{\mathrm{co}}=\mathrm{coRE}$.

Let $G$ be a finite black-box group generated by $g_1,\ldots,g_k$, and let $h$ be a group element. The Group Non-Membership problem asks whether $h\notin G$. Aaronson–Kuperberg's c…

Let $G$ be sampled uniformly from graph states, and let $d4af$ be the set of eigenstates of the operators $X+Y$ and $X-Y$. For an $n$-qubit product state, write…

Let $U$ be a quantum circuit drawn from a distribution $\mathcal{D}$, and let … A classical algorithm is polynomial-time if it runs in time polynomial in the circuit description an…

QMA(2)-completeness conjecture. The pure-state version of the consistency of local density matrices problem should be complete for $\mathsf{QMA}(2)$.

Let $\Lambda\subset\mathbb{R}^D$ be a lattice with covering radius $\rho$, the smallest radius such that the collection of radius-$\rho$ balls centered at points of $\Lambda$ cover…

Quantum approximate counting intermediate-class conjecture. Quantum approximate counting is not $\#\mathsf{P}$-hard; equivalently, it defines an intermediate class lying somewhere…

Let $\mathbb{T}$ denote the unit circle, let $X$ be sampled from the complex Gaussian ensemble $\mathcal{G}=\mathcal{N}_{\mathbb{C}}(0,1)^{n\times n}$, and let…

In the AdS/CFT correspondence, the boundary state is a state in the conformal field theory dual to a bulk spacetime containing a wormhole, and quantum circuit complexity is the min…

Bishop–Gromov tightness conjecture. The infinite-cliff metric has diameter

A holographic state is a boundary state in the anti-de-Sitter-space/conformal-field-theory correspondence, and its complexity measures the resources required to prepare it with a q…

Generic FLO hardness conjecture. Approximating $p_{\mathbf{x}}(V,\Psi_{\mathrm{in}})$ to relative error is $\#\mathrm{P}$-hard for generic FLO circuits initialized in…

Let $V$ be a passive or active fermionic linear-optics circuit initialized in the state $\left|\Psi_{\mathrm{in}}\right>$, let $\mathbf{x}_0$ be a fiducial outcome, and let…

Consider computational problems, with instances or problems equipped with an appropriate measure-theoretic notion of majority, and distinguish problems possessing exploitable struc…

Given a local Hamiltonian $H$, real numbers $a<b$, and the promise that the minimum eigenvalue of $H$ is either less than $a$ or greater than $b$, consider the promise problem of d…

Let $H=\frac{1}{m}\sum_{i=1}^m\Pi_i$ be a local Hamiltonian, where the terms $\Pi_i$ are local projectors, and let a quantum state be trivial if it can be obtained from a product s…

Quantum supremacy conjecture. There is no classical randomized algorithm that performs RCS to inverse-polynomial total variation-distance error.