Publish in OALib Journal

ISSN: 2333-9721

APC: Only $99


Search Results: 1 - 10 of 59 matches for " Christino Tamon "
All listed articles are free for downloading (OA Articles)
Page 1 /59
Display every page Item
Quantum Computation Relative to Oracles
Christino Tamon,Tomoyuki Yamakami
Physics , 2000,
Abstract: This paper has been withdrawn by Christino Tamon and Tomoyuki Yamakami because of errors of the main theorems. An erratum appeared in the Proceedings of the UMC 2000 Conference published by Springer.
Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
Leonid Fedichkin,Dmitry Solenov,Christino Tamon
Physics , 2005,
Abstract: We prove analytical results showing that decoherence can be useful for mixing time in a continuous-time quantum walk on finite cycles. This complements the numerical observations by Kendon and Tregenna (Physical Review A 67 (2003), 042315) of a similar phenomenon for discrete-time quantum walks. Our analytical treatment of continuous-time quantum walks includes a continuous monitoring of all vertices that induces the decoherence process. We identify the dynamics of the probability distribution and observe how mixing times undergo the transition from quantum to classical behavior as our decoherence parameter grows from zero to infinity. Our results show that, for small rates of decoherence, the mixing time improves linearly with decoherence, whereas for large rates of decoherence, the mixing time deteriorates linearly towards the classical limit. In the middle region of decoherence rates, our numerical data confirms the existence of a unique optimal rate for which the mixing time is minimized.
Quantum DNF Learnability Revisited
Jeffrey C. Jackson,Christino Tamon,Tomoyuki Yamakami
Physics , 2002,
Abstract: We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^{3}/\epsilon + s^{2}/\epsilon^{2})$, where $s$ is the size of DNF formula and $\epsilon$ is the PAC error accuracy. If $s$ and $1/\epsilon$ are comparable, this gives a modest improvement over a previously known classical query complexity of $\tilde{O}(ns^{2}/\epsilon^{2})$. We also show a lower bound of $\Omega(s\log n/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF of size $s$ with $n$ inputs under the uniform distribution.
A note on graphs resistant to quantum uniform mixing
William Adamczak,Kevin Andrew,Peter Hernberg,Christino Tamon
Physics , 2003,
Abstract: Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the $n$-cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs $K_{n}$, the continuous-time quantum walk is neither instantaneous (except for $n=2,3,4$) nor average uniform mixing (except for $n=2$). We explore two natural {\em group-theoretic} generalizations of the $n$-cube as a $G$-circulant and as a bunkbed $G \rtimes \Int_{2}$, where $G$ is a finite group. Analyses of these classes suggest that the $n$-cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.
Mixing of Quantum Walks on Generalized Hypercubes
Ana Best,Markus Kliegl,Shawn Mead-Gluchacki,Christino Tamon
Physics , 2008,
Abstract: We study continuous-time quantum walks on graphs which generalize the hypercube. The only known family of graphs whose quantum walk instantaneously mixes to uniform is the Hamming graphs with small arities. We show that quantum uniform mixing on the hypercube is robust under the addition of perfect matchings but not much else. Our specific results include: (1) The graph obtained by augmenting the hypercube with an additive matching is instantaneous uniform mixing whenever the parity of the matching is even, but with a slower mixing time. This strictly includes Moore-Russell's result on the hypercube. (2) The class of Hamming graphs is not uniform mixing if and only if its arity is greater than 5. This is a tight characterization of quantum uniform mixing on Hamming graphs; previously, only the status of arity less than 5 was known. (3) The bunkbed graph B(A[f]), defined by a hypercube-circulant matrix A and a Boolean function f, is not uniform mixing if the Fourier transform of f has small support. This explains why the hypercube is uniform mixing and why the join of two hypercubes is not.
Mixing in Continuous Quantum Walks on Graphs
Amir Ahmadi,Ryan Belk,Christino Tamon,Carolyn Wendler
Physics , 2002,
Abstract: Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.
Perfect state transfer, graph products and equitable partitions
Yang Ge,Benjamin Greenberg,Oscar Perez,Christino Tamon
Mathematics , 2010,
Abstract: We describe new constructions of graphs which exhibit perfect state transfer on continuous-time quantum walks. Our constructions are based on variants of the double cones [BCMS09,ANOPRT10,ANOPRT09] and the Cartesian graph products (which includes the n-cube) [CDDEKL05]. Some of our results include: (1) If $G$ is a graph with perfect state transfer at time $t_{G}$, where $t_{G}\Spec(G) \subseteq \ZZ\pi$, and $H$ is a circulant with odd eigenvalues, their weak product $G \times H$ has perfect state transfer. Also, if $H$ is a regular graph with perfect state transfer at time $t_{H}$ and $G$ is a graph where $t_{H}|V_{H}|\Spec(G) \subseteq 2\ZZ\pi$, their lexicographic product $G[H]$ has perfect state transfer. (2) The double cone $\overline{K}_{2} + G$ on any connected graph $G$, has perfect state transfer if the weights of the cone edges are proportional to the Perron eigenvector of $G$. This generalizes results for double cone on regular graphs studied in [BCMS09,ANOPRT10,ANOPRT09]. (3) For an infinite family $\GG$ of regular graphs, there is a circulant connection so the graph $K_{1}+\GG\circ\GG+K_{1}$ has perfect state transfer. In contrast, no perfect state transfer exists if a complete bipartite connection is used (even in the presence of weights) [ANOPRT09]. We also describe a generalization of the path collapsing argument [CCDFGS03,CDDEKL05], which reduces questions about perfect state transfer to simpler (weighted) multigraphs, for graphs with equitable distance partitions.
Which Exterior Powers are Balanced?
Devlin Mallory,Abigail Raz,Christino Tamon,Thomas Zaslavsky
Mathematics , 2013,
Abstract: A signed graph is a graph whose edges are given (-1,+1) weights. In such a graph, the sign of a cycle is the product of the signs of its edges. A signed graph is called balanced if its adjacency matrix is similar to the adjacency matrix of an unsigned graph via conjugation by a diagonal (-1,+1) matrix. For a signed graph $\Sigma$ on n vertices, its exterior k-th power, where k=1,..,n-1, is a graph $\bigwedge^{k} \Sigma$ whose adjacency matrix is given by \[ A({$\bigwedge^{k} {\Sigma}$}) = P^{\dagger} A(\Sigma^{\Box k}) P, \] where P is the projector onto the anti-symmetric subspace of the k-fold tensor product space $(\mathbb{C}^{n})^{\otimes k}$ and $\Sigma^{\Box k}$ is the k-fold Cartesian product of $\Sigma$ with itself. The exterior power creates a signed graph from any graph, even unsigned. We prove sufficient and necessary conditions so that $\bigwedge^{k} \Sigma$ is balanced. For k=1,..,n-2, the condition is that either $\Sigma$ is a signed path or $\Sigma$ is a signed cycle that is balanced for odd k or is unbalanced for even k; for k=n-1, the condition is that each even cycle in $\Sigma$ is positive and each odd cycle in $\Sigma$ is negative.
Tensors as module homomorphisms over group rings
Carmeliza Navasca,Michael Opperman,Timothy Penderghest,Christino Tamon
Mathematics , 2010,
Abstract: Braman [B08] described a construction where third-order tensors are exactly the set of linear transformations acting on the set of matrices with vectors as scalars. This extends the familiar notion that matrices form the set of all linear transformations over vectors with real-valued scalars. This result is based upon a circulant-based tensor multiplication due to Kilmer et al. [KMP08]. In this work, we generalize these observations further by viewing this construction in its natural framework of group rings.The circulant-based products arise as convolutions in these algebraic structures. Our generalization allows for any abelian group to replace the cyclic group, any commutative ring with identity to replace the field of real numbers, and an arbitrary order tensor to replace third-order tensors, provided the underlying ring is commutative.
Laplacian State Transfer in Coronas
Ethan Ackelsberg,Zachary Brehm,Ada Chan,Joshua Mundinger,Christino Tamon
Mathematics , 2015,
Abstract: We prove that the corona product of two graphs has no Laplacian perfect state transfer whenever the first graph has at least two vertices. This complements a result of Coutinho and Liu who showed that no tree of size greater than two has Laplacian perfect state transfer. In contrast, we prove that the corona product of two graphs exhibits Laplacian pretty good state transfer, under some mild conditions. This provides the first known examples of families of graphs with Laplacian pretty good state transfer. Our result extends of the work of Fan and Godsil on double stars to the Laplacian setting. Moreover, we also show that the corona product of any cocktail party graph with a single vertex graph has Laplacian pretty good state transfer, even though odd cocktail party graphs have no perfect state transfer.
Page 1 /59
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.