New developments in quantum algorithms

Andris Ambainis

doi:10.1007/978-3-642-15155-2_1

New developments in quantum algorithms

Andris Ambainis^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

10 Citations (Scopus)

Abstract

In this talk, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(√N). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N^2.37...) where N is the size of the system, the quantum algorithm runs in time O(log^c N). It outputs a quantum state describing the solution of the system.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings
Pages	1-11
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-15155-2_1
Publication status	Published - 2010
Event	35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010 - Brno, Czech Republic Duration: 23 Aug 2010 → 27 Aug 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6281 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010
Country/Territory	Czech Republic
City	Brno
Period	23/08/10 → 27/08/10

Access to Document

10.1007/978-3-642-15155-2_1

Cite this

Ambainis, A. (2010). New developments in quantum algorithms. In Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings (pp. 1-11). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6281 LNCS). https://doi.org/10.1007/978-3-642-15155-2_1

@inproceedings{c9226c82299c4a98883aaafd6219495a,

title = "New developments in quantum algorithms",

abstract = "In this talk, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(√N). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N2.37...) where N is the size of the system, the quantum algorithm runs in time O(logc N). It outputs a quantum state describing the solution of the system.",

author = "Andris Ambainis",

year = "2010",

doi = "10.1007/978-3-642-15155-2\_1",

language = "English",

isbn = "364215154X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "1--11",

booktitle = "Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings",

note = "35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010 ; Conference date: 23-08-2010 Through 27-08-2010",

}

Ambainis, A 2010, New developments in quantum algorithms. in Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6281 LNCS, pp. 1-11, 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, Brno, Czech Republic, 23/08/10. https://doi.org/10.1007/978-3-642-15155-2_1

New developments in quantum algorithms. / Ambainis, Andris.
Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings. 2010. p. 1-11 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6281 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - New developments in quantum algorithms

AU - Ambainis, Andris

PY - 2010

Y1 - 2010

N2 - In this talk, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(√N). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N2.37...) where N is the size of the system, the quantum algorithm runs in time O(logc N). It outputs a quantum state describing the solution of the system.

AB - In this talk, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(√N). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N2.37...) where N is the size of the system, the quantum algorithm runs in time O(logc N). It outputs a quantum state describing the solution of the system.

UR - https://www.scopus.com/pages/publications/78349259673

U2 - 10.1007/978-3-642-15155-2_1

DO - 10.1007/978-3-642-15155-2_1

M3 - Conference paper

AN - SCOPUS:78349259673

SN - 364215154X

SN - 9783642151545

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 11

BT - Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings

T2 - 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010

Y2 - 23 August 2010 through 27 August 2010

ER -

New developments in quantum algorithms

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this