LU konference
Plašāk par semināru:
The program:
15:00 Renato Portugal, The Staggered Quantum Walk Model
15:45 Bruno Chagas, Applying QAOA to NP-complete Problems
16:15 short break
16:30 Abuzer Yakaryilmaz, Magic coins are useful for small-space
quantum machines
17:15 Franklin Marquezino, A reformulation of the quantum query model
without unitaries
Abstracts
The Staggered Quantum Walk Model
Renato Portugal
(in collaboration with R.A.M. Santos, T.D. Fernandes, and D.N. Gonçalves)
We give a precise definition of the staggered model and discuss natural extensions.Using this definition, we formally prove that any instance of Szegedy's model is equivalent to an instance of the staggered model. On the other hand, we show that there are instances of the staggered model that cannot be cast into Szegedy's framework. Our analysis also works when there are marked vertices. We show that Szegedy's spatial search algorithms can be converted into search algorithms in staggered QWs. We take advantage of the similarity of those models to define the hitting time in the staggered model and to describe a method to calculate the eigenvalues and eigenvectors of the evolution operator of staggered walks with marked vertices.
Magic coins are useful for small-space quantum machines
Abuzer Yakaryilmaz
(with A. C. Cem Say)
arXiv:1411.7647
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such "magic coins" give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language.
A reformulation of the quantum query model without unitaries
Franklin Marquezino
(with S.A. Grillo)
We present a reformulation of the Quantum Query Model (QQM) without considering the measurement step. Our new formulation is described by a set of vectors satisfying some properties, which we call a Block Set. Given an algorithm in QQM we prove that there is an equivalent algorithm in the Block Set Formulation (BSF). If we keep the same measurement step, then both formulations have the same Gram Matrix of the output states and the BSF allows us to describe it explicitly. Finally, we test the advantages of BSF by applying this approach to the construction of exact quantum algorithms.
Applying QAOA to NP-complete Problems
Bruno Chagas
(with R. Portugal)
We review QAOA, which is a quantum approximate optimization algorithm proposed by Farhi, Goldstone, and Gutmann (arXiv:/1412.6062), and we discuss applications to NP-complete problems.
15:00 Renato Portugal, The Staggered Quantum Walk Model
15:45 Bruno Chagas, Applying QAOA to NP-complete Problems
16:15 short break
16:30 Abuzer Yakaryilmaz, Magic coins are useful for small-space
quantum machines
17:15 Franklin Marquezino, A reformulation of the quantum query model
without unitaries
Abstracts
The Staggered Quantum Walk Model
Renato Portugal
(in collaboration with R.A.M. Santos, T.D. Fernandes, and D.N. Gonçalves)
We give a precise definition of the staggered model and discuss natural extensions.Using this definition, we formally prove that any instance of Szegedy's model is equivalent to an instance of the staggered model. On the other hand, we show that there are instances of the staggered model that cannot be cast into Szegedy's framework. Our analysis also works when there are marked vertices. We show that Szegedy's spatial search algorithms can be converted into search algorithms in staggered QWs. We take advantage of the similarity of those models to define the hitting time in the staggered model and to describe a method to calculate the eigenvalues and eigenvectors of the evolution operator of staggered walks with marked vertices.
Magic coins are useful for small-space quantum machines
Abuzer Yakaryilmaz
(with A. C. Cem Say)
arXiv:1411.7647
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such "magic coins" give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language.
A reformulation of the quantum query model without unitaries
Franklin Marquezino
(with S.A. Grillo)
We present a reformulation of the Quantum Query Model (QQM) without considering the measurement step. Our new formulation is described by a set of vectors satisfying some properties, which we call a Block Set. Given an algorithm in QQM we prove that there is an equivalent algorithm in the Block Set Formulation (BSF). If we keep the same measurement step, then both formulations have the same Gram Matrix of the output states and the BSF allows us to describe it explicitly. Finally, we test the advantages of BSF by applying this approach to the construction of exact quantum algorithms.
Applying QAOA to NP-complete Problems
Bruno Chagas
(with R. Portugal)
We review QAOA, which is a quantum approximate optimization algorithm proposed by Farhi, Goldstone, and Gutmann (arXiv:/1412.6062), and we discuss applications to NP-complete problems.