49 problems

Brown–Susskind conjecture on quantum circuit complexity growth and saturation
arXiv@arxiv
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…
Conjectureopenquantum-circuits quantum-complexity
0
Universal-gateset spectral-gap conjecture
arXiv@arxiv
Let $\mathcal{G}$ be a finite universal gateset, and say that $\mathcal{G}$ has a spectral gap when the spectral-gap property used in the paper's random-circuit equidistribution ar…
Conjectureopenquantum-circuits quantum-information spectral-gap
0
The expressibility–trainability trade-off in variational quantum ansätze
arXiv@arxiv
Consider the SE and HEA ansätze, where SE uses five times fewer entangling gates than HEA, and let a target state be representable by an ansatz when it lies within that ansatz's ex…
Conjectureopenquantum-circuits quantum-machine-learning variational-quantum-algorithms
0
Yang–Baxter integrability conjecture for open-boundary time-periodic circuits
arXiv@arxiv
Yang–Baxter integrability conjecture. For two types of inhomogeneities, a circuit is Yang–Baxter integrable if the bulk gate is a solution of the Yang–Baxter equation, the boundary…
Conjectureopenintegrability quantum-circuits yang-baxter-equation
0
Algebraic-depth classical hardness conjecture for random brickwall linear optical networks
arXiv@arxiv
Let $n$ denote the number of modes and let $d$ denote the depth of a random brickwall linear optical network, with the input and sampling setting as considered in the paper. Classi…
Conjectureopenlinear-optical-networks quantum-circuits sampling-complexity
1
Quantum-computational decidability of bounded light cones
arXiv@arxiv
Consider a unitary circuit given by a classical description, and fix finite times. A bounded light cone means that the circuit's causal influence is bounded in the sense studied in…
Conjectureopencausal-constraints computational-complexity quantum-circuits
1
Polylogarithmic-depth symmetric pseudorandom quantum circuits
arXiv@arxiv
Polylogarithmic-depth symmetric PRU conjectural construction. Under the conjecture that no subexponential-time quantum algorithm can solve LWE, random quantum circuits over $n$ qub…
Conjectureopenpseudorandomness quantum-circuits quantum-information
1
Translation-invariant symmetric pseudorandom unitaries from subexponential LWE hardness
arXiv@arxiv
Translation-invariant symmetric PRU conjectural construction. Under the conjecture that no subexponential-time quantum algorithm can solve LWE, one-dimensional translation-invarian…
Conjectureopenpseudorandomness quantum-circuits translation-invariance
1
Subexponentially secure symmetric pseudorandom unitaries in extremely low depth
arXiv@arxiv
Extremely low-depth symmetric PRU conjectural construction. Under the conjecture that no subexponential-time quantum algorithm can solve LWE, symmetric PRUs on $n$ qudits with secu…
Conjectureopenpseudorandomness quantum-circuits quantum-information
0
Fukai et al.'s free-fermion solvability conjecture for three-site-periodic brickwork circuits
arXiv@arxiv
Free-fermion solvability conjecture. The circuits defined by $\mathcal{V}^{({\rm III})}_M$ are solvable by free-fermion decomposition (FFD).
Conjectureopenfree-fermions many-body-physics quantum-circuits
1
Near-tightness conjecture for Reference-Contingent Complexity
arXiv@arxiv
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…
Conjectureopenquantum-circuits quantum-complexity quantum-information
0
Near-tightness conjecture for Reference-Contingent Complexity
arXiv@arxiv
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
Conjectureopenquantum-circuits quantum-complexity quantum-information
0
Free-fermionic solvability conjecture for the selected quantum circuit
arXiv@arxiv
The cited quantum circuit is a product of three-site operators obtained from a transfer matrix of the free-fermions-in-disguise model at a special spectral parameter. Free-fermioni…
Conjectureopenfree-fermions integrable-systems quantum-circuits
0
The quantum fanout separation conjecture for constant-depth QAC-circuits
arXiv@arxiv
A quantum circuit family using unbounded quantum AND-gates and single-qubit gates is a QAC-circuit. The converse of the known simulation of quantum AND-gates by constant-depth circ…
Conjectureopencircuit-complexity quantum-circuits quantum-computation
0
Constant-factor equivalence of CZ-distance and CZ-complexity
arXiv@arxiv
The CZ-distance and CZ-complexity of a graph are the two graph-state preparation measures defined in the paper, with CZ-complexity additionally allowing arbitrarily many measuremen…
Conjectureopengraph-states quantum-circuits vertex-minors
0
The iSWAP optimality conjecture for the brickwork model
arXiv@arxiv
Let $n$ be the number of qubits in the brickwork model, let $t$ denote the circuit depth or number of layers, and let…
Conjectureopenquantum-circuits quantum-information unitary-designs
0
The iSWAP equality conjecture for complete-graph gadgets
arXiv@arxiv
Let $K_n$ be the complete graph on $n$ vertices, and consider a gadget associated with a family of 2-local gates having parameter $a=\frac{5}{9}$ in the notation of the paper. Let…
Conjectureopenquantum-circuits quantum-information unitary-designs
0
The iSWAP optimality conjecture for 2-local unitary circuit ensembles
arXiv@arxiv
Let $n\geq 3$ , let $\mathcal{G}$ be a fixed connected graph, and let $\mathcal{E}$ be a 2-local unitary circuit ensemble. Write…
Conjectureopenquantum-circuits quantum-information unitary-designs
0
Finite-time teleportation transition conjecture for random 2D circuits
arXiv@arxiv
Let $B$ be a subset of sites measured in a random two-dimensional quantum circuit, and let measurement-induced entanglement (MIE) denote the entanglement generated between separate…
Conjecturesolvedmeasurement-induced-entanglement quantum-circuits quantum-entanglement
0
The finite eventual order conjecture for canonical elements of weak Hopf algebras
arXiv@arxiv
Weak Hopf exponent conjecture. There exist positive integers $\eta$ and $\nu$ such that
Conjectureopenhopf-algebras quantum-circuits weak-hopf-algebras
0
XQUATH (Linear Cross-Entropy Quantum Threshold Assumption)
arXiv@arxiv
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…
Conjecturerefutedquantum-circuits quantum-complexity quantum-supremacy
0
Ippoliti et al.'s constant shadow-norm conjecture
arXiv@arxiv
Let $P$ be a Frobenius-normalized Pauli observable on $n$ qubits, with normalization $P/\sqrt{2^n}$ , and consider random Clifford circuits of depth $\log(n)$ . Constant shadow-norm…
Conjectureopenclassical-shadows quantum-circuits
0
Bouland–Bertoni et al.'s all-state shallow-shadow conjecture
arXiv@arxiv
Consider classical-shadow tomography using random Clifford circuits of depth $d=\Theta(\log n)$ , and let the input state be an arbitrary $n$ -qubit state. All-state shallow-shadow c…
Conjectureopenclassical-shadows quantum-circuits
0
Low-depth pseudorandom unitaries under the LWE hardness conjecture
arXiv@arxiv
Let $n$ be the number of qubits, and consider random quantum circuits over these qubits in either a 1D or an all-to-all architecture. Let $d$ denote the circuit depth, and let LWE…
Conjectureopenlearning-with-errors pseudorandomness quantum-circuits
0
The mixed parallel-and-consecutive error-channel modeling conjecture for noisy quantum circuits
arXiv@arxiv
Mixed error-channel modeling conjecture. It might be more accurate to model a noisy quantum circuit as a mix of parallel and consecutive error channels.
Conjectureopennisq quantum-circuits quantum-error-correction
0