Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Jones polynomial: quantum algorithms and applications in quantum complexity theory
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.
rate research
Read More
Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $Ax = lambda Bx$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $Omega(sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.
Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can in principle be solved on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various classical models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem. By constructing a parent Hamiltonian, whose ground state is the desired quantum state, we relate the asymptotic scaling of the state preparation time to the nature of transitions between distinct quantum phases. These insights enable us to identify adiabatic paths that achieve a quantum speedup over classical Markov chain algorithms. In addition, we show that parent Hamiltonians for the problem of sampling from independent sets on certain graphs can be naturally realized with neutral atoms interacting via highly excited Rydberg states.
$ ewcommand{eps}{varepsilon} $In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its richness. In the PAC model $$ ThetaBig(frac{d}{eps} + frac{log(1/delta)}{eps}Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-delta$, a hypothesis $h$ that is $eps$-close to the target concept $c$. In the related agnostic model, where the samples need not come from a $cin C$, we know that $$ ThetaBig(frac{d}{eps^2} + frac{log(1/delta)}{eps^2}Big) $$ examples are necessary and sufficient to output an hypothesis $hin C$ whose error is at most $eps$ worse than the best concept in $C$. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting, quantum examples cannot be much more powerful: the required number of quantum examples is $$ OmegaBig(frac{d^{1-eta}}{eps} + d + frac{log(1/delta)}{eps}Big)mbox{ for all }eta> 0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $log(d/eps)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the Pretty Good Measurement on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors.
We implement a Quantum Autoencoder (QAE) as a quantum circuit capable of correcting Greenberger-Horne-Zeilinger (GHZ) states subject to various noisy quantum channels : the bit-flip channel and the more general quantum depolarizing channel. The QAE shows particularly interesting results, as it enables to perform an almost perfect reconstruction of noisy states, but can also, more surprisingly, act as a generative model to create noise-free GHZ states. Finally, we detail a useful application of QAEs : Quantum Secret Sharing (QSS). We analyze how noise corrupts QSS, causing it to fail, and show how the QAE allows the QSS protocol to succeed even in the presence of noise.
This is a pre-publication version of a forthcoming book on quantum atom optics. It is written as a senior undergraduate to junior graduate level textbook, assuming knowledge of basic quantum mechanics, and covers the basic principles of neutral atom matter wave systems with an emphasis on quantum technology applications. The topics covered include: introduction to second quantization of many-body systems, Bose-Einstein condensation, the order parameter and Gross-Pitaevskii equation, spin dynamics of atoms, spinor Bose-Einstein condensates, atom diffraction, atomic interferometry beyond the standard limit, quantum simulation, squeezing and entanglement with atomic ensembles, quantum information with atomic ensembles. This book would suit students who wish to obtain the necessary skills for working with neutral atom many-body atomic systems, or could be used as a text for an undergraduate or graduate level course (exercises are included throughout). This is a near-final draft of the book, but inevitably errors may be present. If any errors are found, we welcome you to contact us and it will be corrected before publication. (TB: tim.byrnes[at]nyu.edu, EI: ebube[at]nyu.edu)
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
