Postgraduate Thesis uoadl:1325627 292 Read counter

Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού

Library of the School of Science

Library of the School of Science

2016-11-29

2016

Μυρισιώτης Δημήτριος

Ζάχος Ευστάθιος Καθηγητής ΕΚΠΑ

Quantum Complexity, Relativized Worlds, and Oracle Separations

English

Quantum Complexity, Relativized Worlds, and Oracle Separations

The complexity class QMA, defined by Watrous, in 2000, is the quantum

analogue of MA, defined by Babai, in 1985, which, in turn, is a generalization

of the class NP. The class MA generalizes the class NP in the sense that the

verification procedure of the purported proof, put forth by the prover, is

carried out by a probabilistic machine, rather than a deterministic one—as

the definition of the class NP demands.

In 2014, Grilo, Kerenidis, and Sikora, proved that the quantum proof, in

the setting of QMA, may always be replaced by, an appropriately defined,

quantum subset state—without any conceptual loss. That is, QMA ⊆ SQMA.

Grilo et al., named their new class SQMA, for subset-state quantum MerlinArthur.

Thus, one could write that SQMA = QMA, as the inclusion SQMA ⊆

QMA holds trivially.

After this result, by Grilo, Kerenidis, and Sikora, Fefferman and Kimmel, in

2015, used this new characterization of QMA, and further proved that there

exists some quantum oracle A—similar to that Aaronson and Kuperberg

introduced, and used, in 2006, to show that QMAA

1 6⊆ QCMAA—which is

such that QMAA = SQMAA 6⊆ QCMAA. Here, QCMA is that version of QMA,

defined by Aharonov, and Naveh, in 2002, in which the purported proof

is purely-classical, that is, a bitstring, and QMA1 is the perfect completeness

version of QMA. In their separation, Fefferman and Kimmel introduced, and

used, an interesting template to obtain oracle separations against the class

QCMA.

Drawing upon this recent result, by Fefferman and Kimmel, we prove that

there exists some quantum oracle A, such that SQMAA

1 6⊆ QCMAA. We

note that the class SQMA1 is the perfect completeness version of the class

SQMA. In our proof, we used the template of Fefferman and Kimmel, a

modified version of their basic quantum oracle construction, as well as

the basic decision problem, that they themselves used for their separation.

Note that our result implies that of Fefferman and Kimmel, as the inclusion

xiii

SQMA1 ⊆ SQMA holds.

After we state and prove our result, we take a detour to explore a bit the

world of oracle separations, both in the classical and the quantum setting.

That is, we explore some results, and their underlying methods, about

classical and quantum oracles being employed for proving separations—

about classical, or quantum, complexity classes. Hence, we investigate

some gems pertaining to the, not few at all, nor uninteresting, privileged

relativized worlds.

Finally, we return, to the research setting, to approach the open question

of whether there exists some classical, or quantum, oracle A, such that

QMAA

1 6⊆ SQMAA

1

, or not. We record our efforts, and some of our first ideas,

thus far.

analogue of MA, defined by Babai, in 1985, which, in turn, is a generalization

of the class NP. The class MA generalizes the class NP in the sense that the

verification procedure of the purported proof, put forth by the prover, is

carried out by a probabilistic machine, rather than a deterministic one—as

the definition of the class NP demands.

In 2014, Grilo, Kerenidis, and Sikora, proved that the quantum proof, in

the setting of QMA, may always be replaced by, an appropriately defined,

quantum subset state—without any conceptual loss. That is, QMA ⊆ SQMA.

Grilo et al., named their new class SQMA, for subset-state quantum MerlinArthur.

Thus, one could write that SQMA = QMA, as the inclusion SQMA ⊆

QMA holds trivially.

After this result, by Grilo, Kerenidis, and Sikora, Fefferman and Kimmel, in

2015, used this new characterization of QMA, and further proved that there

exists some quantum oracle A—similar to that Aaronson and Kuperberg

introduced, and used, in 2006, to show that QMAA

1 6⊆ QCMAA—which is

such that QMAA = SQMAA 6⊆ QCMAA. Here, QCMA is that version of QMA,

defined by Aharonov, and Naveh, in 2002, in which the purported proof

is purely-classical, that is, a bitstring, and QMA1 is the perfect completeness

version of QMA. In their separation, Fefferman and Kimmel introduced, and

used, an interesting template to obtain oracle separations against the class

QCMA.

Drawing upon this recent result, by Fefferman and Kimmel, we prove that

there exists some quantum oracle A, such that SQMAA

1 6⊆ QCMAA. We

note that the class SQMA1 is the perfect completeness version of the class

SQMA. In our proof, we used the template of Fefferman and Kimmel, a

modified version of their basic quantum oracle construction, as well as

the basic decision problem, that they themselves used for their separation.

Note that our result implies that of Fefferman and Kimmel, as the inclusion

xiii

SQMA1 ⊆ SQMA holds.

After we state and prove our result, we take a detour to explore a bit the

world of oracle separations, both in the classical and the quantum setting.

That is, we explore some results, and their underlying methods, about

classical and quantum oracles being employed for proving separations—

about classical, or quantum, complexity classes. Hence, we investigate

some gems pertaining to the, not few at all, nor uninteresting, privileged

relativized worlds.

Finally, we return, to the research setting, to approach the open question

of whether there exists some classical, or quantum, oracle A, such that

QMAA

1 6⊆ SQMAA

1

, or not. We record our efforts, and some of our first ideas,

thus far.

Science

Mathematics

Quantum computational complexity theory, computational complexity theory, relativized worlds, oracle separations, oracles, QMA, QCMA, SQMA, SQMA1, quantum states, quantum subset-states, quantum proofs, veri- fication procedures, verification protocols, diagonalization, and query complexity

No

0

No

106

153