Search results for "quantum computer"

Improved constructions of quantum automata

2008

We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.

Spatial Search on Grids with Minimum Memory

2015

We study quantum algorithms for spatial search on finite dimensional grids. Patel et al. and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is $O(\sqrt{N\log N})$ and the success probability is $O(1/\log N)$, where $N$ is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.

2014

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9 th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O’Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a “highly influential” …

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

2017

We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…

Quantum Random Walks – New Method for Designing Quantum Algorithms

2008

Quantum walks are quantum counterparts of random walks. In the last 5 years, they have become one of main methods of designing quantum algorithms. Quantum walk based algorithms include element distinctness, spatial search, quantum speedup of Markov chains, evaluation of Boolean formulas and search on "glued trees" graph. In this talk, I will describe the quantum walk method for designing search algorithms and show several of its applications.

Quantum computing thanks to Bianchi groups

2018

It has been shown that the concept of a magic state (in universal quantum computing: uqc) and that of a minimal informationally complete positive operator valued measure: MIC-POVMs (in quantum measurements) are in good agreement when such a magic state is selected in the set of non-stabilizer eigenstates of permutation gates with the Pauli group acting on it [1]. Further work observed that most found low-dimensional MICs may be built from subgroups of the modular group PS L(2, Z) [2] and that this can be understood from the picture of the trefoil knot and related 3-manifolds [3]. Here one concentrates on Bianchi groups PS L(2, O10) (with O10 the integer ring over the imaginary quadratic fie…

Quantum superpositions of clockwise and counterclockwise supercurrent states in the dynamics of a rf-SQUID exposed to a quantized electromagnetic fie…

2002

The dynamical behavior of a superconducting quantum interference device (a rf-SQUID) irradiated by a single mode quantized electromagnetic field is theoretically investigated. Treating the SQUID as a flux qubit, we analyze the dynamics of the combined system within the low lying energy Hilbert subspace both in the asymmetric and in the symmetric SQUID potential configurations. We show that the temporal evolution of the system is dominated by an oscillatory behavior characterized by more than one, generally speaking, incommensurable Rabi frequencies whose expressions are explicitly given. We find that the external parameters may fixed in such a way to realize a control on the dynamical repla…

Molecular spins for quantum computation

2019

Spins in solids or in molecules possess discrete energy levels, and the associated quantum states can be tuned and coherently manipulated by means of external electromagnetic fields. Spins therefore provide one of the simplest platforms to encode a quantum bit (qubit), the elementary unit of future quantum computers. Performing any useful computation demands much more than realizing a robust qubit—one also needs a large number of qubits and a reliable manner with which to integrate them into a complex circuitry that can store and process information and implement quantum algorithms. This ‘scalability’ is arguably one of the challenges for which a chemistry-based bottom-up approach is best-s…

Ideas in the History of Nano/Miniaturization and (Quantum) Simulators: Feynman, Education and Research Reorientation in Translational Science

2015

Cultural history of nanominiaturization, computing, quantum computing and simulating is necessary to comprehend human character and place it in the whole of living beings. Ideas in the history of physics by Feynman, etc. are valued by the questions that generate. A series of questions, answers and hypothesis introduces the nature of the history of nanominiaturization, providing facts. Nanotechnology adds a third dimension to the periodic table of the elements. Thinking about computers was useful. It must do with learning computers possibilities and physics potential. Provisional conclusions follow. (1) Nature (space–time) is not classical but discrete; quantization is a different kind of ma…