---
_id: '27160'
abstract:
- lang: eng
text: "We study the complexity of problems solvable in deterministic polynomial
time\r\nwith access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$\r\nand
$P^{QMA}$, respectively. The former allows one to classify problems more\r\nfinely
than the Polynomial-Time Hierarchy (PH), whereas the latter\r\ncharacterizes physically
motivated problems such as Approximate Simulation\r\n(APX-SIM) [Ambainis, CCC
2014]. In this area, a central role has been played by\r\nthe classes $P^{NP[\\log]}$
and $P^{QMA[\\log]}$, defined identically to $P^{NP}$\r\nand $P^{QMA}$, except
that only logarithmically many oracle queries are\r\nallowed. Here, [Gottlob,
FOCS 1993] showed that if the adaptive queries made by\r\na $P^{NP}$ machine have
a \"query graph\" which is a tree, then this computation\r\ncan be simulated in
$P^{NP[\\log]}$.\r\n In this work, we first show that for any verification class\r\n$C\\in\\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\\exp}\\}$,
any $P^C$ machine with a query\r\ngraph of \"separator number\" $s$ can be simulated
using deterministic time\r\n$\\exp(s\\log n)$ and $s\\log n$ queries to a $C$-oracle.
When $s\\in O(1)$ (which\r\nincludes the case of $O(1)$-treewidth, and thus also
of trees), this gives an\r\nupper bound of $P^{C[\\log]}$, and when $s\\in O(\\log^k(n))$,
this yields bound\r\n$QP^{C[\\log^{k+1}]}$ (QP meaning quasi-polynomial time).
We next show how to\r\ncombine Gottlob's \"admissible-weighting function\" framework
with the\r\n\"flag-qubit\" framework of [Watson, Bausch, Gharibian, 2020], obtaining
a\r\nunified approach for embedding $P^C$ computations directly into APX-SIM\r\ninstances
in a black-box fashion. Finally, we formalize a simple no-go\r\nstatement about
polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear\r\npolynomial $p$
specified via an arithmetic circuit, if one can \"weakly\r\ncompress\" $p$ so
that its optimal value requires $m$ bits to represent, then\r\n$P^{NP}$ can be
decided with only $m$ queries to an NP-oracle."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Dorian
full_name: Rudolph, Dorian
id: '57863'
last_name: Rudolph
citation:
ama: 'Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles.
In: 13th Innovations in Theoretical Computer Science (ITCS 2022). Vol 215.
; 2022:1-27. doi:10.4230/LIPIcs.ITCS.2022.75'
apa: Gharibian, S., & Rudolph, D. (2022). On polynomially many queries to NP
or QMA oracles. 13th Innovations in Theoretical Computer Science (ITCS 2022),
215(75), 1–27. https://doi.org/10.4230/LIPIcs.ITCS.2022.75
bibtex: '@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries
to NP or QMA oracles}, volume={215}, DOI={10.4230/LIPIcs.ITCS.2022.75},
number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS
2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27}
}'
chicago: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to
NP or QMA Oracles.” In 13th Innovations in Theoretical Computer Science (ITCS
2022), 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75.
ieee: 'S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,”
in 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022,
vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.'
mla: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or
QMA Oracles.” 13th Innovations in Theoretical Computer Science (ITCS 2022),
vol. 215, no. 75, 2022, pp. 1–27, doi:10.4230/LIPIcs.ITCS.2022.75.
short: 'S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science
(ITCS 2022), 2022, pp. 1–27.'
date_created: 2021-11-05T08:08:29Z
date_updated: 2026-04-30T14:11:00Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ITCS.2022.75
intvolume: ' 215'
issue: '75'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671
oa: '1'
page: 1-27
publication: 13th Innovations in Theoretical Computer Science (ITCS 2022)
status: public
title: On polynomially many queries to NP or QMA oracles
type: conference
user_id: '71541'
volume: 215
year: '2022'
...
---
_id: '29780'
abstract:
- lang: eng
text: A central tenet of theoretical cryptography is the study of the minimal
assumptions required to implement a given cryptographic primitive. One such primitive
is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO
2008], which is a classical functionality modeled after a non-interactive 1-out-of-2
oblivious transfer, and which is complete for one-time classical and quantum programs.
It is known that secure OTMs do not exist in the standard model in both the classical
and quantum settings. Here, we propose a scheme for using quantum information,
together with the assumption of stateless (i.e.,
reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite
programming-based quantum games framework of Gutoski and Watrous [STOC 2007],
we prove security for a malicious receiver making at most 0.114n
adaptive queries to the token (for n
the key size), in the quantum universal composability framework, but leave open
the question of security against a polynomial amount of queries. Compared to alternative
schemes derived from the literature on quantum money, our scheme is technologically
simple since it is of the "prepare-and-measure" type. We also give two impossibility
results showing certain assumptions in our scheme cannot be relaxed.
article_number: '429'
author:
- first_name: Anne
full_name: Broadbent, Anne
last_name: Broadbent
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Hong-Sheng
full_name: Zhou, Hong-Sheng
last_name: Zhou
citation:
ama: Broadbent A, Gharibian S, Zhou H-S. Towards Quantum One-Time Memories from
Stateless Hardware. Quantum. 2021;5. doi:10.22331/q-2021-04-08-429
apa: Broadbent, A., Gharibian, S., & Zhou, H.-S. (2021). Towards Quantum One-Time
Memories from Stateless Hardware. Quantum, 5, Article 429. https://doi.org/10.22331/q-2021-04-08-429
bibtex: '@article{Broadbent_Gharibian_Zhou_2021, title={Towards Quantum One-Time
Memories from Stateless Hardware}, volume={5}, DOI={10.22331/q-2021-04-08-429},
number={429}, journal={Quantum}, publisher={Verein zur Forderung des Open Access
Publizierens in den Quantenwissenschaften}, author={Broadbent, Anne and Gharibian,
Sevag and Zhou, Hong-Sheng}, year={2021} }'
chicago: Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum
One-Time Memories from Stateless Hardware.” Quantum 5 (2021). https://doi.org/10.22331/q-2021-04-08-429.
ieee: 'A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories
from Stateless Hardware,” Quantum, vol. 5, Art. no. 429, 2021, doi: 10.22331/q-2021-04-08-429.'
mla: Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.”
Quantum, vol. 5, 429, Verein zur Forderung des Open Access Publizierens
in den Quantenwissenschaften, 2021, doi:10.22331/q-2021-04-08-429.
short: A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).
date_created: 2022-02-08T10:59:00Z
date_updated: 2023-02-28T11:07:47Z
department:
- _id: '623'
- _id: '7'
doi: 10.22331/q-2021-04-08-429
intvolume: ' 5'
keyword:
- Physics and Astronomy (miscellaneous)
- Atomic and Molecular Physics
- and Optics
language:
- iso: eng
publication: Quantum
publication_identifier:
issn:
- 2521-327X
publication_status: published
publisher: Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
status: public
title: Towards Quantum One-Time Memories from Stateless Hardware
type: journal_article
user_id: '71541'
volume: 5
year: '2021'
...
---
_id: '13226'
abstract:
- lang: eng
text: "The canonical problem for the class Quantum Merlin-Arthur (QMA) is that of\r\nestimating
ground state energies of local Hamiltonians. Perhaps surprisingly,\r\n[Ambainis,
CCC 2014] showed that the related, but arguably more natural,\r\nproblem of simulating
local measurements on ground states of local Hamiltonians\r\n(APX-SIM) is likely
harder than QMA. Indeed, [Ambainis, CCC 2014] showed that\r\nAPX-SIM is P^QMA[log]-complete,
for P^QMA[log] the class of languages decidable\r\nby a P machine making a logarithmic
number of adaptive queries to a QMA oracle.\r\nIn this work, we show that APX-SIM
is P^QMA[log]-complete even when restricted\r\nto more physical Hamiltonians,
obtaining as intermediate steps a variety of\r\nrelated complexity-theoretic results.\r\n
\ We first give a sequence of results which together yield P^QMA[log]-hardness\r\nfor
APX-SIM on well-motivated Hamiltonians: (1) We show that for NP, StoqMA,\r\nand
QMA oracles, a logarithmic number of adaptive queries is equivalent to\r\npolynomially
many parallel queries. These equalities simplify the proofs of our\r\nsubsequent
results. (2) Next, we show that the hardness of APX-SIM is preserved\r\nunder
Hamiltonian simulations (a la [Cubitt, Montanaro, Piddock, 2017]). As a\r\nbyproduct,
we obtain a full complexity classification of APX-SIM, showing it is\r\ncomplete
for P, P^||NP, P^||StoqMA, or P^||QMA depending on the Hamiltonians\r\nemployed.
(3) Leveraging the above, we show that APX-SIM is P^QMA[log]-complete\r\nfor any
family of Hamiltonians which can efficiently simulate spatially sparse\r\nHamiltonians,
including physically motivated models such as the 2D Heisenberg\r\nmodel.\r\n
\ Our second focus considers 1D systems: We show that APX-SIM remains\r\nP^QMA[log]-complete
even for local Hamiltonians on a 1D line of 8-dimensional\r\nqudits. This uses
a number of ideas from above, along with replacing the \"query\r\nHamiltonian\"
of [Ambainis, CCC 2014] with a new \"sifter\" construction."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Stephen
full_name: Piddock, Stephen
last_name: Piddock
- first_name: Justin
full_name: Yirka, Justin
last_name: Yirka
citation:
ama: 'Gharibian S, Piddock S, Yirka J. Oracle complexity classes and local measurements
on physical Hamiltonians. In: Proceedings of the 37th Symposium on Theoretical
Aspects of Computer Science (STACS 2020). ; 2020:38.'
apa: Gharibian, S., Piddock, S., & Yirka, J. (2020). Oracle complexity classes
and local measurements on physical Hamiltonians. Proceedings of the 37th Symposium
on Theoretical Aspects of Computer Science (STACS 2020), 38.
bibtex: '@inproceedings{Gharibian_Piddock_Yirka_2020, title={Oracle complexity classes
and local measurements on physical Hamiltonians}, booktitle={Proceedings of the
37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, author={Gharibian,
Sevag and Piddock, Stephen and Yirka, Justin}, year={2020}, pages={38} }'
chicago: Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity
Classes and Local Measurements on Physical Hamiltonians.” In Proceedings of
the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020),
38, 2020.
ieee: S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local
measurements on physical Hamiltonians,” in Proceedings of the 37th Symposium
on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
mla: Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements
on Physical Hamiltonians.” Proceedings of the 37th Symposium on Theoretical
Aspects of Computer Science (STACS 2020), 2020, p. 38.
short: 'S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium
on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.'
date_created: 2019-09-16T07:41:31Z
date_updated: 2023-10-09T04:17:41Z
department:
- _id: '623'
- _id: '7'
external_id:
arxiv:
- '1909.05981'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.05981
oa: '1'
page: '38'
publication: Proceedings of the 37th Symposium on Theoretical Aspects of Computer
Science (STACS 2020)
publication_status: published
status: public
title: Oracle complexity classes and local measurements on physical Hamiltonians
type: conference
user_id: '71541'
year: '2020'
...
---
_id: '8426'
abstract:
- lang: eng
text: "A central tenet of theoretical cryptography is the study of the minimal assumptions
required to implement a given cryptographic primitive. One such primitive is the
one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008],
which is a classical functionality modeled after a non-interactive 1-out-of-2
oblivious transfer, and which is complete for one-time classical and quantum programs.
It is known that secure OTMs do not exist in the standard model in both the classical
and quantum settings. \r\n\r\nHere, we propose a scheme for using quantum information,
together with the assumption of stateless (i.e., reusable) hardware tokens, to
build statistically secure OTMs. Via the semidefinite programming-based quantum
games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious
receiver, against a linear number of adaptive queries to the token, in the quantum
universal composability framework. We prove stand-alone security against a malicious
sender, but leave open the question of composable security against a malicious
sender, as well as security against a malicious receiver making a polynomial number
of adaptive queries. Compared to alternative schemes derived from the literature
on quantum money, our scheme is technologically simple since it is of the \"prepare-and
measure\" type. We also show our scheme is \"tight\" according to two scenarios."
author:
- first_name: Anne
full_name: Broadbent, Anne
last_name: Broadbent
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Hong-Sheng
full_name: Zhou, Hong-Sheng
last_name: Zhou
citation:
ama: 'Broadbent A, Gharibian S, Zhou H-S. Towards Quantum One-Time Memories from
Stateless Hardware. In: Proceedings of the 15th Conference on the Theory of
Quantum Computation, Communication and Cryptography (TQC). Vol 158. Leibniz
International Proceedings in Informatics (LIPIcs); 2020:6:1-6:25.'
apa: Broadbent, A., Gharibian, S., & Zhou, H.-S. (2020). Towards Quantum One-Time
Memories from Stateless Hardware. Proceedings of the 15th Conference on the
Theory of Quantum Computation, Communication and Cryptography (TQC), 158,
6:1-6:25.
bibtex: '@inproceedings{Broadbent_Gharibian_Zhou_2020, title={Towards Quantum One-Time
Memories from Stateless Hardware}, volume={158}, booktitle={Proceedings of the
15th Conference on the Theory of Quantum Computation, Communication and Cryptography
(TQC)}, publisher={Leibniz International Proceedings in Informatics (LIPIcs)},
author={Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, year={2020},
pages={6:1-6:25} }'
chicago: Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum
One-Time Memories from Stateless Hardware.” In Proceedings of the 15th Conference
on the Theory of Quantum Computation, Communication and Cryptography (TQC),
158:6:1-6:25. Leibniz International Proceedings in Informatics (LIPIcs), 2020.
ieee: A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories
from Stateless Hardware,” in Proceedings of the 15th Conference on the Theory
of Quantum Computation, Communication and Cryptography (TQC), 2020, vol. 158,
p. 6:1-6:25.
mla: Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.”
Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication
and Cryptography (TQC), vol. 158, Leibniz International Proceedings in Informatics
(LIPIcs), 2020, p. 6:1-6:25.
short: 'A. Broadbent, S. Gharibian, H.-S. Zhou, in: Proceedings of the 15th Conference
on the Theory of Quantum Computation, Communication and Cryptography (TQC), Leibniz
International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.'
date_created: 2019-03-06T14:37:09Z
date_updated: 2023-02-28T10:59:55Z
department:
- _id: '623'
- _id: '7'
external_id:
arxiv:
- '1810.05226'
intvolume: ' 158'
language:
- iso: eng
main_file_link:
- url: https://arxiv.org/abs/1810.05226
page: 6:1-6:25
publication: Proceedings of the 15th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC)
publication_status: published
publisher: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Towards Quantum One-Time Memories from Stateless Hardware
type: conference
user_id: '71541'
volume: 158
year: '2020'
...
---
_id: '16927'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Marco
full_name: Aldi, Marco
last_name: Aldi
- first_name: Niel
full_name: de Beaudrap, Niel
last_name: de Beaudrap
- first_name: Seyran
full_name: Saeedi, Seyran
last_name: Saeedi
citation:
ama: Gharibian S, Aldi M, de Beaudrap N, Saeedi S. On efficiently solvable cases
of Quantum k-SAT. Communications in Mathematical Physics. Published online
2020.
apa: Gharibian, S., Aldi, M., de Beaudrap, N., & Saeedi, S. (2020). On efficiently
solvable cases of Quantum k-SAT. Communications in Mathematical Physics.
bibtex: '@article{Gharibian_Aldi_de Beaudrap_Saeedi_2020, title={On efficiently
solvable cases of Quantum k-SAT}, journal={Communications in Mathematical Physics},
author={Gharibian, Sevag and Aldi, Marco and de Beaudrap, Niel and Saeedi, Seyran},
year={2020} }'
chicago: Gharibian, Sevag, Marco Aldi, Niel de Beaudrap, and Seyran Saeedi. “On
Efficiently Solvable Cases of Quantum K-SAT.” Communications in Mathematical
Physics, 2020.
ieee: S. Gharibian, M. Aldi, N. de Beaudrap, and S. Saeedi, “On efficiently solvable
cases of Quantum k-SAT,” Communications in Mathematical Physics, 2020.
mla: Gharibian, Sevag, et al. “On Efficiently Solvable Cases of Quantum K-SAT.”
Communications in Mathematical Physics, 2020.
short: S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical
Physics (2020).
date_created: 2020-04-30T07:12:00Z
date_updated: 2023-02-28T11:05:17Z
department:
- _id: '623'
- _id: '7'
external_id:
arxiv:
- '1712.09617'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00220-020-03843-9
oa: '1'
publication: Communications in Mathematical Physics
publication_status: published
status: public
title: On efficiently solvable cases of Quantum k-SAT
type: journal_article
user_id: '71541'
year: '2020'
...
---
_id: '13297'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Ojas
full_name: Parekh, Ojas
last_name: Parekh
citation:
ama: 'Gharibian S, Parekh O. Almost Optimal Classical Approximation Algorithms for
a Quantum Generalization of Max-Cut. In: Proceedings of the 22nd International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX).
Vol 145. Leibniz International Proceedings in Informatics (LIPIcs). ; 2019:31:1-31:17.
doi:10.4230/LIPICS.APPROX-RANDOM.2019.31'
apa: Gharibian, S., & Parekh, O. (2019). Almost Optimal Classical Approximation
Algorithms for a Quantum Generalization of Max-Cut. Proceedings of the 22nd
International Workshop on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX), 145, 31:1-31:17. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31
bibtex: '@inproceedings{Gharibian_Parekh_2019, series={Leibniz International Proceedings
in Informatics (LIPIcs)}, title={Almost Optimal Classical Approximation Algorithms
for a Quantum Generalization of Max-Cut}, volume={145}, DOI={10.4230/LIPICS.APPROX-RANDOM.2019.31},
booktitle={Proceedings of the 22nd International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems (APPROX)}, author={Gharibian, Sevag and
Parekh, Ojas}, year={2019}, pages={31:1-31:17}, collection={Leibniz International
Proceedings in Informatics (LIPIcs)} }'
chicago: Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation
Algorithms for a Quantum Generalization of Max-Cut.” In Proceedings of the
22nd International Workshop on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX), 145:31:1-31:17. Leibniz International Proceedings in Informatics
(LIPIcs), 2019. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31.
ieee: 'S. Gharibian and O. Parekh, “Almost Optimal Classical Approximation Algorithms
for a Quantum Generalization of Max-Cut,” in Proceedings of the 22nd International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX),
2019, vol. 145, p. 31:1-31:17, doi: 10.4230/LIPICS.APPROX-RANDOM.2019.31.'
mla: Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation
Algorithms for a Quantum Generalization of Max-Cut.” Proceedings of the 22nd
International Workshop on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX), vol. 145, 2019, p. 31:1-31:17, doi:10.4230/LIPICS.APPROX-RANDOM.2019.31.
short: 'S. Gharibian, O. Parekh, in: Proceedings of the 22nd International Workshop
on Approximation Algorithms for Combinatorial Optimization Problems (APPROX),
2019, p. 31:1-31:17.'
date_created: 2019-09-19T08:33:29Z
date_updated: 2023-02-28T11:05:46Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPICS.APPROX-RANDOM.2019.31
intvolume: ' 145'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2019/11246/
oa: '1'
page: 31:1-31:17
publication: Proceedings of the 22nd International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems (APPROX)
publication_status: published
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Almost Optimal Classical Approximation Algorithms for a Quantum Generalization
of Max-Cut
type: conference
user_id: '71541'
volume: 145
year: '2019'
...
---
_id: '13558'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: 'Justin '
full_name: 'Yirka, Justin '
last_name: Yirka
citation:
ama: Gharibian S, Yirka J. The complexity of simulating local measurements on quantum
systems. Quantum. 2019;3:189. doi:10.22331/q-2019-09-30-189
apa: Gharibian, S., & Yirka, J. (2019). The complexity of simulating local measurements
on quantum systems. Quantum, 3, 189. https://doi.org/10.22331/q-2019-09-30-189
bibtex: '@article{Gharibian_Yirka_2019, title={The complexity of simulating local
measurements on quantum systems}, volume={3}, DOI={10.22331/q-2019-09-30-189},
journal={Quantum}, author={Gharibian, Sevag and Yirka, Justin }, year={2019},
pages={189} }'
chicago: 'Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local
Measurements on Quantum Systems.” Quantum 3 (2019): 189. https://doi.org/10.22331/q-2019-09-30-189.'
ieee: 'S. Gharibian and J. Yirka, “The complexity of simulating local measurements
on quantum systems,” Quantum, vol. 3, p. 189, 2019, doi: 10.22331/q-2019-09-30-189.'
mla: Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements
on Quantum Systems.” Quantum, vol. 3, 2019, p. 189, doi:10.22331/q-2019-09-30-189.
short: S. Gharibian, J. Yirka, Quantum 3 (2019) 189.
date_created: 2019-10-01T08:25:27Z
date_updated: 2023-02-28T11:05:35Z
department:
- _id: '623'
- _id: '7'
doi: 10.22331/q-2019-09-30-189
intvolume: ' 3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://quantum-journal.org/papers/q-2019-09-30-189/
oa: '1'
page: '189'
publication: Quantum
publication_status: published
status: public
title: The complexity of simulating local measurements on quantum systems
type: journal_article
user_id: '71541'
volume: 3
year: '2019'
...
---
_id: '8162'
abstract:
- lang: eng
text: 'The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are
canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively,
where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT
has been well-studied for special tractable cases, as well as from a parameterized
complexity perspective, much less is known in similar settings for k-QSAT. Here,
we study the open problem of computing satisfying assignments to k-QSAT instances
which have a "matching" or "dimer covering"; this is an NP problem whose decision
variant is trivial, but whose search complexity remains open. Our results fall
into three directions, all of which relate to the "matching" setting: (1) We give
a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most
two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a
certain non-trivial class, which allows us to obtain exponential speedups over
brute force methods in some cases by reducing the problem to solving for a single
root of a single univariate polynomial. (3) We conduct a structural graph theoretic
study of 3-QSAT interaction graphs which have a "matching". We remark that the
results of (2), in particular, introduce a number of new tools to the study of
Quantum SAT, including graph theoretic concepts such as transfer filtrations and
blow-ups from algebraic geometry; we hope these prove useful elsewhere.'
author:
- first_name: Marco
full_name: Aldi, Marco
last_name: Aldi
- first_name: Niel
full_name: de Beaudrap, Niel
last_name: de Beaudrap
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Seyran
full_name: Saeedi, Seyran
last_name: Saeedi
citation:
ama: 'Aldi M, de Beaudrap N, Gharibian S, Saeedi S. On Efficiently Solvable Cases
of Quantum k-SAT. In: Potapov I, Spirakis P, Worrell J, eds. 43rd International
Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Vol
117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl
- Leibniz-Zentrum fuer Informatik; 2018:38:1-38:16. doi:10.4230/LIPIcs.MFCS.2018.38'
apa: Aldi, M., de Beaudrap, N., Gharibian, S., & Saeedi, S. (2018). On Efficiently
Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, & J. Worrell
(Eds.), 43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018) (Vol. 117, p. 38:1-38:16). Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.38
bibtex: '@inproceedings{Aldi_de Beaudrap_Gharibian_Saeedi_2018, place={Dagstuhl,
Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)},
title={On Efficiently Solvable Cases of Quantum k-SAT}, volume={117}, DOI={10.4230/LIPIcs.MFCS.2018.38},
booktitle={43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
author={Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran},
editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={38:1-38:16},
collection={Leibniz International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On
Efficiently Solvable Cases of Quantum K-SAT.” In 43rd International Symposium
on Mathematical Foundations of Computer Science (MFCS 2018), edited by Igor
Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International
Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.38.'
ieee: 'M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable
Cases of Quantum k-SAT,” in 43rd International Symposium on Mathematical Foundations
of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, p. 38:1-38:16,
doi: 10.4230/LIPIcs.MFCS.2018.38.'
mla: Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” 43rd
International Symposium on Mathematical Foundations of Computer Science (MFCS
2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2018, p. 38:1-38:16, doi:10.4230/LIPIcs.MFCS.2018.38.
short: 'M. Aldi, N. de Beaudrap, S. Gharibian, S. Saeedi, in: I. Potapov, P. Spirakis,
J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of
Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
Dagstuhl, Germany, 2018, p. 38:1-38:16.'
conference:
location: Liverpool, UK
name: 43rd International Symposium on Mathematical Foundations of Computer Science
(MFCS 2018)
date_created: 2019-03-01T11:34:41Z
date_updated: 2023-02-28T11:01:16Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.MFCS.2018.38
editor:
- first_name: Igor
full_name: Potapov, Igor
last_name: Potapov
- first_name: Paul
full_name: Spirakis, Paul
last_name: Spirakis
- first_name: James
full_name: Worrell, James
last_name: Worrell
external_id:
arxiv:
- '1712.09617'
intvolume: ' 117'
keyword:
- search complexity
- local Hamiltonian
- Quantum SAT
- algebraic geometry
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2018/9620/
oa: '1'
page: 38:1-38:16
place: Dagstuhl, Germany
publication: 43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)
publication_identifier:
unknown:
- 978-3-95977-086-6
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: On Efficiently Solvable Cases of Quantum k-SAT
type: conference
user_id: '71541'
volume: 117
year: '2018'
...
---
_id: '8161'
abstract:
- lang: eng
text: The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing
separations in computational complexity theory (modulo standard conjectures such
as PH does not collapse). Here, we study whether two quantum generalizations of
PH can similarly prove separations in the quantum setting. The first generalization,
QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the
former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem.
For the latter, we place its third level, Q Sigma_3, into NEXP using the Ellipsoid
Method for efficiently solving semidefinite programs. These results yield two
implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled
proofs, a complexity class whose characterization has proven difficult. First,
if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to
make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting
Hierarchy (specifically, in P^{PP^{PP}}). Second, unless QMA(2)= Q Sigma_3 (i.e.,
alternating quantifiers do not help in the presence of "unentanglement"), QMA(2)
is strictly contained in NEXP.
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Miklos
full_name: Santha, Miklos
last_name: Santha
- first_name: Jamie
full_name: Sikora, Jamie
last_name: Sikora
- first_name: Aarthi
full_name: Sundaram, Aarthi
last_name: Sundaram
- first_name: Justin
full_name: Yirka, Justin
last_name: Yirka
citation:
ama: 'Gharibian S, Santha M, Sikora J, Sundaram A, Yirka J. Quantum Generalizations
of the Polynomial Hierarchy with Applications to QMA(2). In: Potapov I, Spirakis
P, Worrell J, eds. 43rd International Symposium on Mathematical Foundations
of Computer Science (MFCS 2018). Vol 117. Leibniz International Proceedings
in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:58:1-58:16.
doi:10.4230/LIPIcs.MFCS.2018.58'
apa: Gharibian, S., Santha, M., Sikora, J., Sundaram, A., & Yirka, J. (2018).
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).
In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium
on Mathematical Foundations of Computer Science (MFCS 2018) (Vol. 117, p.
58:1-58:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.58
bibtex: '@inproceedings{Gharibian_Santha_Sikora_Sundaram_Yirka_2018, place={Dagstuhl,
Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)},
title={Quantum Generalizations of the Polynomial Hierarchy with Applications to
QMA(2)}, volume={117}, DOI={10.4230/LIPIcs.MFCS.2018.58},
booktitle={43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
author={Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi
and Yirka, Justin}, editor={Potapov, Igor and Spirakis, Paul and Worrell, James},
year={2018}, pages={58:1-58:16}, collection={Leibniz International Proceedings
in Informatics (LIPIcs)} }'
chicago: 'Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin
Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications
to QMA(2).” In 43rd International Symposium on Mathematical Foundations of
Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James
Worrell, 117:58:1-58:16. Leibniz International Proceedings in Informatics (LIPIcs).
Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.58.'
ieee: 'S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum Generalizations
of the Polynomial Hierarchy with Applications to QMA(2),” in 43rd International
Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool,
UK, 2018, vol. 117, p. 58:1-58:16, doi: 10.4230/LIPIcs.MFCS.2018.58.'
mla: Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy
with Applications to QMA(2).” 43rd International Symposium on Mathematical
Foundations of Computer Science (MFCS 2018), edited by Igor Potapov et al.,
vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 58:1-58:16,
doi:10.4230/LIPIcs.MFCS.2018.58.
short: 'S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, in: I. Potapov,
P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations
of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
Dagstuhl, Germany, 2018, p. 58:1-58:16.'
conference:
location: Liverpool, UK
name: 43rd International Symposium on Mathematical Foundations of Computer Science
(MFCS 2018)
date_created: 2019-03-01T11:29:44Z
date_updated: 2023-02-28T11:01:03Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.MFCS.2018.58
editor:
- first_name: Igor
full_name: Potapov, Igor
last_name: Potapov
- first_name: Paul
full_name: Spirakis, Paul
last_name: Spirakis
- first_name: James
full_name: Worrell, James
last_name: Worrell
external_id:
arxiv:
- '1805.11139'
intvolume: ' 117'
keyword:
- Complexity Theory
- Quantum Computing
- Polynomial Hierarchy
- Semidefinite Programming
- QMA(2)
- Quantum Complexity
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=9640
oa: '1'
page: 58:1-58:16
place: Dagstuhl, Germany
publication: 43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)
publication_identifier:
unknown:
- 978-3-95977-086-6
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)
type: conference
user_id: '71541'
volume: 117
year: '2018'
...
---
_id: '8160'
abstract:
- lang: eng
text: An important task in quantum physics is the estimation of local quantities
for ground states of local Hamiltonians. Recently, Ambainis defined the complexity
class P^QMA[log], and motivated its study by showing that the physical task of
estimating the expectation value of a local observable against the ground state
of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the
study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness
result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We
show that simulating even a single qubit measurement on ground states of 5-local
Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We
formalize the complexity theoretic study of estimating two-point correlation functions
against ground states, and show that this task is similarly P^QMA[log]-complete.
P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally
by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung
to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP
from Kitaev and Watrous. A central theme of this work is the subtlety involved
in the study of oracle classes in which the oracle solves a promise problem. In
this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness
proof for estimating spectral gaps of local Hamiltonians. By introducing a "query
validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness
for estimating spectral gaps under polynomial-time Turing reductions.
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Justin
full_name: Yirka, Justin
last_name: Yirka
citation:
ama: 'Gharibian S, Yirka J. The Complexity of Simulating Local Measurements on Quantum
Systems. In: Wilde M, ed. 12th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2017). Vol 73. Leibniz International Proceedings
in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:2:1-2:17.
doi:10.4230/LIPIcs.TQC.2017.2'
apa: Gharibian, S., & Yirka, J. (2018). The Complexity of Simulating Local Measurements
on Quantum Systems. In M. Wilde (Ed.), 12th Conference on the Theory of Quantum
Computation, Communication and Cryptography (TQC 2017) (Vol. 73, p. 2:1-2:17).
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.TQC.2017.2
bibtex: '@inproceedings{Gharibian_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz
International Proceedings in Informatics (LIPIcs)}, title={The Complexity of Simulating
Local Measurements on Quantum Systems}, volume={73}, DOI={10.4230/LIPIcs.TQC.2017.2},
booktitle={12th Conference on the Theory of Quantum Computation, Communication
and Cryptography (TQC 2017)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer
Informatik}, author={Gharibian, Sevag and Yirka, Justin}, editor={Wilde, Mark},
year={2018}, pages={2:1-2:17}, collection={Leibniz International Proceedings in
Informatics (LIPIcs)} }'
chicago: 'Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local
Measurements on Quantum Systems.” In 12th Conference on the Theory of Quantum
Computation, Communication and Cryptography (TQC 2017), edited by Mark Wilde,
73:2:1-2:17. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl,
Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.TQC.2017.2.'
ieee: 'S. Gharibian and J. Yirka, “The Complexity of Simulating Local Measurements
on Quantum Systems,” in 12th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2017), Paris, France, 2018, vol. 73, p.
2:1-2:17, doi: 10.4230/LIPIcs.TQC.2017.2.'
mla: Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements
on Quantum Systems.” 12th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2017), edited by Mark Wilde, vol. 73,
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 2:1-2:17, doi:10.4230/LIPIcs.TQC.2017.2.
short: 'S. Gharibian, J. Yirka, in: M. Wilde (Ed.), 12th Conference on the Theory
of Quantum Computation, Communication and Cryptography (TQC 2017), Schloss Dagstuhl
- Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 2:1-2:17.'
conference:
location: Paris, France
name: 12th Conference on the Theory of Quantum Computation, Communication and Cryptography
(TQC 2017)
date_created: 2019-03-01T11:25:27Z
date_updated: 2023-02-28T11:00:48Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.TQC.2017.2
editor:
- first_name: Mark
full_name: Wilde, Mark
last_name: Wilde
external_id:
arxiv:
- '1606.05626'
intvolume: ' 73'
keyword:
- Complexity theory
- Quantum Merlin Arthur (QMA)
- local Hamiltonian
- local measurement
- spectral gap
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577
oa: '1'
page: 2:1-2:17
place: Dagstuhl, Germany
publication: 12th Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2017)
publication_identifier:
unknown:
- 978-3-95977-034-7
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: The Complexity of Simulating Local Measurements on Quantum Systems
type: conference
user_id: '71541'
volume: 73
year: '2018'
...
---
_id: '8167'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Jamie
full_name: Sikora, Jamie
last_name: Sikora
citation:
ama: Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. ACM
Transactions on Computation Theory (TOCT). 2018;10(2):8:1-8:28. doi:10.1145/3186587
apa: Gharibian, S., & Sikora, J. (2018). Ground State Connectivity of Local
Hamiltonians. ACM Transactions on Computation Theory (TOCT), 10(2),
8:1-8:28. https://doi.org/10.1145/3186587
bibtex: '@article{Gharibian_Sikora_2018, title={Ground State Connectivity of Local
Hamiltonians}, volume={10}, DOI={10.1145/3186587},
number={2}, journal={ACM Transactions on Computation Theory (TOCT)}, publisher={ACM},
author={Gharibian, Sevag and Sikora, Jamie}, year={2018}, pages={8:1-8:28} }'
chicago: 'Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local
Hamiltonians.” ACM Transactions on Computation Theory (TOCT) 10, no. 2
(2018): 8:1-8:28. https://doi.org/10.1145/3186587.'
ieee: 'S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,”
ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, p. 8:1-8:28,
2018, doi: 10.1145/3186587.'
mla: Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.”
ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, ACM, 2018,
p. 8:1-8:28, doi:10.1145/3186587.
short: S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10
(2018) 8:1-8:28.
date_created: 2019-03-01T11:49:31Z
date_updated: 2023-02-28T11:01:36Z
department:
- _id: '623'
- _id: '7'
doi: 10.1145/3186587
external_id:
arxiv:
- '1409.3182'
intvolume: ' 10'
issue: '2'
keyword:
- Local Hamiltonian
- ground state connectivity
- quantum Hamiltonian complexity
- reconfiguration problem
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1409.3182
oa: '1'
page: 8:1-8:28
publication: ACM Transactions on Computation Theory (TOCT)
publication_identifier:
issn:
- 1942-3454
publication_status: published
publisher: ACM
status: public
title: Ground State Connectivity of Local Hamiltonians
type: journal_article
user_id: '71541'
volume: 10
year: '2018'
...
---
_id: '8159'
abstract:
- lang: eng
text: The Boolean constraint satisfaction problem 3-SAT is arguably the canonical
NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial
time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically
motivated generalization of k-SAT to the quantum setting, defining the problem
"quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time
on a classical computer, in particular in deterministic time O(n^4), assuming
unit-cost arithmetic over a field extension of the rational numbers, where n is
number of variables. In this paper, we present an algorithm for quantum 2-SAT
which runs in linear time, i.e. deterministic time O(n+m) for n and m the number
of variables and clauses, respectively. Our approach exploits the transfer matrix
techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions
for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT
algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and
Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].
author:
- first_name: Niel
full_name: de Beaudrap, Niel
last_name: de Beaudrap
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
citation:
ama: 'de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In:
Raz R, ed. Proceedings of the 31st Conference on Computational Complexity (CCC
2016). Vol 50. Leibniz International Proceedings in Informatics (LIPIcs).
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:10.4230/LIPIcs.CCC.2016.27'
apa: de Beaudrap, N., & Gharibian, S. (2016). A Linear Time Algorithm for Quantum
2-SAT. In R. Raz (Ed.), Proceedings of the 31st Conference on Computational
Complexity (CCC 2016) (Vol. 50, p. 27:1-17:21). Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik. https://doi.org/10.4230/LIPIcs.CCC.2016.27
bibtex: '@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz
International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm
for Quantum 2-SAT}, volume={50}, DOI={10.4230/LIPIcs.CCC.2016.27},
booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC
2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de
Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21},
collection={Leibniz International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
2-SAT.” In Proceedings of the 31st Conference on Computational Complexity (CCC
2016), edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings
in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.27.'
ieee: 'N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,”
in Proceedings of the 31st Conference on Computational Complexity (CCC 2016),
Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: 10.4230/LIPIcs.CCC.2016.27.'
mla: de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
2-SAT.” Proceedings of the 31st Conference on Computational Complexity (CCC
2016), edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer
Informatik, 2016, p. 27:1-17:21, doi:10.4230/LIPIcs.CCC.2016.27.
short: 'N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st
Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.'
conference:
location: Tokyo, Japan
name: 31st Conference on Computational Complexity (CCC 2016)
date_created: 2019-03-01T11:19:54Z
date_updated: 2023-02-28T11:01:53Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.CCC.2016.27
editor:
- first_name: Ran
full_name: Raz, Ran
last_name: Raz
extern: '1'
external_id:
arxiv:
- '1508.07338'
intvolume: ' 50'
keyword:
- quantum 2-SAT
- transfer matrix
- strongly connected components
- limited backtracking
- local Hamiltonian
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2016/5836/
oa: '1'
page: 27:1-17:21
place: Dagstuhl, Germany
publication: Proceedings of the 31st Conference on Computational Complexity (CCC 2016)
publication_identifier:
isbn:
- 978-3-95977-008-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: A Linear Time Algorithm for Quantum 2-SAT
type: conference
user_id: '71541'
volume: 50
year: '2016'
...
---
_id: '8164'
abstract:
- lang: eng
text: The study of ground state energies of local Hamiltonians has played a fundamental
role in quantum complexity theory. In this paper, we take a new direction by introducing
the physically motivated notion of ``ground state connectivity'' of local Hamiltonians,
which captures problems in areas ranging from quantum stabilizer codes to quantum
memories. We show that determining how ``connected'' the ground space of a local
Hamiltonian is can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete
for an appropriately defined ``succinct'' version of the problem. As a result,
we obtain a natural QCMA-complete problem, a goal which has generally proven difficult
since the conception of QCMA over a decade ago. Our proofs rely on a new technical
tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution
must traverse under certain conditions. We show that this lemma is essentially
tight with respect to the length of the unitary evolution in question.
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Jamie
full_name: Sikora, Jamie
last_name: Sikora
citation:
ama: 'Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. In:
Halld{\’o}rsson MM, Iwama K, Kobayashi N, Speckmann B, eds. International Colloquium
on Automata, Languages, and Programming (ICALP 2015). Springer Berlin Heidelberg;
2015:617-628. doi:10.1007/978-3-662-47672-7_50'
apa: Gharibian, S., & Sikora, J. (2015). Ground State Connectivity of Local
Hamiltonians. In M. M. Halld{\’o}rsson, K. Iwama, N. Kobayashi, & B. Speckmann
(Eds.), International Colloquium on Automata, Languages, and Programming (ICALP
2015) (pp. 617–628). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_50
bibtex: '@inproceedings{Gharibian_Sikora_2015, place={Berlin, Heidelberg}, title={Ground
State Connectivity of Local Hamiltonians}, DOI={10.1007/978-3-662-47672-7_50},
booktitle={International Colloquium on Automata, Languages, and Programming (ICALP
2015)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Sikora,
Jamie}, editor={Halld{\’o}rsson, Magn{\’u}s M. and Iwama, Kazuo and Kobayashi,
Naoki and Speckmann, Bettina}, year={2015}, pages={617–628} }'
chicago: 'Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local
Hamiltonians.” In International Colloquium on Automata, Languages, and Programming
(ICALP 2015), edited by Magn{\’u}s M. Halld{\’o}rsson, Kazuo Iwama, Naoki
Kobayashi, and Bettina Speckmann, 617–28. Berlin, Heidelberg: Springer Berlin
Heidelberg, 2015. https://doi.org/10.1007/978-3-662-47672-7_50.'
ieee: 'S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,”
in International Colloquium on Automata, Languages, and Programming (ICALP
2015), Kyoto, Japan, 2015, pp. 617–628, doi: 10.1007/978-3-662-47672-7_50.'
mla: Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.”
International Colloquium on Automata, Languages, and Programming (ICALP 2015),
edited by Magn{\’u}s M. Halld{\’o}rsson et al., Springer Berlin Heidelberg, 2015,
pp. 617–28, doi:10.1007/978-3-662-47672-7_50.
short: 'S. Gharibian, J. Sikora, in: M.M. Halld{\’o}rsson, K. Iwama, N. Kobayashi,
B. Speckmann (Eds.), International Colloquium on Automata, Languages, and Programming
(ICALP 2015), Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 617–628.'
conference:
location: Kyoto, Japan
name: International Colloquium on Automata, Languages, and Programming (ICALP)
date_created: 2019-03-01T11:37:54Z
date_updated: 2023-02-28T11:02:07Z
department:
- _id: '623'
- _id: '7'
doi: 10.1007/978-3-662-47672-7_50
editor:
- first_name: Magn{\'u}s M.
full_name: Halld{\'o}rsson, Magn{\'u}s M.
last_name: Halld{\'o}rsson
- first_name: Kazuo
full_name: Iwama, Kazuo
last_name: Iwama
- first_name: Naoki
full_name: Kobayashi, Naoki
last_name: Kobayashi
- first_name: Bettina
full_name: Speckmann, Bettina
last_name: Speckmann
external_id:
arxiv:
- '1409.3182'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1409.3182
oa: '1'
page: 617-628
place: Berlin, Heidelberg
publication: International Colloquium on Automata, Languages, and Programming (ICALP
2015)
publication_identifier:
isbn:
- 978-3-662-47672-7
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: Ground State Connectivity of Local Hamiltonians
type: conference
user_id: '71541'
year: '2015'
...
---
_id: '8166'
abstract:
- lang: eng
text: 'Constraint satisfaction problems are a central pillar of modern computational
complexity theory. This survey provides an introduction to the rapidly growing
field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint
satisfaction problems. Over the past decade and a half, this field has witnessed
fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin
Theorem” to deep insights into the structure of 1D low-temperature quantum systems
via so-called area laws. Our aim here is to provide a computer science-oriented
introduction to the subject in order to help bridge the language barrier between
computer scientists and physicists in the field. As such, we include the following
in this survey: (1) The motivations and history of the field, (2) a glossary of
condensed matter physics terms explained in computer-science friendly language,
(3) overviews of central ideas from condensed matter physics, such as indistinguishable
particles, mean field theory, tensor networks, and area laws, and (4) brief expositions
of selected computer science-based results in the area. For example, as part of
the latter, we provide a novel information theoretic presentation of Bravyi’s
polynomial time algorithm for Quantum 2-SAT.'
article_type: review
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Yichen
full_name: Huang, Yichen
last_name: Huang
- first_name: Zeph
full_name: Landau, Zeph
last_name: Landau
- first_name: Seung
full_name: Woo Shin, Seung
last_name: Woo Shin
citation:
ama: Gharibian S, Huang Y, Landau Z, Woo Shin S. Quantum Hamiltonian Complexity.
Foundations and Trends® in Theoretical Computer Science. 2015;10(3):159-282.
doi:10.1561/0400000066
apa: Gharibian, S., Huang, Y., Landau, Z., & Woo Shin, S. (2015). Quantum Hamiltonian
Complexity. Foundations and Trends® in Theoretical Computer Science, 10(3),
159–282. https://doi.org/10.1561/0400000066
bibtex: '@article{Gharibian_Huang_Landau_Woo Shin_2015, title={Quantum Hamiltonian
Complexity}, volume={10}, DOI={10.1561/0400000066},
number={3}, journal={Foundations and Trends® in Theoretical Computer Science},
author={Gharibian, Sevag and Huang, Yichen and Landau, Zeph and Woo Shin, Seung},
year={2015}, pages={159–282} }'
chicago: 'Gharibian, Sevag, Yichen Huang, Zeph Landau, and Seung Woo Shin. “Quantum
Hamiltonian Complexity.” Foundations and Trends® in Theoretical Computer Science
10, no. 3 (2015): 159–282. https://doi.org/10.1561/0400000066.'
ieee: 'S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin, “Quantum Hamiltonian
Complexity,” Foundations and Trends® in Theoretical Computer Science, vol.
10, no. 3, pp. 159–282, 2015, doi: 10.1561/0400000066.'
mla: Gharibian, Sevag, et al. “Quantum Hamiltonian Complexity.” Foundations and
Trends® in Theoretical Computer Science, vol. 10, no. 3, 2015, pp. 159–282,
doi:10.1561/0400000066.
short: S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in
Theoretical Computer Science 10 (2015) 159–282.
date_created: 2019-03-01T11:45:40Z
date_updated: 2023-02-28T11:02:21Z
department:
- _id: '623'
- _id: '7'
doi: 10.1561/0400000066
extern: '1'
external_id:
arxiv:
- '1401.3916'
intvolume: ' 10'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1401.3916
oa: '1'
page: 159-282
publication: Foundations and Trends® in Theoretical Computer Science
publication_identifier:
issn:
- 1551-305X
publication_status: published
status: public
title: Quantum Hamiltonian Complexity
type: journal_article
user_id: '71541'
volume: 10
year: '2015'
...
---
_id: '8168'
abstract:
- lang: eng
text: "Tensor networks are a central tool in condensed matter physics. In this paper,
we initiate the study of tensor network non-zero testing (TNZ): Given a tensor
network T, does T represent a non-zero vector? We show that TNZ is not in the
Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among
other results) that the special cases of TNZ on non-negative and injective tensor
networks are in NP. Using this, we make a simple observation: The commuting variant
of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for
logarithmic k and constant D. This reveals the first class of quantum Hamiltonians
whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant
D, and (3) for arbitrary interaction graphs.\r\n"
article_type: original
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Zeph
full_name: Landau, Zeph
last_name: Landau
- first_name: Seung
full_name: Woo Shin, Seung
last_name: Woo Shin
- first_name: Guoming
full_name: Wang, Guoming
last_name: Wang
citation:
ama: Gharibian S, Landau Z, Woo Shin S, Wang G. Tensor network non-zero testing.
Quantum Information & Computation. 2015;15(9{\ & }10):885-899.
apa: Gharibian, S., Landau, Z., Woo Shin, S., & Wang, G. (2015). Tensor network
non-zero testing. Quantum Information & Computation, 15(9{\
& }10), 885–899.
bibtex: '@article{Gharibian_Landau_Woo Shin_Wang_2015, title={Tensor network non-zero
testing}, volume={15}, number={9{\ & }10}, journal={Quantum Information &
Computation}, author={Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and
Wang, Guoming}, year={2015}, pages={885–899} }'
chicago: 'Gharibian, Sevag, Zeph Landau, Seung Woo Shin, and Guoming Wang. “Tensor
Network Non-Zero Testing.” Quantum Information & Computation 15, no.
9{\ & }10 (2015): 885–99.'
ieee: S. Gharibian, Z. Landau, S. Woo Shin, and G. Wang, “Tensor network non-zero
testing,” Quantum Information & Computation, vol. 15, no. 9{\ &
}10, pp. 885–899, 2015.
mla: Gharibian, Sevag, et al. “Tensor Network Non-Zero Testing.” Quantum Information
& Computation, vol. 15, no. 9{\ & }10, 2015, pp. 885–99.
short: S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information &
Computation 15 (2015) 885–899.
date_created: 2019-03-01T11:53:08Z
date_updated: 2023-02-28T11:02:35Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1406.5279'
intvolume: ' 15'
issue: 9{\&}10
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1406.5279
oa: '1'
page: 885-899
publication: Quantum Information & Computation
publication_status: published
status: public
title: Tensor network non-zero testing
type: journal_article
user_id: '71541'
volume: 15
year: '2015'
...
---
_id: '8171'
abstract:
- lang: eng
text: "The polynomial hierarchy plays a central role in classical complexity theory.
Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate
its study. We show that\r\nnot only are there natural complete problems for the
second level of this quantum hierarchy, but that these problems are in fact hard
to approximate. Using the same techniques, we\r\nalso obtain hardness of approximation
for the class QCMA. Our approach is based on the\r\nuse of dispersers, and is
inspired by the classical results of Umans regarding hardness of approximation
for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].\r\nThe
problems for which we prove hardness of approximation for include, among others,
a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local
Hamiltonian\r\nproblem with hybrid classical-quantum ground states."
article_type: original
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Julia
full_name: Kempe, Julia
last_name: Kempe
citation:
ama: Gharibian S, Kempe J. Hardness of approximation for quantum problems. Quantum
Information & Computation. 2014;14(5-6):517-540.
apa: Gharibian, S., & Kempe, J. (2014). Hardness of approximation for quantum
problems. Quantum Information & Computation, 14(5–6), 517–540.
bibtex: '@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum
problems}, volume={14}, number={5–6}, journal={Quantum Information & Computation},
author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }'
chicago: 'Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum
Problems.” Quantum Information & Computation 14, no. 5–6 (2014): 517–40.'
ieee: S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,”
Quantum Information & Computation, vol. 14, no. 5–6, pp. 517–540, 2014.
mla: Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.”
Quantum Information & Computation, vol. 14, no. 5–6, 2014, pp. 517–40.
short: S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540.
date_created: 2019-03-01T11:56:55Z
date_updated: 2023-02-28T11:02:47Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1209.1055'
intvolume: ' 14'
issue: 5-6
keyword:
- Hardness of approximation
- polynomial time hierarchy
- succinct set cover
- quantum complexity
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1209.1055
oa: '1'
page: 517-540
publication: Quantum Information & Computation
publication_status: published
status: public
title: Hardness of approximation for quantum problems
type: journal_article
user_id: '71541'
volume: 14
year: '2014'
...
---
_id: '8172'
abstract:
- lang: eng
text: We show how to efficiently simulate continuous-time quantum query algorithms
that run in time T in a manner that preserves the query complexity (within a polylogarithmic
factor) while also incurring a small overhead cost in the total number of gates
between queries. By small overhead, we mean T within a factor that is polylogarithmic
in terms of T and a cost measure that reflects the cost of computing the driving
Hamiltonian. This permits any continuous-time quantum algorithm based on an efficiently
computable driving Hamiltonian to be converted into a gate-efficient algorithm
with similar running time.
article_type: original
author:
- first_name: Dominic
full_name: W. Berry, Dominic
last_name: W. Berry
- first_name: Richard
full_name: Cleve, Richard
last_name: Cleve
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
citation:
ama: W. Berry D, Cleve R, Gharibian S. Gate-efficient discrete simulations of continuous-time
quantum query algorithms. Quantum Information & Computation. 2014;14(1-2):1-30.
apa: W. Berry, D., Cleve, R., & Gharibian, S. (2014). Gate-efficient discrete
simulations of continuous-time quantum query algorithms. Quantum Information
& Computation, 14(1–2), 1–30.
bibtex: '@article{W. Berry_Cleve_Gharibian_2014, title={Gate-efficient discrete
simulations of continuous-time quantum query algorithms}, volume={14}, number={1–2},
journal={Quantum Information & Computation}, author={W. Berry, Dominic and
Cleve, Richard and Gharibian, Sevag}, year={2014}, pages={1–30} }'
chicago: 'W. Berry, Dominic, Richard Cleve, and Sevag Gharibian. “Gate-Efficient
Discrete Simulations of Continuous-Time Quantum Query Algorithms.” Quantum
Information & Computation 14, no. 1–2 (2014): 1–30.'
ieee: D. W. Berry, R. Cleve, and S. Gharibian, “Gate-efficient discrete simulations
of continuous-time quantum query algorithms,” Quantum Information & Computation,
vol. 14, no. 1–2, pp. 1–30, 2014.
mla: W. Berry, Dominic, et al. “Gate-Efficient Discrete Simulations of Continuous-Time
Quantum Query Algorithms.” Quantum Information & Computation, vol.
14, no. 1–2, 2014, pp. 1–30.
short: D. W. Berry, R. Cleve, S. Gharibian, Quantum Information & Computation
14 (2014) 1–30.
date_created: 2019-03-01T11:59:24Z
date_updated: 2023-02-28T11:02:58Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1211.4637'
intvolume: ' 14'
issue: 1-2
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1211.4637
oa: '1'
page: 1-30
publication: Quantum Information & Computation
publication_status: published
status: public
title: Gate-efficient discrete simulations of continuous-time quantum query algorithms
type: journal_article
user_id: '71541'
volume: 14
year: '2014'
...
---
_id: '8425'
abstract:
- lang: eng
text: "This thesis studies three topics in quantum computation and information:
The approximability of quantum problems, quantum proof systems, and non-classical
correlations in quantum systems. \r\n\r\nIn the first area, we demonstrate a polynomial-time
(classical) approximation algorithm for dense instances of the canonical QMA-complete
quantum constraint satisfaction problem, the local Hamiltonian problem. In the
opposite direction, we next introduce a quantum generalization of the polynomial-time
hierarchy, and define problems which we prove are not only complete for the second
level of this hierarchy, but are in fact hard to approximate. \r\n\r\nIn the second
area, we study variants of the interesting and stubbornly open question of whether
a quantum proof system with multiple unentangled quantum provers is equal in expressive
power to a proof system with a single quantum prover. Our results concern classes
such as BellQMA(poly), and include a novel proof of perfect parallel repetition
for SepQMA(m) based on cone programming duality. \r\n\r\nIn the third area, we
study non-classical quantum correlations beyond entanglement, often dubbed \"non-classicality\".
Among our results are two novel schemes for quantifying non-classicality: The
first proposes the new paradigm of exploiting local unitary operations to study
non-classical correlations, and the second introduces a protocol through which
non-classical correlations in a starting system can be \"activated\" into distillable
entanglement with an ancilla system. \r\n\r\nAn introduction to all required linear
algebra and quantum mechanics is included."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
citation:
ama: Gharibian S. Approximation, Proof Systems, and Correlations in a Quantum
World.; 2013.
apa: Gharibian, S. (2013). Approximation, Proof Systems, and Correlations in
a Quantum World.
bibtex: '@book{Gharibian_2013, title={Approximation, Proof Systems, and Correlations
in a Quantum World}, author={Gharibian, Sevag}, year={2013} }'
chicago: Gharibian, Sevag. Approximation, Proof Systems, and Correlations in
a Quantum World, 2013.
ieee: S. Gharibian, Approximation, Proof Systems, and Correlations in a Quantum
World. 2013.
mla: Gharibian, Sevag. Approximation, Proof Systems, and Correlations in a Quantum
World. 2013.
short: S. Gharibian, Approximation, Proof Systems, and Correlations in a Quantum
World, 2013.
date_created: 2019-03-06T14:35:06Z
date_updated: 2023-02-28T11:00:15Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1301.2632'
language:
- iso: eng
main_file_link:
- open_access: '1'
oa: '1'
page: '240'
related_material:
link:
- relation: confirmation
url: https://arxiv.org/abs/1301.2632
status: public
title: Approximation, Proof Systems, and Correlations in a Quantum World
type: dissertation
user_id: '71541'
year: '2013'
...
---
_id: '8173'
abstract:
- lang: eng
text: We study three variants of multi-prover quantum Merlin-Arthur proof systems.
We first show that the class of problems that can be efficiently verified using
polynomially many quantum proofs, each of logarithmic-size, is exactly MQA (also
known as QCMA), the class of problems which can be efficiently verified via a
classical proof and a quantum verifier. We then study the class BellQMA(poly),
characterized by a verifier who first applies unentangled, nonadaptive measurements
to each of the polynomially many proofs, followed by an arbitrary but efficient
quantum verification circuit on the resulting measurement outcomes. We show that
if the number of outcomes per nonadaptive measurement is a polynomially-bounded
function, then the expressive power of the proof system is exactly QMA. Finally,
we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's
measurement operator corresponding to outcome "accept" is a fully separable operator
across the m quantum proofs. Using cone programming duality, we give an alternate
proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows
a perfect parallel repetition theorem for SepQMA(m) for any m.
article_type: original
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Jamie
full_name: Sikora, Jamie
last_name: Sikora
- first_name: Sarvagya
full_name: Upadhyay, Sarvagya
last_name: Upadhyay
citation:
ama: Gharibian S, Sikora J, Upadhyay S. QMA variants with polynomially many provers.
Quantum Information & Computation. 2013;13(1-2):135-157.
apa: Gharibian, S., Sikora, J., & Upadhyay, S. (2013). QMA variants with polynomially
many provers. Quantum Information & Computation, 13(1–2), 135–157.
bibtex: '@article{Gharibian_Sikora_Upadhyay_2013, title={QMA variants with polynomially
many provers}, volume={13}, number={1–2}, journal={Quantum Information & Computation},
author={Gharibian, Sevag and Sikora, Jamie and Upadhyay, Sarvagya}, year={2013},
pages={135–157} }'
chicago: 'Gharibian, Sevag, Jamie Sikora, and Sarvagya Upadhyay. “QMA Variants with
Polynomially Many Provers.” Quantum Information & Computation 13, no.
1–2 (2013): 135–57.'
ieee: S. Gharibian, J. Sikora, and S. Upadhyay, “QMA variants with polynomially
many provers,” Quantum Information & Computation, vol. 13, no. 1–2,
pp. 135–157, 2013.
mla: Gharibian, Sevag, et al. “QMA Variants with Polynomially Many Provers.” Quantum
Information & Computation, vol. 13, no. 1–2, 2013, pp. 135–57.
short: S. Gharibian, J. Sikora, S. Upadhyay, Quantum Information & Computation
13 (2013) 135–157.
date_created: 2019-03-01T12:00:39Z
date_updated: 2023-02-28T11:03:13Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1108.0617'
intvolume: ' 13'
issue: 1-2
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1108.0617
oa: '1'
page: 135-157
publication: Quantum Information & Computation
publication_status: published
status: public
title: QMA variants with polynomially many provers
type: journal_article
user_id: '71541'
volume: 13
year: '2013'
...
---
_id: '8169'
abstract:
- lang: eng
text: The polynomial hierarchy plays a central role in classical complexity theory.
Here, we define a quantum generalization of the polynomial hierarchy, and initiate
its study. We show that not only are there natural complete problems for the second
level of this quantum hierarchy, but that these problems are in fact hard to approximate.
Our work thus yields the first known hardness of approximation results for a quantum
complexity class. Using these techniques, we also obtain hardness of approximation
for the class QCMA. Our approach is based on the use of dispersers, and is inspired
by the classical results of Umans regarding hardness of approximation for the
second level of the classical polynomial hierarchy (Umans 1999). We close by showing
that a variant of the local Hamiltonian problem with hybrid classical-quantum
ground states is complete for the second level of our quantum hierarchy.
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Julia
full_name: Kempe, Julia
last_name: Kempe
citation:
ama: 'Gharibian S, Kempe J. Hardness of Approximation for Quantum Problems. In:
Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. International Colloquium
on Automata, Languages, and Programming (ICALP 2012). Springer Berlin Heidelberg;
2012:387-398. doi:10.1007/978-3-642-31594-7_33'
apa: Gharibian, S., & Kempe, J. (2012). Hardness of Approximation for Quantum
Problems. In A. Czumaj, K. Mehlhorn, A. Pitts, & R. Wattenhofer (Eds.), International
Colloquium on Automata, Languages, and Programming (ICALP 2012) (pp. 387–398).
Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-31594-7_33
bibtex: '@inproceedings{Gharibian_Kempe_2012, place={Berlin, Heidelberg}, title={Hardness
of Approximation for Quantum Problems}, DOI={10.1007/978-3-642-31594-7_33},
booktitle={International Colloquium on Automata, Languages, and Programming (ICALP
2012)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Kempe,
Julia}, editor={Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer,
Roger}, year={2012}, pages={387–398} }'
chicago: 'Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum
Problems.” In International Colloquium on Automata, Languages, and Programming
(ICALP 2012), edited by Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger
Wattenhofer, 387–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. https://doi.org/10.1007/978-3-642-31594-7_33.'
ieee: 'S. Gharibian and J. Kempe, “Hardness of Approximation for Quantum Problems,”
in International Colloquium on Automata, Languages, and Programming (ICALP
2012), Warwick, UK, 2012, pp. 387–398, doi: 10.1007/978-3-642-31594-7_33.'
mla: Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.”
International Colloquium on Automata, Languages, and Programming (ICALP 2012),
edited by Artur Czumaj et al., Springer Berlin Heidelberg, 2012, pp. 387–98, doi:10.1007/978-3-642-31594-7_33.
short: 'S. Gharibian, J. Kempe, in: A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer
(Eds.), International Colloquium on Automata, Languages, and Programming (ICALP
2012), Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 387–398.'
conference:
location: Warwick, UK
name: International Colloquium on Automata, Languages, and Programming (ICALP)
date_created: 2019-03-01T11:55:18Z
date_updated: 2023-02-28T11:03:26Z
department:
- _id: '623'
- _id: '7'
doi: 10.1007/978-3-642-31594-7_33
editor:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Kurt
full_name: Mehlhorn, Kurt
last_name: Mehlhorn
- first_name: Andrew
full_name: Pitts, Andrew
last_name: Pitts
- first_name: Roger
full_name: Wattenhofer, Roger
last_name: Wattenhofer
extern: '1'
external_id:
arxiv:
- '1209.1055'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1209.1055
oa: '1'
page: 387-398
place: Berlin, Heidelberg
publication: International Colloquium on Automata, Languages, and Programming (ICALP
2012)
publication_identifier:
isbn:
- 978-3-642-31594-7
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: Hardness of Approximation for Quantum Problems
type: conference
user_id: '71541'
year: '2012'
...