0000000000516192
AUTHOR
Alexander Rivosh
showing 17 related works from this author
Exceptional Configurations of Quantum Walks with Grover’s Coin
2016
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation -- Grover's diffusion transformation -- has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by [AR08].
Quantum Walks with Multiple or Moving Marked Locations
2008
We study some properties of quantum walks on the plane. First, we discuss the behavior of quantum walks when moving marked locations are introduced. Second, we present an exceptional case, when quantum walk fails to find any of the marked locations.
Nonlocal Quantum XOR Games for Large Number of Players
2010
Nonlocal games are used to display differences between classical and quantum world In this paper, we study nonlocal games with a large number of players We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player, a subclass of nonlocal games We illustrate those methods on the example of the N-player game (due to Ardehali [Ard92]) that provides the maximum quantum-over-classical advantage.
Quantum walks on two-dimensional grids with multiple marked locations
2015
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied.We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations.In this paper, we prove two results showing the importance of how the marked locations ar…
Grover’s Search with Faults on Some Marked Elements
2016
Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size N using $$O\sqrt{N}$$ queries. It provides a significant speed-up over any classical algorithm [2]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [1, 4]. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in $$O\sqrt{N}$$ queries.
On symmetric nonlocal games
2013
Abstract Nonlocal games are used to display differences between the classical and quantum world. In this paper, we study symmetric XOR games, which form an important subset of nonlocal games. We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player. We illustrate those methods with two examples. One example is an N -player game (due to Ardehali (1992) [3] ) that provides the maximum quantum-over-classical advantage. The second example comes from generalization of CHSH game by letting the referee to choose arbitrary symmetric distribution of players’ inputs.
Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations
2016
The running time of a quantum walk search algorithm depends on both the structure of the search space graph and the configuration of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present tw…
Evaluation of T7 and lambda phage display systems for survey of autoantibody profiles in cancer patients.
2008
In the current study we attempted to evaluate the suitability of T7 Select 10-3b and lambdaKM8 phage display systems for the identification of antigens eliciting B cell responses in cancer patients and the production of phage-displayed antigen microarrays that could be exploited for the monitoring of autoantibody profiles. Members of 15 tumour-associated antigen (TAA) families were cloned into both phage display vectors and the TAA mini-libraries were immunoscreened with 22 melanoma patients' sera resulting in the detection of reactivity against members of 5 antigen families in both systems, yet with variable sensitivity. T7 phage display system showed greater sensitivity for the detection …
Grover’s Algorithm with Errors
2013
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].
Grover’s Search with Faults on Some Marked Elements
2018
Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze…
Melanoma epidemiology, prognosis and trends in Latvia
2012
Background Melanoma incidence and mortality rates are increasing worldwide within the white population. Clinical and histological factors have been usually used for the prognosis and assessment of the risk for melanoma. Objectives The aim of the study was to describe the clinical and histopathological features of the cutaneous melanoma (CM) in the Latvian population, to test the association between melanoma features and patient survival, and to assess the time trends for melanoma incidence. Methods We undertook a descriptive, retrospective analysis of archive data of 984 melanoma patients treated at the largest oncological hospital of Latvia, Riga East University Hospital Latvian Oncology C…
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
2013
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).
Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory
2023
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory.
Coins Make Quantum Walks Faster
2004
We show how to search N items arranged on a $\sqrt{N}\times\sqrt{N}$ grid in time $O(\sqrt N \log N)$, using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom, since it has been shown recently that such a continuous time walk needs time $\Omega(N)$ to perform the same task. Our result furthermore improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of $O(\sqrt{N})$ and give several extensions of quantum walk search algorithms for general graphs. T…
Quantum versus Classical Online Streaming Algorithms with Advice
2018
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.
Exceptional configurations of quantum walks with Grover's coin
2015
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation - Grover's diffusion transformation - has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by Ambainis and Rivosh [AR08]
Search by quantum walks on two-dimensional grid without amplitude amplification
2011
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh (quant-ph/0402107) takes O(\sqrt{N log N}) steps and finds a marked location with probability O(1/log N) for grid of size \sqrt{N} * \sqrt{N}. This probability is small, thus amplitude amplification is needed to achieve \Theta(1) success probability. The amplitude amplification adds an additional O(\sqrt{log N}) factor to the number of steps, making it O(\sqrt{N} log N). In this paper, we show that despite a small probability to find a marked location, the probability to be within an O(\sqrt{N}) neighbourhood (at an O(\sqrt[4]{N}) distance) of the marked location is \Theta(1). This all…