1,721,020 research outputs found
Generalizations Of The Quantum Search Algorithm
No full textQuantum computation has attracted a great deal of attention from the scientific community in recent years. By using the quantum mechanical phenomena of superposition and entanglement, a quantum computer can solve certain problems much faster than classical computers. Several quantum algorithms have been developed to demonstrate this quantum speedup. Two important examples are Shor’s algorithm for the factorization problem, and Grover’s algorithm for the search problem. Significant efforts are on to build a large scale quantum computer for implementing these quantum algorithms.
This thesis deals with Grover’s search algorithm, and presents its several generalizations that perform better in specific contexts. While writing the thesis, we have assumed the familiarity of readers with the basics of quantum mechanics and computer science. For a general introduction to the subject of quantum computation, see [1].
In Chapter 1, we formally define the search problem as well as present Grover’s search algorithm [2]. This algorithm, or more generally the quantum amplitude amplification algorithm [3, 4], drives a quantum system from a prepared initial state (s) to a desired target state (t). It uses O(α-1 = | (t−|s)| -1) iterations of the operator g = IsIt on |s), where { IsIt} are selective phase inversions selective phase inversions of the corresponding states. That is a quadratic speedup over the simple scheme of O(α−2) preparations of |s) and subsequent projective measurements. Several generalizations of Grover’s algorithm exist.
In Chapter 2, we study further generalizations of Grover’s algorithm. We analyse the iteration of the search operator S = DsI t on |s) where Ds is a more general transformation than Is, and I t is a selective phase rotation of |t) by angle . We find sufficient conditions for S to produce a successful quantum search algorithm.
In Chapter 3, we demonstrate that our general framework encapsulates several previous generalizations of Grover’s algorithm. For example, the phase-matching condition for the search operator requires the angles and and to be almost equal for a successful quantum search. In Kato’s algorithm, the search operator is where Ks consists of only single-qubit gates, which are easier to implement physically than multi-qubit gates. The spatial search algorithms consider the search operator where is a spatially local operator and provides implementation advantages over Is. The analysis of Chapter 2 provides a simpler understanding of all these special cases.
In Chapter 4, we present schemes to improve our general quantum search algorithm, by controlling the operators through an ancilla qubit. For the case of two dimensional spatial search problem, these schemes yield an algorithm with time complexity . Earlier algorithms solved this problem in time steps, and it was an open question to design a faster algorithm. The schemes can also be used to find, for a given unitary operator, an eigenstate corresponding to a specified eigenvalue.
In Chapter 5, we extend the analysis of Chapter 2 to general adiabatic quantum search. It starts with the ground state |s) of an initial Hamiltonian Hs and evolves adiabatically to the target state |t) that is the ground state of the final Hamiltonian The evolution uses a time dependent Hamiltonian HT that varies linearly with time . We show that the minimum excitation gap of HT is proportional to α. Also, the ground state of HT changes significantly only within a very narrow interval of width around the transition point, where the excitation gap has its minimum. This feature can be used to reach the target state (t) using adiabatic evolution for time
In Chapter 6, we present a robust quantum search algorithm that iterates the operator on |s) to successfully reach |t), whereas Grover’s algorithm fails if as per the phase-matching condition. The robust algorithm also works when is generalized to multiple target states. Moreover, the algorithm provides a new search Hamiltonian that is robust against certain systematic perturbations.
In Chapter 7, we look beyond the widely studied scenario of iterative quantum search algorithms, and present a recursive quantum search algorithm that succeeds with transformations {Vs,Vt} sufficiently close to {Is,It.} Grover’s algorithm generally fails if while the recursive algorithm is nearly optimal as long as , improving the error tolerance of the transformations.
The algorithms of Chapters 6-7 have applications in quantum error-correction, when systematic errors affect the transformations The algorithms are robust as long as the errors are small, reproducible and reversible. This type of errors arise often from imperfections in apparatus setup, and so the algorithms increase the flexibility in physical implementation of quantum search.
In Chapter 8, we present a fixed-point quantum search algorithm. Its state evolution monotonically converges towards |t), unlike Grover’s algorithm where the evolution passes through |t) under iterations of the operator . In q steps, our algorithm monotonically reduces the failure probability, i.e. the probability of not getting |t), from . That is asymptotically optimal for monotonic convergence. Though the fixed-point algorithm is of not much use for , it is useful when and each oracle query is highly expensive.
In Chapter 9, we conclude the thesis and present an overall outlook
Search On A Hypercubic Lattice Using Quantum Random Walk
No full textRandom walks describe diffusion processes, where movement at every time step is restricted only to neighbouring locations. Classical random walks are constructed using the non-relativistic Laplacian evolution operator and a coin toss instruction. In quantum theory, an alternative is to use the relativistic Dirac operator. That necessarily introduces an internal degree of freedom (chirality), which may be identified with the coin. The resultant walk spreads quadratically faster than the classical one, and can be applied to a variety of graph theoretical problems.
We study in detail the problem of spatial search, i.e. finding a marked site on a hypercubic lattice in d-dimensions. For d=1, the scaling behaviour of classical and quantum spatial search is the same due to the restriction on movement. On the other hand, the restriction on movement hardly matters for d ≥ 3, and scaling behaviour close to Grover’s optimal algorithm(which has no restriction on movement) can be achieved. d=2 is the borderline critical dimension, where infrared divergence in propagation leads to logarithmic slow down that can be minimised using clever chirality flips. In support of these analytic expectations, we present numerical simulation results for d=2 to d=9, using a lattice implementation of the Dirac operator inspired by staggered fermions. We optimise the parameters of the algorithm, and the simulation results demonstrate that the number of binary oracle calls required for d= 2 and d ≥ 3 spatial search problems are O(√NlogN) and O(√N) respectively. Moreover, with increasing d, the results approach the optimal behaviour of Grover’s algorithm(corresponding to mean field theory or d → ∞ limit). In particular, the d = 3 scaling behaviour is only about 25% higher than the optimal value
Quantum walks and spatial search on regular graph
No full textRandom walks and algorithms based upon them are used widely to explore large state spaces that arise while studying physical systems. In this thesis, we will discuss some quantum generalizations of such algorithms and study their
complexity. In the first part of this talk, we will discuss quantum search in the presence of spatial constraints. One of the main results in this thesis is an efficient search algorithm that can find multiple marked elements under spatial constraints imposed by regular graphs. Next, we will focus attention on two-dimensional square lattices. Building on our earlier algorithmic framework, we will show that optimal quantum search is possible on the square lattice by only mildly violating the locality constraints imposed by the graph. This investigation leads to a general prescription for dealing with the graph powering operation in the quantum walk framework. After this, we will move on to discussing mixing times of quantum walks. We will show that a fully decohered quantum walk mixes asymptotically at the same rate as its classical counterpart only if its degree is a constant function of its size. We will also present some numerical evidence showing that faster mixing is possible using a weakly decohered quantum walk, if the decoherence probability is tuned in relation to the spectral gap of the graph. Finally, we will also discuss the implementation of quantum walks and spatial search on IBM's quantum computing platform.EMR/2016/00631
An Efficient Quantum Algorithm and Circuit to Generate Eigenstates Of SU(2) and SU(3) Representations
Full text linkMany quantum computation algorithms, and processes like measurement based quantum computing, require the initial state of the quantum computer to be an eigenstate of a specific unitary operator. Here we study how quantum states that are eigenstates of finite dimensional irreducible representations of the special unitary (SU(d)) and the permutation (S_n) groups can be efficiently constructed in the computational basis formed by tensor products of the qudit states. The procedure is a unitary transform, which first uses Schur-Weyl duality to map every eigenstate to a unique Schur basis state, and then recursively uses the Clebsch - Gordan transform to rotate the Schur basis state to the computational basis. We explicitly provide an efficient quantum algorithm, and the corresponding quantum logic circuit, to generate any desired eigenstate of SU(2) and SU(3) irreducible representations in the computational basis
Efficient Quantum Algorithms for Linear Algebra Problems
No full textMany simulation problems can be expressed as time evolution under specific interactions,
from some simple initial state to a final state whose properties are to be investigated. In this
context, the Hamiltonian evolution problem has been extensively studied. Quantum simulations
can sum multiple evolutionary paths contributing to a quantum process in superposition at one
go, while classical simulations need to evaluate these paths one by one. Real physical systems are
governed by local Hamiltonians, i.e. where each component interacts only with a limited number
of its neighbours independent of the overall size of the system, which helps in parallelisation
of their simulations. The procedure is not simple, however. Although, in the 2n-dimensional
Hilbert space of n qubits, we can superpose 2n components evolving in parallel, we can measure
only n binary observables at the end. So the exponential gain of superposition is limited by
the restriction to extract only a small number of results at the end. This dichotomy means that
quantum algorithms will be advantageous only when the final observables are local in some
manner; no general prescription is available, and one has to look at the problems on a case by
case basis.
Early quantum evolution algorithms exploited locality of Hamiltonians for efficient use of
time and space resources during evolution [3, 4]. More recently, the error complexity of the
evolution has been reduced from power-law to logarithmic in the inverse error, using large step
discrete time algorithms [5–7]. After the Hamiltonian evolution, investigation of final state
properties requires expectation values of various observables to be measured. The problem of
how to do this efficiently has not been adequately addressed so far. Since quantum measurements
are probabilistic, determination of the expectation values needs multiple repetitions of the same
algorithm. Thereafter, importance sampling or phase estimation based results yield errors that
decrease as power-law in the number of repetitions [8, 9], e.g. Niter × *2 as per the central
limit theorem, and that is not efficient. What we want is a strategy that decreases the errors
exponentially with the number of repetitions, e.g. finding zeroes of a function by bisection
is efficient with Niter × log , and finding them by Newton’s method is super-efficient with
Niter × log log . While that may not be possible for generic observables, it can be achieved
for k-local observables that appear in evaluations of k-point Green’s functions for many-body
systems. We explicitly show how to do that.
The novel concept we introduce is a digital state representation of quantum states, which
maps non-unitary linear algebra operations to unitary operators. High precision calculations need
3 1.1. Scope of the Thesis
a digital representation instead of an analog one. Our digital representation for both the quantum
states and the operators maintains the expectation values of all physical observables. It combines
classical reversible logic with equally weighted linear superposition, and is essentially free of
the unitarity constraint for quantum states. This digital implementation can help in construction
of efficient quantum algorithms for many linear algebra problems
Quantum dynamics of weak measurements: Understanding the Born rule and applying weak error correction
No full textProjective measurement is used as a fundamental axiom in quantum mechanics, even though it is discontinuous and cannot predict which measured operator eigen state will be observed in which experimental run. The probabilistic Born rule gives it an ensemble interpretation, predicting proportions of various outcomes over many experimental runs. Understanding gradual weak measurements requires replacing this scenario with a dynamical evolution equation for the collapse of the quantum state in individual experimental runs. In this work, I revisit the quantum trajectory framework that models quantum measurement as a continuous nonlinear stochastic process. I describe the ensemble of quantum trajectories as noise fluctuations on top of geodesics that attract the quantum state towards the measured operator eigen states. In this effective theory framework for the ensemble of quantum trajectories, the measurement interaction is specific to each system-apparatus pair—a context necessary for understanding weak measurements. Also in this framework, the constraint to reproduce projective measurement as per the Born rule in the appropriate limit, requires that the magnitudes of the noise and the attraction are precisely related, in a manner reminiscent of the fluctuation dissipation relation. This relation implies that both the noise and the attraction have a common origin in the underlying measurement interaction between the system and the apparatus. I analyse the quantum trajectory ensemble for the scenarios of quantum diffusion and binary quantum jump, and show that the ensemble distribution is completely determined in terms of a single evolution parameter.
I test the trajectory ensemble distribution predicted by the quantum diffusion model against the experimental data for weak measurement of superconducting transmon qubits. There is a good fit between theory and experiment for different initial states and several weak measurement couplings. This test vindicates the continuous stochastic measurement framework for quantum state collapse, where the rate of collapse is a characteristic parameter for each system-apparatus pair and is not a universal constant. Furthermore, it implies that the environment can influence the measurement outcomes only via the apparatus and not directly. These are important clues in construction of a complete theory of quantum measurement.
The framework of weak measurements can also be used to construct quantum error correction protocols that protect a quantum state from external disturbances. Unlike projective measurements, one can extract only partial information about the error syndrome
from the encoded state using weak measurements. I construct a feedback protocol that probabilistically corrects the error based on the extracted information. Using numerical simulations of one-qubit error correction codes, I show that the error correction succeeds for a range of the weak measurement strength, where (a) the error rate is below the threshold beyond which multiple errors dominate, and (b) the error rate is less than the rate at which weak measurement extracts information. It is also obvious that error correction with too small a measurement strength should be avoided
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
