Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits
- URL: http://arxiv.org/abs/2012.05460v2
- Date: Sun, 6 Jun 2021 00:11:10 GMT
- Title: Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits
- Authors: Nolan J. Coble and Matthew Coudron
- Abstract summary: We present a classical algorithm for any 3D geometrically-local, polylogarithmic-depth quantum circuit.
It computes the quantity $| x |C|0otimes n>|2$ to within any inverse-polynomial additive error in quasi-polynomial time.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a classical algorithm that, for any 3D geometrically-local,
polylogarithmic-depth quantum circuit $C$ acting on $n$ qubits, and any bit
string $x\in\{0,1\}^n$, can compute the quantity $|< x |C|0^{\otimes n}>|^2$ to
within any inverse-polynomial additive error in quasi-polynomial time. It is
known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$
additive error [Mov20, KMM21]. The previous best known algorithm for this
problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute
probabilities to within additive error $\epsilon$ [BGM20]. Notably, the [BGM20]
paper included an elegant polynomial time algorithm for this estimation task
restricted to 2D circuits, which makes a novel use of 1D Matrix Product States
(MPS) carefully tailored to the 2D geometry of the circuit in question.
Surprisingly, it is not clear that it is possible to extend this use of MPS to
address the case of 3D circuits in polynomial time. This raises a natural
question as to whether the computational complexity of the 3D problem might be
drastically higher than that of the 2D problem. In this work we address this
question by exhibiting a quasi-polynomial time algorithm for the 3D case. In
order to surpass the technical barriers encountered by previously known
techniques we are forced to pursue a novel approach.
Our algorithm has a Divide-and-Conquer structure, demonstrating how to
approximate the desired quantity via several instantiations of the same problem
type, each involving 3D-local circuits on about half the number of qubits as
the original. This division step is then applied recursively, expressing the
original quantity as a weighted combination of smaller and smaller 3D-local
quantum circuits. A central technical challenge is to control correlations
arising from entanglement that may exist between the different circuit
``pieces" produced this way.
Related papers
- On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
The problem of encoded quantum gate generation is studied in this paper.
The emphReference Input Generation Algorithm (RIGA) is generalized in this work.
arXiv Detail & Related papers (2024-09-02T10:41:15Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
We describe an algorithm with quasipolynomial runtime $nO(logn)$ that samples from the output distribution of a peaked constant-depth circuit.
Our algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error.
arXiv Detail & Related papers (2023-09-15T14:01:13Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems.
We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
arXiv Detail & Related papers (2023-02-03T03:19:14Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Approximating Output Probabilities of Shallow Quantum Circuits which are
Geometrically-local in any Fixed Dimension [0.0]
We present an algorithm that can compute the quantity $|x|C|0otimes n>|2$ to within any inverse-polynomial additive error in quasi-polynomial time.
This is an extension of the result [CC21], which originally proved this result for $D = 3$.
arXiv Detail & Related papers (2022-02-16T21:37:16Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
We discuss hybrid quantum-classical algorithms for skewed linear systems for over-determined and under-determined cases.
Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth.
We present an algorithm for the special case of a factorized linear system with run time poly-logarithmic in the respective dimensions.
arXiv Detail & Related papers (2020-09-28T12:59:27Z) - A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes.
We consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set, a universal gate set.
arXiv Detail & Related papers (2020-06-22T17:21:41Z)
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.