Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Knot and link invariants naturally arise from any braided Hopf algebra. We consider the computational complexity of the invariants arising from an elementary family of finite-dimensional Hopf algebras: quantum doubles of finite groups (denoted D(G), for a group G). Regarding algorithms for these invariants, we develop quantum circuits for the quantum Fourier transform over D(G); in general, we show that when one can uniformly and efficiently carry out the quantum Fourier transform over the centralizers Z(g) of the elements of G, one can efficiently carry out the quantum Fourier transform over D(G). We apply these results to the symmetric groups to yield efficient circuits for the quantum Fourier transform over D(S_n). With such a Fourier transform, it is straightforward to obtain additive approximation algorithms for the related link invariant. Additionally, we show that certain D(G) invariants (such as D(A_n) invariants) are BPP-hard to additively approximate, SBP-hard to multiplicatively approximate, and #P-hard to exactly evaluate. Finally, we make partial progress on the question of simulating anyonic computation in groups uniformly as a function of the group size. In this direction, we provide efficient quantum circuits for the Clebsch-Gordan transform over D(G) for fluxon irreps, i.e., irreps of D(G) characterized by a conjugacy class of G. For general irreps, i.e., those which are associated with a conjugacy class of G and an irrep of a centralizer, we present an efficient implementation under certain conditions such as when there is an efficient Clebsch-Gordan transform over the centralizers. We remark that this also provides a simulation of certain anyonic models of quantum computation, even in circumstances where the group may have size exponential in the size of the circuit.
rate research
Read More
Given a quantum circuit, a quantum computer can sample the output distribution exponentially faster in the number of bits than classical computers. A similar exponential separation has yet to be established in generative models through quantum sample learning: given samples from an n-qubit computation, can we learn the underlying quantum distribution using models with training parameters that scale polynomial in n under a fixed training time? We study four kinds of generative models: Deep Boltzmann machine (DBM), Generative Adversarial Networks (GANs), Long Short-Term Memory (LSTM) and Autoregressive GAN, on learning quantum data set generated by deep random circuits. We demonstrate the leading performance of LSTM in learning quantum samples, and thus the autoregressive structure present in the underlying quantum distribution from random quantum circuits. Both numerical experiments and a theoretical proof in the case of the DBM show exponentially growing complexity of learning-agent parameters required for achieving a fixed accuracy as n increases. Finally, we establish a connection between learnability and the complexity of generative models by benchmarking learnability against different sets of samples drawn from probability distributions of variable degrees of complexities in their quantum and classical representations.
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by proving that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.
We construct a quantum oracle relative to which $mathsf{BQP} = mathsf{QMA}$ but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be broken by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if $mathsf{BQP} = mathsf{PP}$. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
The literature on the exponential Fourier approach to the one-dimensional quantum harmonic oscillator problem is revised and criticized. It is shown that the solution of this problem has been built on faulty premises. The problem is revisited via the Fourier sine and cosine transform method and the stationary states are properly determined by requiring definite parity and square-integrable eigenfunctions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
