The Parameterized Complexity of Quantum Verification

• URL: http://arxiv.org/abs/2202.08119v1
• Date: Wed, 16 Feb 2022 14:53:42 GMT
• Title: The Parameterized Complexity of Quantum Verification
• Authors: Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, Bryan O'Gorman
• Abstract summary: We show that for the problem of quantum circuit satisfiability, there exists an algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates. We derive new lower bounds on the $T$-count of circuit satisfiability instances and the $$-count of the $W$-state.
• Score: 7.7155343772895275
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the study of parameterized complexity of $\textsf{QMA}$ problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + $t$ $T$-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most $t$ qubits (independent of the system size). Furthermore, we derive new lower bounds on the $T$-count of circuit satisfiability instances and the $T$-count of the $W$-state assuming the classical exponential time hypothesis ($\textsf{ETH}$). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.

Related papers

• Pseudo-deterministic Quantum Algorithms [7.46931129146594]
  We show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms.<n>On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead.
  arXiv  Detail & Related papers  (2026-02-19T18:54:47Z)
• Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers [1.1666234644810893]
  Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in potential quantum computing applications.<n>Main parameters determining the complexity of QLS solvers are the condition number $$ and sparsity $s$ of the linear system.<n>We prove the lower bound of $(sqrts)$ for any quantum algorithm that solves QLS with constant error.
  arXiv  Detail & Related papers  (2026-01-23T12:27:08Z)
• Performance Guarantees for Quantum Neural Estimation of Entropies [31.955071410400947]
  Quantum neural estimators (QNEs) combine classical neural networks with parametrized quantum circuits.<n>We study formal guarantees for QNEs of measured relative entropies in the form of non-asymptotic error risk bounds.<n>Our theory aims to facilitate principled implementation of QNEs for measured relative entropies.
  arXiv  Detail & Related papers  (2025-11-24T16:36:06Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective. We construct a zeroth-order quantum estimator for the surrogate oracle function.
  arXiv  Detail & Related papers  (2024-10-21T16:52:26Z)
• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC) By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity, leading to general theorems bounding the time complexity of a class of algorithms.
  arXiv  Detail & Related papers  (2024-06-06T11:33:29Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes [34.225996865725605]
  We develop a hardware-efficient, fault-tolerant approach to realizing quantum sampling circuits.<n>We develop a theory of second-moment properties of degree-$D$ IQP circuits for analyzing hardness and verification of random sampling.<n>Our results highlight fault-tolerant compiling as a powerful tool in co-configurable algorithms with specific error-correcting codes and realistic hardware.
  arXiv  Detail & Related papers  (2024-04-29T18:00:03Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  We show that max-k-SSAT is the computational algorithm on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory. We also prove that max-k-SSAT is on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory.
  arXiv  Detail & Related papers  (2024-03-05T15:03:47Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
  We develop a hybrid quantum-classical algorithm to estimate the partition function. Our algorithm requires only a shallow $mathcalO(1)$-depth quantum circuit. Shallow-depth quantum circuits are considered vitally important for currently available NISQ (Noisy Intermediate-Scale Quantum) devices.
  arXiv  Detail & Related papers  (2021-09-22T02:03:35Z)

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.