This uses a sub-string search, so that "graph" matches both "graph" and "graphical".
This search only searches by keyword. If you'd like, you can also search by researcher.
Found 7 results.
Listing from newest to oldest
TR-CS-2006-12
On the Equational Definability of Brouwer-Zadeh Lattices
Matthew Spinks and Robert Veroff
We give an axiomatisation of the variety of Brouwer-Zadeh lattices, suitable for applications to quantum theory.
TR-CS-2003-16
Generic Quantum Fourier Transforms
Cristopher Moore, Daniel Rockmore, and Alexander Russell
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by ``quantizing'' the separation of variables technique that has been so successful in the study of classical Fourier transform computations. Specifically, this framework applies the existence of computable Bratteli diagrams, adapted factorizations, and Gel'fand-Tsetlin bases to offer efficient quantum circuits for the QFT over a wide variety a finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, the method gives rise to the first subexponential-size quantum circuits for the QFT over the linear groups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime power q.
TR-CS-2002-35
The Hidden Subgroup Problem in Affine Groups:
Basis Selection in Fourier Sampling
Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state Psi uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of Psi is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups which can be reconstructed via the strong method by not by the weak, or any other known, method.
In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of the form Z_q x Z_p, where q | (p-1) and q = p over polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We also give an information-theoretic solution to the the hidden conjugate problem over the affine groups, which generalizes known results for the dihedral groups. In particular, this gives rise to an information-theoretic solution for the hidden subgroup problem over the Affine groups for a prime p where p-1 has polylog(p) divisors. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
TR-CS-2002-01
Quantum and stochastic branching programs of bounded width
Farid Ablayev, Cristopher Moore, and Christopher Pollett
We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC^1=ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC^1.
TR-CS-2001-09
Counting, Fanout, and the Complexity of Quantum QACC
Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett
Quantum Information and Computation 2(1) (2002) 35-65.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum Mod_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q, p>1, Mod_q is equivalent to Mod_p (up to constant depth). This implies that QAC^0 with unbounded fanout gates, denoted QAC_wf^0, is the same as QACC[q] and QACC for all q. Since ACC[p] != ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts.
TR-CS-2001-06
Quantum Walks on the Hypercube
Cristopher Moore and Alexander Russell
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in 0.785 n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is exactly uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.
TR-CS-2000-37
Parallel Quantum Computation and Quantum Codes
Cristopher Moore and Martin Nilsson
To appear in SIAM Journal on Computing.
We study the class QNC of efficient parallel quantum circuits, the quantum analog of NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or more generally any circuit consisting of controlled-not gates, controlled pi-shifts, and Hadamard gates. Finally, while we note the exact quantum Fourier transform can be parallelized to linear depth, we conjecture that neither it nor a simpler ``staircase'' circuit can be parallelized to less than this.
News & Events | People | Academics | Research | Jobs | Companies | Visitors | Computer Facilities | Home
