Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Schur Sampling Circuits can be Strongly Simulated
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Permutational Quantum Computing (PQC) [emph{Quantum~Info.~Comput.}, textbf{10}, 470--497, (2010)] is a natural quantum computational model conjectured to capture non-classical aspects of quantum computation. An argument backing this conjecture was the observation that there was no efficient classical algorithm for estimation of matrix elements of the $S_n$ irreducible representation matrices in the Youngs orthogonal form, which correspond to transition amplitudes of a broad class of PQC circuits. This problem can be solved with a PQC machine in polynomial time, but no efficient classical algorithm for the problem was previously known. Here we give a classical algorithm that efficiently approximates the transition amplitudes up to polynomial additive precision and hence solves this problem. We further extend our discussion to show that transition amplitudes of a broader class of quantum circuits -- the Quantum Schur Sampling circuits -- can be also efficiently estimated classically.
rate research
Read More
Many quantum algorithms can be represented in a form of a classical circuit positioned between quantum Fourier transformations. Motivated by the search for new quantum algorithms, we turn to circuits where the latter transformation is replaced by the $textsf{SU}(2)$ quantum Schur Transform -- a global transformation which maps the computational basis to a basis defined by angular momenta. We show that the output distributions of these circuits can be approximately classically sampled in polynomial time if they are sufficiently close to being sparse, thus isolating a regime in which these Quantum $textsf{SU}(2)$ Schur Circuits could lead to algorithms with exponential computational advantage. Our work is primarily motivated by a conjecture that underpinned the hardness of Permutational Quantum Computing, a restricted quantum computational model that has the above circuit structure in one of its computationally interesting regimes. The conjecture stated that approximating transition amplitudes of Permutational Quantum Computing model to inverse polynomial precision on a classical computer is computationally hard. We disprove the extended version of this conjecture -- even in the case when the hardness of approximation originated from a difficulty of finding the large elements in the output probability distributions. Finally, we present some evidence that output of the above Permutational Quantum Computing circuits could be efficiently approximately sampled from on a classical computer.
Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered, and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in $mathrm{P}$ this would imply the collapse of the complexity hierarchy $mathrm{P} subseteq mathrm{NP} subseteq # mathrm{P}$.
We show that low-depth random quantum circuits can be efficiently simulated by a quantum teleportation-inspired algorithm. By using logical qubits to redirect and teleport the quantum information in quantum circuits, the original circuits can be renormalized to new circuits with a smaller number of logical qubits. We demonstrate the algorithm to simulate several random quantum circuits, including 1D-chain 1000-qubit 42-depth, 2D-grid 125*8-qubit 42-depth and 2D-Bristlecone 72-qubit 32-depth circuits. Our results present a memory-efficient method with a clear physical picture to simulate low-depth random quantum circuits.
Optimization algorithms and Monte Carlo sampling algorithms have provided the computational foundations for the rapid growth in applications of statistical machine learning in recent years. There is, however, limited theoretical understanding of the relationships between these two kinds of methodology, and limited understanding of relative strengths and weaknesses. Moreover, existing results have been obtained primarily in the setting of convex functions (for optimization) and log-concave functions (for sampling). In this setting, where local properties determine global properties, optimization algorithms are unsurprisingly more efficient computationally than sampling algorithms. We instead examine a class of nonconvex objective functions that arise in mixture modeling and multi-stable systems. In this nonconvex setting, we find that the computational complexity of sampling algorithms scales linearly with the model dimension while that of optimization algorithms scales exponentially.
We consider the class of quantum stochastic evolutions ($SLH$-models) leading to a quantum dynamical semigroup over a fixed quantum mechanical system (taken to be finite-dimensional). We show that if the semigroup is dissipative, that is, the coupling operators are non-zero, then a dynamical decoupling scheme based on unitary rotations on the system space cannot suppress decoherence even in the limit where the period between pulses vanishes. We emphasize the role of the Fock space dilation used here to construct a quantum stochastic model, as there are often dilations of the same semigroup using an environmental noise model of lower level of chaoticity for which dynamical decoupling is effective. We show that the Chebotarev-Gregoratti Hamiltonian behind a quantum stochastic evolution is an example of a Hamiltonian dynamics on a joint system-environment that cannot be dynamically decoupled in this way.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
