Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiscrete Cosine Transforms on Quantum Computers
94
0
0.0
(
0
)
Added by
Andreas Klappenecker
Publication date
2001
fields
Physics
and research's language is
English
Authors
Andreas Klappenecker
Ask ChatGPT about the research
No Arabic abstract
A classical computer does not allow to calculate a discrete cosine transform on N points in less than linear time. This trivial lower bound is no longer valid for a computer that takes advantage of quantum mechanical superposition, entanglement, and interference principles. In fact, we show that it is possible to realize the discrete cosine transforms and the discrete sine transforms of size NxN and types I,II,III, and IV with as little as O(log^2 N) operations on a quantum computer, whereas the known fast algorithms on a classical computer need O(N log N) operations.
rate research
Read More
The discrete cosine and sine transforms are generalized to a triangular fragment of the honeycomb lattice. The honeycomb point sets are constructed by subtracting the root lattice from the weight lattice points of the crystallographic root system $A_2$. The two-variable orbit functions of the Weyl group of $A_2$, discretized simultaneously on the weight and root lattices, induce a novel parametric family of extended Weyl orbit functions. The periodicity and von Neumann and Dirichlet boundary properties of the extended Weyl orbit functions are detailed. Three types of discrete complex Fourier-Weyl transforms and real-valued Hartley-Weyl transforms are described. Unitary transform matrices and interpolating behaviour of the discrete transforms are exemplified. Consequences of the developed discrete transforms for transversal eigenvibrations of the mechanical graphene model are discussed.
Symmetry is a unifying concept in physics. In quantum information and beyond, it is known that quantum states possessing symmetry are not useful for certain information-processing tasks. For example, states that commute with a Hamiltonian realizing a time evolution are not useful for timekeeping during that evolution, and bipartite states that are highly extendible are not strongly entangled and thus not useful for basic tasks like teleportation. Motivated by this perspective, this paper details several quantum algorithms that test the symmetry of quantum states and channels. For the case of testing Bose symmetry of a state, we show that there is a simple and efficient quantum algorithm, while the tests for other kinds of symmetry rely on the aid of a quantum prover. We prove that the acceptance probability of each algorithm is equal to the maximum symmetric fidelity of the state being tested, thus giving a firm operational meaning to these latter resource quantifiers. Special cases of the algorithms test for incoherence or separability of quantum states. We evaluate the performance of these algorithms by using the variational approach to quantum algorithms, replacing the quantum prover with a variational circuit. We also show that the maximum symmetric fidelities can be calculated by semi-definite programs, which is useful for benchmarking the performance of the quantum algorithms for sufficiently small examples. Finally, we establish various generalizations of the resource theory of asymmetry, with the upshot being that the acceptance probabilities of the algorithms are resource monotones and thus well motivated from the resource-theoretic perspective.
Let $G_{n,r}(bbK)$ be the Grassmannian manifold of $k$-dimensional $bbK$-subspaces in $bbK^n$ where $bbK=mathbb R, mathbb C, mathbb H$ is the field of real, complex or quaternionic numbers. We consider the Radon, cosine and sine transforms, $mathcal R_{r^prime, r}$, $mathcal C_{r^prime, r}$ and $mathcal S_{r^prime, r}$, from the $L^2$ space $L^2(G_{n,r}(bbK))$ to the space $L^2(G_{n,r^prime}(bbK))$, for $r, r^prime le n-1$. The $L^2$ spaces are decomposed into irreducible representations of $G$ with multiplicity free. We compute the spectral symbols of the transforms under the decomposition. For that purpose we prove two Bernstein-Sato type formulas on general root systems of type BC for the sine and cosine type functions on the compact torus $mathbb R^r/{2pi Q^vee}$ generalizing our recent results for the hyperbolic sine and cosine functions on the non-compact space $mathbb R^r$. We find then also a characterization of the images of the transforms. Our results generalize those of Alesker-Bernstein and Grinberg. We prove further that the Knapp-Stein intertwining operator for certain induced representations is given by the sine transform and we give the unitary structure of the Steins complementary series in the compact picture.
This expository paper reviews some of the recent uses of computational algebraic geometry in classical and quantum optimization. The paper assumes an elementary background in algebraic geometry and adiabatic quantum computing (AQC), and concentrates on presenting concrete examples (with Python codes tested on a quantum computer) of applying algebraic geometry constructs: solving binary optimization, factoring, and compiling. Reversing the direction, we also briefly describe a novel use of quantum computers to compute Groebner bases for toric ideals. We also show how Groebner bases play a role in studying AQC at a fundamental level within a Morse theory framework. We close by placing our work in perspective, by situating this leg of the journey, as part of a marvelous intellectual expedition that began with our ancients over 4000 years ago.
Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigate using this paradigm to perform $k$-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We compare the performance of this approach to classical $k$-means clustering both numerically and experimentally on IBM Q hardware. We are able to find data sets where coresets work well relative to random sampling and where QAOA could potentially outperform standard $k$-means on a coreset. However, finding data sets where both coresets and QAOA work well--which is necessary for a quantum advantage over $k$-means on the entire data set--appears to be challenging.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
