---
_id: '57866'
abstract:
- lang: eng
text: "The theory of Total Function NP (TFNP) and its subclasses says that, even
if\r\none is promised an efficiently verifiable proof exists for a problem, finding\r\nthis
proof can be intractable. Despite the success of the theory at showing\r\nintractability
of problems such as computing Brouwer fixed points and Nash\r\nequilibria, subclasses
of TFNP remain arguably few and far between. In this\r\nwork, we define two new
subclasses of TFNP borne of the study of complex\r\npolynomial systems: Multi-homogeneous
Systems (MHS) and Sparse Fundamental\r\nTheorem of Algebra (SFTA). The first of
these is based on B\\'ezout's theorem\r\nfrom algebraic geometry, marking the
first TFNP subclass based on an algebraic\r\ngeometric principle. At the heart
of our study is the computational problem\r\nknown as Quantum SAT (QSAT) with
a System of Distinct Representatives (SDR),\r\nfirst studied by [Laumann, L\\\"auchli,
Moessner, Scardicchio, and Sondhi 2010].\r\nAmong other results, we show that
QSAT with SDR is MHS-complete, thus giving\r\nnot only the first link between
quantum complexity theory and TFNP, but also\r\nthe first TFNP problem whose classical
variant (SAT with SDR) is easy but whose\r\nquantum variant is hard. We also show
how to embed the roots of a sparse,\r\nhigh-degree, univariate polynomial into
QSAT with SDR, obtaining that SFTA is\r\ncontained in a zero-error version of
MHS. We conjecture this construction also\r\nworks in the low-error setting, which
would imply SFTA is contained in MHS."
author:
- first_name: Marco
full_name: Aldi, Marco
last_name: Aldi
- 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: 'Aldi M, Gharibian S, Rudolph D. An unholy trinity: TFNP, polynomial systems,
and the quantum satisfiability problem. In: 17th Innovations in Theoretical
Computer Science Conference (ITCS 2026). Vol 362. ; 2026:7:1-7:24.'
apa: 'Aldi, M., Gharibian, S., & Rudolph, D. (2026). An unholy trinity: TFNP,
polynomial systems, and the quantum satisfiability problem. 17th Innovations
in Theoretical Computer Science Conference (ITCS 2026), 362, 7:1-7:24.'
bibtex: '@inproceedings{Aldi_Gharibian_Rudolph_2026, title={An unholy trinity: TFNP,
polynomial systems, and the quantum satisfiability problem}, volume={362}, booktitle={17th
Innovations in Theoretical Computer Science Conference (ITCS 2026)}, author={Aldi,
Marco and Gharibian, Sevag and Rudolph, Dorian}, year={2026}, pages={7:1-7:24}
}'
chicago: 'Aldi, Marco, Sevag Gharibian, and Dorian Rudolph. “An Unholy Trinity:
TFNP, Polynomial Systems, and the Quantum Satisfiability Problem.” In 17th
Innovations in Theoretical Computer Science Conference (ITCS 2026), 362:7:1-7:24,
2026.'
ieee: 'M. Aldi, S. Gharibian, and D. Rudolph, “An unholy trinity: TFNP, polynomial
systems, and the quantum satisfiability problem,” in 17th Innovations in Theoretical
Computer Science Conference (ITCS 2026), 2026, vol. 362, p. 7:1-7:24.'
mla: 'Aldi, Marco, et al. “An Unholy Trinity: TFNP, Polynomial Systems, and the
Quantum Satisfiability Problem.” 17th Innovations in Theoretical Computer
Science Conference (ITCS 2026), vol. 362, 2026, p. 7:1-7:24.'
short: 'M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer
Science Conference (ITCS 2026), 2026, p. 7:1-7:24.'
date_created: 2024-12-30T13:55:27Z
date_updated: 2026-01-23T07:53:03Z
external_id:
arxiv:
- '2412.19623'
intvolume: ' 362'
language:
- iso: eng
page: 7:1-7:24
publication: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
publication_status: published
status: public
title: 'An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability
problem'
type: conference
user_id: '71541'
volume: 362
year: '2026'
...
---
_id: '50272'
abstract:
- lang: eng
text: "Despite the fundamental role the Quantum Satisfiability (QSAT) problem has\r\nplayed
in quantum complexity theory, a central question remains open: At which\r\nlocal
dimension does the complexity of QSAT transition from \"easy\" to \"hard\"?\r\nHere,
we study QSAT with each constraint acting on a $k$-dimensional and\r\n$l$-dimensional
qudit pair, denoted $(k,l)$-QSAT. Our first main result shows\r\nthat, surprisingly,
QSAT on qubits can remain $\\mathsf{QMA}_1$-hard, in that\r\n$(2,5)$-QSAT is $\\mathsf{QMA}_1$-complete.
In contrast, $2$-SAT on qubits is\r\nwell-known to be poly-time solvable [Bravyi,
2006]. Our second main result\r\nproves that $(3,d)$-QSAT on the 1D line with
$d\\in O(1)$ is also\r\n$\\mathsf{QMA}_1$-hard. Finally, we initiate the study
of 1D $(2,d)$-QSAT by\r\ngiving a frustration-free 1D Hamiltonian with a unique,
entangled ground state.\r\n Our first result uses a direct embedding, combining
a novel clock\r\nconstruction with the 2D circuit-to-Hamiltonian construction
of [Gosset, Nagaj,\r\n2013]. Of note is a new simplified and analytic proof for
the latter (as\r\nopposed to a partially numeric proof in [GN13]). This exploits
Unitary Labelled\r\nGraphs [Bausch, Cubitt, Ozols, 2017] together with a new \"Nullspace
Connection\r\nLemma\", allowing us to break low energy analyses into small patches
of\r\nprojectors, and to improve the soundness analysis of [GN13] from\r\n$\\Omega(1/T^6)$
to $\\Omega(1/T^2)$, for $T$ the number of gates. Our second\r\nresult goes via
black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on\r\n$d'$-dimensional
qudits, we show how to embed it into an effective null-space\r\nof a 1D $(3,d)$-QSAT
instance, for $d\\in O(1)$. Our approach may be viewed as a\r\nweaker notion of
\"simulation\" (\\`a la [Bravyi, Hastings 2017], [Cubitt,\r\nMontanaro, Piddock
2018]). As far as we are aware, this gives the first\r\n\"black-box simulation\"-based
$\\mathsf{QMA}_1$-hardness result, i.e. for\r\nfrustration-free Hamiltonians."
author:
- first_name: Dorian
full_name: Rudolph, Dorian
last_name: Rudolph
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Daniel
full_name: Nagaj, Daniel
last_name: Nagaj
citation:
ama: 'Rudolph D, Gharibian S, Nagaj D. Quantum 2-SAT on low dimensional systems
is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation. In:
16th Innovations in Theoretical Computer Science (ITCS). Vol 325. ; 2025:1-24.
doi:10.4230/LIPIcs.ITCS.2025.85'
apa: Rudolph, D., Gharibian, S., & Nagaj, D. (2025). Quantum 2-SAT on low dimensional
systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation.
16th Innovations in Theoretical Computer Science (ITCS), 325(85),
1–24. https://doi.org/10.4230/LIPIcs.ITCS.2025.85
bibtex: '@inproceedings{Rudolph_Gharibian_Nagaj_2025, title={Quantum 2-SAT on low
dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box
simulation}, volume={325}, DOI={10.4230/LIPIcs.ITCS.2025.85},
number={85}, booktitle={16th Innovations in Theoretical Computer Science (ITCS)},
author={Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}, year={2025},
pages={1–24} }'
chicago: Rudolph, Dorian, Sevag Gharibian, and Daniel Nagaj. “Quantum 2-SAT on Low
Dimensional Systems Is $\mathsf{QMA}_1$-Complete: Direct Embeddings and Black-Box
Simulation.” In 16th Innovations in Theoretical Computer Science (ITCS),
325:1–24, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.85.
ieee: 'D. Rudolph, S. Gharibian, and D. Nagaj, “Quantum 2-SAT on low dimensional
systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation,”
in 16th Innovations in Theoretical Computer Science (ITCS), 2025, vol.
325, no. 85, pp. 1–24, doi: 10.4230/LIPIcs.ITCS.2025.85.'
mla: Rudolph, Dorian, et al. “Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_1$-Complete:
Direct Embeddings and Black-Box Simulation.” 16th Innovations in Theoretical
Computer Science (ITCS), vol. 325, no. 85, 2025, pp. 1–24, doi:10.4230/LIPIcs.ITCS.2025.85.
short: 'D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical
Computer Science (ITCS), 2025, pp. 1–24.'
date_created: 2024-01-07T20:09:13Z
date_updated: 2025-02-11T07:21:23Z
doi: 10.4230/LIPIcs.ITCS.2025.85
external_id:
arxiv:
- '2401.02368'
intvolume: ' 325'
issue: '85'
language:
- iso: eng
page: 1-24
publication: 16th Innovations in Theoretical Computer Science (ITCS)
publication_status: published
status: public
title: 'Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct
embeddings and black-box simulation'
type: conference
user_id: '71541'
volume: 325
year: '2025'
...
---
_id: '60432'
abstract:
- lang: eng
text: "The Quantum k-SAT problem is the quantum generalization of the k-SAT problem.\r\nIt
is the problem whether a given local Hamiltonian is frustration-free.\r\nFrustration-free
means that the ground state of the k-local Hamiltonian\r\nminimizes the energy
of every local interaction term simultaneously. This is a\r\ncentral question
in quantum physics and a canonical QMA_1-complete problem. The\r\nQuantum k-SAT
problem is not as well studied as the classical k-SAT problem in\r\nterms of special
tractable cases, approximation algorithms and parameterized\r\ncomplexity. In
this paper, we will give a graph-theoretic study of the Quantum\r\nk-SAT problem
with the structures core and radius. These hypergraph structures\r\nare important
to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT\r\ninstance in
polynomial time if the derived hypergraph has a core of size n-m+a,\r\nwhere a
is a constant, and the radius is at most logarithmic. If it exists, we\r\ncan
find a core of size n-m+a with the best possible radius in polynomial time,\r\nwhereas
finding a general minimum core with minimal radius is NP-hard."
author:
- first_name: Simon-Luca
full_name: Kremer, Simon-Luca
last_name: Kremer
- first_name: Dorian
full_name: Rudolph, Dorian
id: '57863'
last_name: Rudolph
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
citation:
ama: Kremer S-L, Rudolph D, Gharibian S. Quantum k-SAT Related Hypergraph Problems.
arXiv:250617066. Published online 2025.
apa: Kremer, S.-L., Rudolph, D., & Gharibian, S. (2025). Quantum k-SAT Related
Hypergraph Problems. In arXiv:2506.17066.
bibtex: '@article{Kremer_Rudolph_Gharibian_2025, title={Quantum k-SAT Related Hypergraph
Problems}, journal={arXiv:2506.17066}, author={Kremer, Simon-Luca and Rudolph,
Dorian and Gharibian, Sevag}, year={2025} }'
chicago: Kremer, Simon-Luca, Dorian Rudolph, and Sevag Gharibian. “Quantum K-SAT
Related Hypergraph Problems.” ArXiv:2506.17066, 2025.
ieee: S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph
Problems,” arXiv:2506.17066. 2025.
mla: Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” ArXiv:2506.17066,
2025.
short: S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
date_created: 2025-06-27T06:56:35Z
date_updated: 2025-06-27T06:57:03Z
external_id:
arxiv:
- '2506.17066'
language:
- iso: eng
publication: arXiv:2506.17066
status: public
title: Quantum k-SAT Related Hypergraph Problems
type: preprint
user_id: '71541'
year: '2025'
...
---
_id: '55037'
abstract:
- lang: eng
text: "Estimating ground state energies of many-body Hamiltonians is a central task\r\nin
many areas of quantum physics. In this work, we give quantum algorithms\r\nwhich,
given any $k$-body Hamiltonian $H$, compute an estimate for the ground\r\nstate
energy and prepare a quantum state achieving said energy, respectively.\r\nSpecifically,
for any $\\varepsilon>0$, our algorithms return, with high\r\nprobability, an
estimate of the ground state energy of $H$ within additive\r\nerror $\\varepsilon
M$, or a quantum state with the corresponding energy. Here,\r\n$M$ is the total
strength of all interaction terms, which in general is\r\nextensive in the system
size. Our approach makes no assumptions about the\r\ngeometry or spatial locality
of interaction terms of the input Hamiltonian and\r\nthus handles even long-range
or all-to-all interactions, such as in quantum\r\nchemistry, where lattice-based
techniques break down. In this fully general\r\nsetting, the runtime of our algorithms
scales as $2^{cn/2}$ for $c<1$, yielding\r\nthe first quantum algorithms for low-energy
estimation breaking the natural\r\nbound based on Grover search. The core of our
approach is remarkably simple,\r\nand relies on showing that any $k$-body Hamiltonian
has a low-energy subspace\r\nof exponential dimension."
author:
- first_name: Harry
full_name: Buhrman, Harry
last_name: Buhrman
- 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: François Le
full_name: Gall, François Le
last_name: Gall
- first_name: Norbert
full_name: Schuch, Norbert
last_name: Schuch
- first_name: Suguru
full_name: Tamaki, Suguru
last_name: Tamaki
citation:
ama: Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. Beating Grover
search for low-energy estimation and state preparation. Physical Review Letters.
2025;135:030601. doi:10.1103/29qw-bssx
apa: Buhrman, H., Gharibian, S., Landau, Z., Gall, F. L., Schuch, N., & Tamaki,
S. (2025). Beating Grover search for low-energy estimation and state preparation.
Physical Review Letters, 135, 030601. https://doi.org/10.1103/29qw-bssx
bibtex: '@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki_2025, title={Beating
Grover search for low-energy estimation and state preparation}, volume={135},
DOI={10.1103/29qw-bssx}, journal={Physical
Review Letters}, author={Buhrman, Harry and Gharibian, Sevag and Landau, Zeph
and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}, year={2025}, pages={030601}
}'
chicago: 'Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert
Schuch, and Suguru Tamaki. “Beating Grover Search for Low-Energy Estimation and
State Preparation.” Physical Review Letters 135 (2025): 030601. https://doi.org/10.1103/29qw-bssx.'
ieee: 'H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki,
“Beating Grover search for low-energy estimation and state preparation,” Physical
Review Letters, vol. 135, p. 030601, 2025, doi: 10.1103/29qw-bssx.'
mla: Buhrman, Harry, et al. “Beating Grover Search for Low-Energy Estimation and
State Preparation.” Physical Review Letters, vol. 135, 2025, p. 030601,
doi:10.1103/29qw-bssx.
short: H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, Physical
Review Letters 135 (2025) 030601.
date_created: 2024-07-04T09:02:42Z
date_updated: 2025-07-16T10:25:43Z
doi: 10.1103/29qw-bssx
external_id:
arxiv:
- '2407.03073'
intvolume: ' 135'
language:
- iso: eng
page: '030601'
publication: Physical Review Letters
publication_status: published
status: public
title: Beating Grover search for low-energy estimation and state preparation
type: journal_article
user_id: '71541'
volume: 135
year: '2025'
...
---
_id: '61922'
abstract:
- lang: eng
text: "We present an extremely simple polynomial-space exponential-time\r\n$(1-\\varepsilon)$-approximation
algorithm for MAX-k-SAT that is (slightly)\r\nfaster than the previous known polynomial-space
$(1-\\varepsilon)$-approximation\r\nalgorithms by Hirsch (Discrete Applied Mathematics,
2003) and Escoffier,\r\nPaschos and Tourniaire (Theoretical Computer Science,
2014). Our algorithm\r\nrepeatedly samples an assignment uniformly at random until
finding an\r\nassignment that satisfies a large enough fraction of clauses. Surprisingly,
we\r\ncan show the efficiency of this simpler approach by proving that in any\r\ninstance
of MAX-k-SAT (or more generally any instance of MAXCSP), an\r\nexponential number
of assignments satisfy a fraction of clauses close to the\r\noptimal value."
author:
- first_name: Harry
full_name: Buhrman, Harry
last_name: Buhrman
- 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: François Le
full_name: Gall, François Le
last_name: Gall
- first_name: Norbert
full_name: Schuch, Norbert
last_name: Schuch
- first_name: Suguru
full_name: Tamaki, Suguru
last_name: Tamaki
citation:
ama: Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. A Simpler Exponential-Time
Approximation Algorithm for MAX-k-SAT. SIAM Symposium on Simplicity in Algorithms
(SOSA).
apa: Buhrman, H., Gharibian, S., Landau, Z., Gall, F. L., Schuch, N., & Tamaki,
S. (n.d.). A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. In
SIAM Symposium on Simplicity in Algorithms (SOSA).
bibtex: '@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki, title={A Simpler
Exponential-Time Approximation Algorithm for MAX-k-SAT}, journal={SIAM Symposium
on Simplicity in Algorithms (SOSA)}, author={Buhrman, Harry and Gharibian, Sevag
and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}
}'
chicago: Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert
Schuch, and Suguru Tamaki. “A Simpler Exponential-Time Approximation Algorithm
for MAX-k-SAT.” SIAM Symposium on Simplicity in Algorithms (SOSA), n.d.
ieee: H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki,
“A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT,” SIAM Symposium
on Simplicity in Algorithms (SOSA). .
mla: Buhrman, Harry, et al. “A Simpler Exponential-Time Approximation Algorithm
for MAX-k-SAT.” SIAM Symposium on Simplicity in Algorithms (SOSA).
short: H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, SIAM
Symposium on Simplicity in Algorithms (SOSA) (n.d.).
date_created: 2025-10-22T09:33:22Z
date_updated: 2026-01-07T14:26:56Z
department:
- _id: '7'
- _id: '623'
external_id:
arxiv:
- '2510.18164'
language:
- iso: eng
publication: SIAM Symposium on Simplicity in Algorithms (SOSA)
publication_status: inpress
status: public
title: A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
type: preprint
user_id: '71541'
year: '2025'
...
---
_id: '48544'
abstract:
- lang: eng
text: 'When it comes to NP, its natural definition, its wide applicability across
scientific disciplines, and its timeless relevance, the writing is on the wall:
There can be only one. Quantum NP, on the other hand, is clearly the apple that
fell far from the tree of NP. Two decades since the first definitions of quantum
NP started rolling in, quantum complexity theorists face a stark reality: There''s
QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical
computer science audience, I survey these various definitions of quantum NP, their
strengths and weaknesses, and why most of them, for better or worse, actually
appear to fit naturally into the complexity zoo.'
article_type: review
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
citation:
ama: 'Gharibian S. Guest Column: The 7 faces of quantum NP. ACM SIGACT News.
2024;54(4):54-91.'
apa: 'Gharibian, S. (2024). Guest Column: The 7 faces of quantum NP. ACM SIGACT
News, 54(4), 54–91.'
bibtex: '@article{Gharibian_2024, title={Guest Column: The 7 faces of quantum NP},
volume={54}, number={4}, journal={ACM SIGACT News}, author={Gharibian, Sevag},
year={2024}, pages={54–91} }'
chicago: 'Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT
News 54, no. 4 (2024): 54–91.'
ieee: 'S. Gharibian, “Guest Column: The 7 faces of quantum NP,” ACM SIGACT News,
vol. 54, no. 4, pp. 54–91, 2024.'
mla: 'Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT
News, vol. 54, no. 4, 2024, pp. 54–91.'
short: S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
date_created: 2023-10-30T12:19:11Z
date_updated: 2024-01-07T18:16:36Z
intvolume: ' 54'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2310.18010
oa: '1'
page: 54-91
publication: ACM SIGACT News
publication_status: published
related_material:
link:
- relation: confirmation
url: https://dl.acm.org/doi/abs/10.1145/3639528.3639535
status: public
title: 'Guest Column: The 7 faces of quantum NP'
type: journal_article
user_id: '71541'
volume: 54
year: '2024'
...
---
_id: '50406'
abstract:
- lang: eng
text: "What is the power of polynomial-time quantum computation with access to an
NP\r\noracle? In this work, we focus on two fundamental tasks from the study of\r\nBoolean
satisfiability (SAT) problems: search-to-decision reductions, and\r\napproximate
counting. We first show that, in strong contrast to the classical\r\nsetting where
a poly-time Turing machine requires $\\Theta(n)$ queries to an NP\r\noracle to
compute a witness to a given SAT formula, quantumly $\\Theta(\\log n)$\r\nqueries
suffice. We then show this is tight in the black-box model - any\r\nquantum algorithm
with \"NP-like\" query access to a formula requires\r\n$\\Omega(\\log n)$ queries
to extract a solution with constant probability.\r\nMoving to approximate counting
of SAT solutions, by exploiting a quantum link\r\nbetween search-to-decision reductions
and approximate counting, we show that\r\nexisting classical approximate counting
algorithms are likely optimal. First,\r\nwe give a lower bound in the \"NP-like\"
black-box query setting: Approximate\r\ncounting requires $\\Omega(\\log n)$ queries,
even on a quantum computer. We then\r\ngive a \"white-box\" lower bound (i.e.
where the input formula is not hidden in\r\nthe oracle) - if there exists a randomized
poly-time classical or quantum\r\nalgorithm for approximate counting making $o(log
n)$ NP queries, then\r\n$\\text{BPP}^{\\text{NP}[o(n)]}$ contains a $\\text{P}^{\\text{NP}}$-complete\r\nproblem
if the algorithm is classical and $\\text{FBQP}^{\\text{NP}[o(n)]}$\r\ncontains
an $\\text{FP}^{\\text{NP}}$-complete problem if the algorithm is\r\nquantum."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Jonas
full_name: Kamminga, Jonas
last_name: Kamminga
citation:
ama: 'Gharibian S, Kamminga J. BQP, meet NP: Search-to-decision reductions and approximate
counting. In: Proceedings of 51st EATCS International Colloquium on Automata,
Languages and Programming (ICALP). Vol 297. ; 2024:1-19.'
apa: 'Gharibian, S., & Kamminga, J. (2024). BQP, meet NP: Search-to-decision
reductions and approximate counting. Proceedings of 51st EATCS International
Colloquium on Automata, Languages and Programming (ICALP), 297(70),
1–19.'
bibtex: '@inproceedings{Gharibian_Kamminga_2024, title={BQP, meet NP: Search-to-decision
reductions and approximate counting}, volume={297}, number={70}, booktitle={Proceedings
of 51st EATCS International Colloquium on Automata, Languages and Programming
(ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas}, year={2024}, pages={1–19}
}'
chicago: 'Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision
Reductions and Approximate Counting.” In Proceedings of 51st EATCS International
Colloquium on Automata, Languages and Programming (ICALP), 297:1–19, 2024.'
ieee: 'S. Gharibian and J. Kamminga, “BQP, meet NP: Search-to-decision reductions
and approximate counting,” in Proceedings of 51st EATCS International Colloquium
on Automata, Languages and Programming (ICALP), 2024, vol. 297, no. 70, pp.
1–19.'
mla: 'Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions
and Approximate Counting.” Proceedings of 51st EATCS International Colloquium
on Automata, Languages and Programming (ICALP), vol. 297, no. 70, 2024, pp.
1–19.'
short: 'S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium
on Automata, Languages and Programming (ICALP), 2024, pp. 1–19.'
date_created: 2024-01-09T13:59:44Z
date_updated: 2024-07-02T13:16:48Z
external_id:
arxiv:
- '2401.03943'
intvolume: ' 297'
issue: '70'
language:
- iso: eng
page: 1-19
publication: Proceedings of 51st EATCS International Colloquium on Automata, Languages
and Programming (ICALP)
publication_status: published
status: public
title: 'BQP, meet NP: Search-to-decision reductions and approximate counting'
type: conference
user_id: '71541'
volume: 297
year: '2024'
...
---
_id: '50273'
abstract:
- lang: eng
text: "The Polynomial-Time Hierarchy ($\\mathsf{PH}$) is a staple of classical\r\ncomplexity
theory, with applications spanning randomized computation to circuit\r\nlower
bounds to ''quantum advantage'' analyses for near-term quantum computers.\r\nQuantumly,
however, despite the fact that at least \\emph{four} definitions of\r\nquantum
$\\mathsf{PH}$ exist, it has been challenging to prove analogues for\r\nthese
of even basic facts from $\\mathsf{PH}$. This work studies three\r\nquantum-verifier
based generalizations of $\\mathsf{PH}$, two of which are from\r\n[Gharibian,
Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings\r\n($\\mathsf{QCPH}$)
and quantum mixed states ($\\mathsf{QPH}$) as proofs, and one\r\nof which is new
to this work, utilizing quantum pure states\r\n($\\mathsf{pureQPH}$) as proofs.
We first resolve several open problems from\r\n[GSSSY22], including a collapse
theorem and a Karp-Lipton theorem for\r\n$\\mathsf{QCPH}$. Then, for our new class
$\\mathsf{pureQPH}$, we show one-sided\r\nerror reduction for $\\mathsf{pureQPH}$,
as well as the first bounds relating\r\nthese quantum variants of $\\mathsf{PH}$,
namely $\\mathsf{QCPH}\\subseteq\r\n\\mathsf{pureQPH} \\subseteq \\mathsf{EXP}^{\\mathsf{PP}}$."
author:
- first_name: Avantika
full_name: Agarwal, Avantika
last_name: Agarwal
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Venkata
full_name: Koppula, Venkata
last_name: Koppula
- first_name: Dorian
full_name: Rudolph, Dorian
last_name: Rudolph
citation:
ama: 'Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies:
Karp-Lipton, error reduction, and lower bounds. In: Proceedings of 49th International
Symposium on Mathematical Foundations of Computer Science (MFCS). Vol 306.
; 2024:7-17. doi:10.4230/LIPIcs.MFCS.2024.7'
apa: 'Agarwal, A., Gharibian, S., Koppula, V., & Rudolph, D. (2024). Quantum
Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. Proceedings
of 49th International Symposium on Mathematical Foundations of Computer Science
(MFCS), 306(7), 7–17. https://doi.org/10.4230/LIPIcs.MFCS.2024.7'
bibtex: '@inproceedings{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial
Hierarchies: Karp-Lipton, error reduction, and lower bounds}, volume={306}, DOI={10.4230/LIPIcs.MFCS.2024.7},
number={7}, booktitle={Proceedings of 49th International Symposium on Mathematical
Foundations of Computer Science (MFCS)}, author={Agarwal, Avantika and Gharibian,
Sevag and Koppula, Venkata and Rudolph, Dorian}, year={2024}, pages={7–17} }'
chicago: 'Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph.
“Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds.”
In Proceedings of 49th International Symposium on Mathematical Foundations
of Computer Science (MFCS), 306:7–17, 2024. https://doi.org/10.4230/LIPIcs.MFCS.2024.7.'
ieee: 'A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial
Hierarchies: Karp-Lipton, error reduction, and lower bounds,” in Proceedings
of 49th International Symposium on Mathematical Foundations of Computer Science
(MFCS), 2024, vol. 306, no. 7, pp. 7–17, doi: 10.4230/LIPIcs.MFCS.2024.7.'
mla: 'Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error
Reduction, and Lower Bounds.” Proceedings of 49th International Symposium
on Mathematical Foundations of Computer Science (MFCS), vol. 306, no. 7, 2024,
pp. 7–17, doi:10.4230/LIPIcs.MFCS.2024.7.'
short: 'A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th
International Symposium on Mathematical Foundations of Computer Science (MFCS),
2024, pp. 7–17.'
date_created: 2024-01-07T20:09:32Z
date_updated: 2024-08-23T06:18:02Z
doi: 10.4230/LIPIcs.MFCS.2024.7
external_id:
arxiv:
- '2401.01633'
intvolume: ' 306'
issue: '7'
language:
- iso: eng
page: 7-17
publication: Proceedings of 49th International Symposium on Mathematical Foundations
of Computer Science (MFCS)
publication_status: published
status: public
title: 'Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds'
type: conference
user_id: '71541'
volume: 306
year: '2024'
...
---
_id: '56950'
abstract:
- lang: eng
text: "After nearly two decades of research, the question of a quantum PCP theorem\r\nfor
quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a\r\nresult,
proving QMA-hardness of approximation for ground state energy\r\nestimation has
remained elusive. Recently, it was shown [Bittel, Gharibian,\r\nKliesch, CCC 2023]
that a natural problem involving variational quantum\r\ncircuits is QCMA-hard
to approximate within ratio N^(1-eps) for any eps > 0 and\r\nN the input size.
Unfortunately, this problem was not related to quantum CSPs,\r\nleaving the question
of hardness of approximation for quantum CSPs open. In\r\nthis work, we show that
if instead of focusing on ground state energies, one\r\nconsiders computing properties
of the ground space, QCMA-hardness of computing\r\nground space properties can
be shown. In particular, we show that it is (1)\r\nQCMA-complete within ratio
N^(1-eps) to approximate the Ground State\r\nConnectivity problem (GSCON), and
(2) QCMA-hard within the same ratio to\r\nestimate the amount of entanglement
of a local Hamiltonian's ground state,\r\ndenoted Ground State Entanglement (GSE).
As a bonus, a simplification of our\r\nconstruction yields NP-completeness of
approximation for a natural k-SAT\r\nreconfiguration problem, to be contrasted
with the recent PCP-based PSPACE\r\nhardness of approximation results for a different
definition of k-SAT\r\nreconfiguration [Karthik C.S. and Manurangsi, 2023, and
Hirahara, Ohsaka, STOC\r\n2024]."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Carsten
full_name: Hecht, Carsten
last_name: Hecht
citation:
ama: Gharibian S, Hecht C. Hardness of approximation for ground state problems.
arXiv:241104874. Published online 2024.
apa: Gharibian, S., & Hecht, C. (2024). Hardness of approximation for ground
state problems. In arXiv:2411.04874.
bibtex: '@article{Gharibian_Hecht_2024, title={Hardness of approximation for ground
state problems}, journal={arXiv:2411.04874}, author={Gharibian, Sevag and Hecht,
Carsten}, year={2024} }'
chicago: Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground
State Problems.” ArXiv:2411.04874, 2024.
ieee: S. Gharibian and C. Hecht, “Hardness of approximation for ground state problems,”
arXiv:2411.04874. 2024.
mla: Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground
State Problems.” ArXiv:2411.04874, 2024.
short: S. Gharibian, C. Hecht, ArXiv:2411.04874 (2024).
date_created: 2024-11-08T07:58:24Z
date_updated: 2024-11-08T07:58:44Z
external_id:
arxiv:
- '2411.04874'
language:
- iso: eng
publication: arXiv:2411.04874
status: public
title: Hardness of approximation for ground state problems
type: preprint
user_id: '71541'
year: '2024'
...
---
_id: '56944'
abstract:
- lang: eng
text: "Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic\r\nHeisenberg
model, is a QMA-complete problem relevant to quantum many-body\r\nphysics and
computer science. Semidefinite programming relaxations have been\r\nfruitful in
designing theoretical approximation algorithms for QMC, but are\r\ncomputationally
expensive for systems beyond tens of qubits. We give a second\r\norder cone relaxation
for QMC, which optimizes over the set of mutually\r\nconsistent three-qubit reduced
density matrices. In combination with Pauli\r\nlevel-$1$ of the quantum Lasserre
hierarchy, the relaxation achieves an\r\napproximation ratio of $0.526$ to the
ground state energy. Our relaxation is\r\nsolvable on systems with hundreds of
qubits and paves the way to\r\ncomputationally efficient lower and upper bounds
on the ground state energy of\r\nlarge-scale quantum spin systems."
author:
- first_name: Felix
full_name: Huber, Felix
last_name: Huber
- first_name: Kevin
full_name: Thompson, Kevin
last_name: Thompson
- first_name: Ojas
full_name: Parekh, Ojas
last_name: Parekh
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
citation:
ama: Huber F, Thompson K, Parekh O, Gharibian S. Second order cone relaxations for
quantum Max Cut. arXiv:241104120. Published online 2024.
apa: Huber, F., Thompson, K., Parekh, O., & Gharibian, S. (2024). Second order
cone relaxations for quantum Max Cut. In arXiv:2411.04120.
bibtex: '@article{Huber_Thompson_Parekh_Gharibian_2024, title={Second order cone
relaxations for quantum Max Cut}, journal={arXiv:2411.04120}, author={Huber, Felix
and Thompson, Kevin and Parekh, Ojas and Gharibian, Sevag}, year={2024} }'
chicago: Huber, Felix, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. “Second
Order Cone Relaxations for Quantum Max Cut.” ArXiv:2411.04120, 2024.
ieee: F. Huber, K. Thompson, O. Parekh, and S. Gharibian, “Second order cone relaxations
for quantum Max Cut,” arXiv:2411.04120. 2024.
mla: Huber, Felix, et al. “Second Order Cone Relaxations for Quantum Max Cut.” ArXiv:2411.04120,
2024.
short: F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
date_created: 2024-11-07T12:09:37Z
date_updated: 2024-11-07T12:10:28Z
external_id:
arxiv:
- '2411.04120'
language:
- iso: eng
publication: arXiv:2411.04120
status: public
title: Second order cone relaxations for quantum Max Cut
type: preprint
user_id: '71541'
year: '2024'
...
---
_id: '32407'
abstract:
- lang: eng
text: "Estimating the ground state energy of a local Hamiltonian is a central\r\nproblem
in quantum chemistry. In order to further investigate its complexity\r\nand the
potential of quantum algorithms for quantum chemistry, Gharibian and Le\r\nGall
(STOC 2022) recently introduced the guided local Hamiltonian problem\r\n(GLH),
which is a variant of the local Hamiltonian problem where an\r\napproximation
of a ground state is given as an additional input. Gharibian and\r\nLe Gall showed
quantum advantage (more precisely, BQP-completeness) for GLH\r\nwith $6$-local
Hamiltonians when the guiding vector has overlap\r\n(inverse-polynomially) close
to 1/2 with a ground state. In this paper, we\r\noptimally improve both the locality
and the overlap parameters: we show that\r\nthis quantum advantage (BQP-completeness)
persists even with 2-local\r\nHamiltonians, and even when the guiding vector has
overlap\r\n(inverse-polynomially) close to 1 with a ground state. Moreover, we
show that\r\nthe quantum advantage also holds for 2-local physically motivated
Hamiltonians\r\non a 2D square lattice. This makes a further step towards establishing\r\npractical
quantum advantage in quantum chemistry."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Ryu
full_name: Hayakawa, Ryu
last_name: Hayakawa
- first_name: François Le
full_name: Gall, François Le
last_name: Gall
- first_name: Tomoyuki
full_name: Morimae, Tomoyuki
last_name: Morimae
citation:
ama: 'Gharibian S, Hayakawa R, Gall FL, Morimae T. Improved Hardness Results for
the Guided Local Hamiltonian Problem. In: Proceedings of the 50th EATCS International
Colloquium on Automata, Languages and Programming (ICALP). Vol 261. ; 2023:1-19.
doi:10.4230/LIPIcs.ICALP.2023.32'
apa: Gharibian, S., Hayakawa, R., Gall, F. L., & Morimae, T. (2023). Improved
Hardness Results for the Guided Local Hamiltonian Problem. Proceedings of the
50th EATCS International Colloquium on Automata, Languages and Programming (ICALP),
261(32), 1–19. https://doi.org/10.4230/LIPIcs.ICALP.2023.32
bibtex: '@inproceedings{Gharibian_Hayakawa_Gall_Morimae_2023, title={Improved Hardness
Results for the Guided Local Hamiltonian Problem}, volume={261}, DOI={10.4230/LIPIcs.ICALP.2023.32},
number={32}, booktitle={Proceedings of the 50th EATCS International Colloquium
on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and
Hayakawa, Ryu and Gall, François Le and Morimae, Tomoyuki}, year={2023}, pages={1–19}
}'
chicago: Gharibian, Sevag, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae.
“Improved Hardness Results for the Guided Local Hamiltonian Problem.” In Proceedings
of the 50th EATCS International Colloquium on Automata, Languages and Programming
(ICALP), 261:1–19, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.32.
ieee: 'S. Gharibian, R. Hayakawa, F. L. Gall, and T. Morimae, “Improved Hardness
Results for the Guided Local Hamiltonian Problem,” in Proceedings of the 50th
EATCS International Colloquium on Automata, Languages and Programming (ICALP),
2023, vol. 261, no. 32, pp. 1–19, doi: 10.4230/LIPIcs.ICALP.2023.32.'
mla: Gharibian, Sevag, et al. “Improved Hardness Results for the Guided Local Hamiltonian
Problem.” Proceedings of the 50th EATCS International Colloquium on Automata,
Languages and Programming (ICALP), vol. 261, no. 32, 2023, pp. 1–19, doi:10.4230/LIPIcs.ICALP.2023.32.
short: 'S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the
50th EATCS International Colloquium on Automata, Languages and Programming (ICALP),
2023, pp. 1–19.'
date_created: 2022-07-22T12:32:40Z
date_updated: 2023-10-09T04:17:10Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ICALP.2023.32
external_id:
arxiv:
- '2207.10250'
intvolume: ' 261'
issue: '32'
language:
- iso: eng
page: 1-19
publication: Proceedings of the 50th EATCS International Colloquium on Automata, Languages
and Programming (ICALP)
publication_status: published
status: public
title: Improved Hardness Results for the Guided Local Hamiltonian Problem
type: conference
user_id: '71541'
volume: 261
year: '2023'
...
---
_id: '50271'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: François
full_name: Le Gall, François
last_name: Le Gall
citation:
ama: 'Gharibian S, Le Gall F. Dequantizing the Quantum Singular Value Transformation:
Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.
SIAM Journal on Computing. 2023;52(4):1009-1038. doi:10.1137/22m1513721'
apa: 'Gharibian, S., & Le Gall, F. (2023). Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture. SIAM Journal on Computing, 52(4), 1009–1038. https://doi.org/10.1137/22m1513721'
bibtex: '@article{Gharibian_Le Gall_2023, title={Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture}, volume={52}, DOI={10.1137/22m1513721},
number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial
& Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Le Gall, François},
year={2023}, pages={1009–1038} }'
chicago: 'Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture.” SIAM Journal on Computing 52, no. 4 (2023): 1009–38. https://doi.org/10.1137/22m1513721.'
ieee: 'S. Gharibian and F. Le Gall, “Dequantizing the Quantum Singular Value Transformation:
Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture,”
SIAM Journal on Computing, vol. 52, no. 4, pp. 1009–1038, 2023, doi: 10.1137/22m1513721.'
mla: 'Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture.” SIAM Journal on Computing, vol. 52, no. 4, Society for
Industrial & Applied Mathematics (SIAM), 2023, pp. 1009–38, doi:10.1137/22m1513721.'
short: S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.
date_created: 2024-01-07T18:19:42Z
date_updated: 2024-01-07T18:20:37Z
doi: 10.1137/22m1513721
intvolume: ' 52'
issue: '4'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
page: 1009-1038
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
status: public
title: 'Dequantizing the Quantum Singular Value Transformation: Hardness and Applications
to Quantum Chemistry and the Quantum PCP Conjecture'
type: journal_article
user_id: '71541'
volume: 52
year: '2023'
...
---
_id: '31872'
abstract:
- lang: eng
text: "Savitch's theorem states that NPSPACE computations can be simulated in\r\nPSPACE.
We initiate the study of a quantum analogue of NPSPACE, denoted\r\nStreaming-QCMASPACE
(SQCMASPACE), where an exponentially long classical proof\r\nis streamed to a
poly-space quantum verifier. Besides two main results, we also\r\nshow that a
quantum analogue of Savitch's theorem is unlikely to hold, as\r\nSQCMASPACE=NEXP.
For completeness, we introduce Streaming-QMASPACE (SQMASPACE)\r\nwith an exponentially
long streamed quantum proof, and show SQMASPACE=QMA_EXP\r\n(quantum analogue of
NEXP). Our first main result shows, in contrast to the\r\nclassical setting, the
solution space of a quantum constraint satisfaction\r\nproblem (i.e. a local Hamiltonian)
is always connected when exponentially long\r\nproofs are permitted. For this,
we show how to simulate any Lipschitz\r\ncontinuous path on the unit hypersphere
via a sequence of local unitary gates,\r\nat the expense of blowing up the circuit
size. This shows quantum\r\nerror-correcting codes can be unable to detect one
codeword erroneously\r\nevolving to another if the evolution happens sufficiently
slowly, and answers\r\nan open question of [Gharibian, Sikora, ICALP 2015] regarding
the Ground State\r\nConnectivity problem. Our second main result is that any SQCMASPACE
computation\r\ncan be embedded into \"unentanglement\", i.e. into a quantum constraint\r\nsatisfaction
problem with unentangled provers. Formally, we show how to embed\r\nSQCMASPACE
into the Sparse Separable Hamiltonian problem of [Chailloux,\r\nSattath, CCC 2012]
(QMA(2)-complete for 1/poly promise gap), at the expense of\r\nscaling the promise
gap with the streamed proof size. As a corollary, we obtain\r\nthe first systematic
construction for obtaining QMA(2)-type upper bounds on\r\narbitrary multi-prover
interactive proof systems, where the QMA(2) promise gap\r\nscales exponentially
with the number of bits of communication in the\r\ninteractive proof."
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
last_name: Rudolph
citation:
ama: 'Gharibian S, Rudolph D. Quantum space, ground space traversal, and how to
embed multi-prover interactive proofs into unentanglement. In: 14th Innovations
in Theoretical Computer Science (ITCS). Vol 251. ; 2023:53:1-53:23. doi:10.4230/LIPIcs.ITCS.2023.53'
apa: Gharibian, S., & Rudolph, D. (2023). Quantum space, ground space traversal,
and how to embed multi-prover interactive proofs into unentanglement. 14th
Innovations in Theoretical Computer Science (ITCS), 251, 53:1-53:23.
https://doi.org/10.4230/LIPIcs.ITCS.2023.53
bibtex: '@inproceedings{Gharibian_Rudolph_2023, title={Quantum space, ground space
traversal, and how to embed multi-prover interactive proofs into unentanglement},
volume={251}, DOI={10.4230/LIPIcs.ITCS.2023.53},
booktitle={14th Innovations in Theoretical Computer Science (ITCS)}, author={Gharibian,
Sevag and Rudolph, Dorian}, year={2023}, pages={53:1-53:23} }'
chicago: Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal,
and How to Embed Multi-Prover Interactive Proofs into Unentanglement.” In 14th
Innovations in Theoretical Computer Science (ITCS), 251:53:1-53:23, 2023.
https://doi.org/10.4230/LIPIcs.ITCS.2023.53.
ieee: 'S. Gharibian and D. Rudolph, “Quantum space, ground space traversal, and
how to embed multi-prover interactive proofs into unentanglement,” in 14th
Innovations in Theoretical Computer Science (ITCS), 2023, vol. 251, p. 53:1-53:23,
doi: 10.4230/LIPIcs.ITCS.2023.53.'
mla: Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal,
and How to Embed Multi-Prover Interactive Proofs into Unentanglement.” 14th
Innovations in Theoretical Computer Science (ITCS), vol. 251, 2023, p. 53:1-53:23,
doi:10.4230/LIPIcs.ITCS.2023.53.
short: 'S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science
(ITCS), 2023, p. 53:1-53:23.'
date_created: 2022-06-13T14:40:46Z
date_updated: 2023-02-28T11:06:55Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ITCS.2023.53
external_id:
arxiv:
- '2206.05243'
intvolume: ' 251'
language:
- iso: eng
page: 53:1-53:23
publication: 14th Innovations in Theoretical Computer Science (ITCS)
publication_status: published
status: public
title: Quantum space, ground space traversal, and how to embed multi-prover interactive
proofs into unentanglement
type: conference
user_id: '71541'
volume: 251
year: '2023'
...
---
_id: '20841'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: James
full_name: Watson, James
last_name: Watson
- first_name: Johannes
full_name: Bausch, Johannes
last_name: Bausch
citation:
ama: 'Gharibian S, Watson J, Bausch J. The Complexity of Translationally Invariant
Problems beyond Ground State Energies. In: Proceedings of the 40th International
Symposium on Theoretical Aspects of Computer Science (STACS). Vol 254. ; 2023:54:1-54:21.
doi:https://doi.org/10.4230/LIPIcs.STACS.2023.54'
apa: Gharibian, S., Watson, J., & Bausch, J. (2023). The Complexity of Translationally
Invariant Problems beyond Ground State Energies. Proceedings of the 40th International
Symposium on Theoretical Aspects of Computer Science (STACS), 254,
54:1-54:21. https://doi.org/10.4230/LIPIcs.STACS.2023.54
bibtex: '@inproceedings{Gharibian_Watson_Bausch_2023, title={The Complexity of Translationally
Invariant Problems beyond Ground State Energies}, volume={254}, DOI={https://doi.org/10.4230/LIPIcs.STACS.2023.54},
booktitle={Proceedings of the 40th International Symposium on Theoretical Aspects
of Computer Science (STACS)}, author={Gharibian, Sevag and Watson, James and Bausch,
Johannes}, year={2023}, pages={54:1-54:21} }'
chicago: Gharibian, Sevag, James Watson, and Johannes Bausch. “The Complexity of
Translationally Invariant Problems beyond Ground State Energies.” In Proceedings
of the 40th International Symposium on Theoretical Aspects of Computer Science
(STACS), 254:54:1-54:21, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.54.
ieee: 'S. Gharibian, J. Watson, and J. Bausch, “The Complexity of Translationally
Invariant Problems beyond Ground State Energies,” in Proceedings of the 40th
International Symposium on Theoretical Aspects of Computer Science (STACS),
2023, vol. 254, p. 54:1-54:21, doi: https://doi.org/10.4230/LIPIcs.STACS.2023.54.'
mla: Gharibian, Sevag, et al. “The Complexity of Translationally Invariant Problems
beyond Ground State Energies.” Proceedings of the 40th International Symposium
on Theoretical Aspects of Computer Science (STACS), vol. 254, 2023, p. 54:1-54:21,
doi:https://doi.org/10.4230/LIPIcs.STACS.2023.54.
short: 'S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International
Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.'
date_created: 2020-12-24T14:15:09Z
date_updated: 2023-05-04T17:51:23Z
department:
- _id: '623'
- _id: '7'
doi: https://doi.org/10.4230/LIPIcs.STACS.2023.54
external_id:
arxiv:
- '2012.12717'
intvolume: ' 254'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.12717
oa: '1'
page: 54:1-54:21
publication: Proceedings of the 40th International Symposium on Theoretical Aspects
of Computer Science (STACS)
publication_status: published
status: public
title: The Complexity of Translationally Invariant Problems beyond Ground State Energies
type: conference
user_id: '71541'
volume: 254
year: '2023'
...
---
_id: '34138'
abstract:
- lang: eng
text: "Variational Quantum Algorithms (VQAs), such as the Quantum Approximate\r\nOptimization
Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen\r\nintense study
towards near-term applications on quantum hardware. A crucial\r\nparameter for
VQAs is the depth of the variational ansatz used - the smaller\r\nthe depth, the
more amenable the ansatz is to near-term quantum hardware in\r\nthat it gives
the circuit a chance to be fully executed before the system\r\ndecoheres. This
potential for depth reduction has made VQAs a staple of Noisy\r\nIntermediate-Scale
Quantum (NISQ)-era research.\r\n In this work, we show that approximating the
optimal depth for a given VQA\r\nansatz is intractable. Formally, we show that
for any constant $\\epsilon>0$, it\r\nis QCMA-hard to approximate the optimal
depth of a VQA ansatz within\r\nmultiplicative factor $N^{1-\\epsilon}$, for $N$
denoting the encoding size of\r\nthe VQA instance. (Here, Quantum Classical Merlin-Arthur
(QCMA) is a quantum\r\ngeneralization of NP.) We then show that this hardness
persists even in the\r\n\"simpler\" setting of QAOAs. To our knowledge, this yields
the first natural\r\nQCMA-hard-to-approximate problems. To achieve these results,
we bypass the need\r\nfor a PCP theorem for QCMA by appealing to the disperser-based
NP-hardness of\r\napproximation construction of [Umans, FOCS 1999]."
author:
- first_name: Lennart
full_name: Bittel, Lennart
last_name: Bittel
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Martin
full_name: Kliesch, Martin
last_name: Kliesch
citation:
ama: 'Bittel L, Gharibian S, Kliesch M. The Optimal Depth of Variational Quantum
Algorithms Is QCMA-Hard to Approximate. In: Proceedings of the 38th Computational
Complexity Conference (CCC). Vol 264. Leibniz International Proceedings in
Informatics (LIPIcs). ; 2023:34:1-34:24. doi:10.4230/LIPIcs.CCC.2023.34'
apa: Bittel, L., Gharibian, S., & Kliesch, M. (2023). The Optimal Depth of Variational
Quantum Algorithms Is QCMA-Hard to Approximate. Proceedings of the 38th Computational
Complexity Conference (CCC), 264(34), 34:1-34:24. https://doi.org/10.4230/LIPIcs.CCC.2023.34
bibtex: '@inproceedings{Bittel_Gharibian_Kliesch_2023, series={Leibniz International
Proceedings in Informatics (LIPIcs)}, title={The Optimal Depth of Variational
Quantum Algorithms Is QCMA-Hard to Approximate}, volume={264}, DOI={10.4230/LIPIcs.CCC.2023.34},
number={34}, booktitle={Proceedings of the 38th Computational Complexity Conference
(CCC)}, author={Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}, year={2023},
pages={34:1-34:24}, collection={Leibniz International Proceedings in Informatics
(LIPIcs)} }'
chicago: Bittel, Lennart, Sevag Gharibian, and Martin Kliesch. “The Optimal Depth
of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” In Proceedings
of the 38th Computational Complexity Conference (CCC), 264:34:1-34:24. Leibniz
International Proceedings in Informatics (LIPIcs), 2023. https://doi.org/10.4230/LIPIcs.CCC.2023.34.
ieee: 'L. Bittel, S. Gharibian, and M. Kliesch, “The Optimal Depth of Variational
Quantum Algorithms Is QCMA-Hard to Approximate,” in Proceedings of the 38th
Computational Complexity Conference (CCC), 2023, vol. 264, no. 34, p. 34:1-34:24,
doi: 10.4230/LIPIcs.CCC.2023.34.'
mla: Bittel, Lennart, et al. “The Optimal Depth of Variational Quantum Algorithms
Is QCMA-Hard to Approximate.” Proceedings of the 38th Computational Complexity
Conference (CCC), vol. 264, no. 34, 2023, p. 34:1-34:24, doi:10.4230/LIPIcs.CCC.2023.34.
short: 'L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational
Complexity Conference (CCC), 2023, p. 34:1-34:24.'
date_created: 2022-11-24T08:07:56Z
date_updated: 2023-07-10T14:33:00Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.CCC.2023.34
external_id:
arxiv:
- '2211.12519'
intvolume: ' 264'
issue: '34'
language:
- iso: eng
page: 34:1-34:24
publication: Proceedings of the 38th Computational Complexity Conference (CCC)
publication_status: published
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate
type: conference
user_id: '71541'
volume: 264
year: '2023'
...
---
_id: '27531'
abstract:
- lang: eng
text: "The Quantum Singular Value Transformation (QSVT) is a recent technique that\r\ngives
a unified framework to describe most quantum algorithms discovered so\r\nfar,
and may lead to the development of novel quantum algorithms. In this paper\r\nwe
investigate the hardness of classically simulating the QSVT. A recent result\r\nby
Chia, Gily\\'en, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can\r\nbe
efficiently \"dequantized\" for low-rank matrices, and discussed its\r\nimplication
to quantum machine learning. In this work, motivated by\r\nestablishing the superiority
of quantum algorithms for quantum chemistry and\r\nmaking progress on the quantum
PCP conjecture, we focus on the other main class\r\nof matrices considered in
applications of the QSVT, sparse matrices.\r\n We first show how to efficiently
\"dequantize\", with arbitrarily small\r\nconstant precision, the QSVT associated
with a low-degree polynomial. We apply\r\nthis technique to design classical algorithms
that estimate, with constant\r\nprecision, the singular values of a sparse matrix.
We show in particular that a\r\ncentral computational problem considered by quantum
algorithms for quantum\r\nchemistry (estimating the ground state energy of a local
Hamiltonian when\r\ngiven, as an additional input, a state sufficiently close
to the ground state)\r\ncan be solved efficiently with constant precision on a
classical computer. As a\r\ncomplementary result, we prove that with inverse-polynomial
precision, the same\r\nproblem becomes BQP-complete. This gives theoretical evidence
for the\r\nsuperiority of quantum algorithms for chemistry, and strongly suggests
that\r\nsaid superiority stems from the improved precision achievable in the quantum\r\nsetting.
We also discuss how this dequantization technique may help make\r\nprogress on
the central quantum PCP conjecture."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: François Le
full_name: Gall, François Le
last_name: Gall
citation:
ama: 'Gharibian S, Gall FL. Dequantizing the Quantum Singular Value Transformation:
Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.
In: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC).
; 2022:19-32.'
apa: 'Gharibian, S., & Gall, F. L. (2022). Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the
Quantum PCP Conjecture. Proceedings of the 54th ACM Symposium on Theory of
Computing (STOC), 19–32.'
bibtex: '@inproceedings{Gharibian_Gall_2022, title={Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the
Quantum PCP Conjecture}, booktitle={Proceedings of the 54th ACM Symposium on Theory
of Computing (STOC)}, author={Gharibian, Sevag and Gall, François Le}, year={2022},
pages={19–32} }'
chicago: 'Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the
Quantum PCP Conjecture.” In Proceedings of the 54th ACM Symposium on Theory
of Computing (STOC), 19–32, 2022.'
ieee: 'S. Gharibian and F. L. Gall, “Dequantizing the Quantum Singular Value Transformation:
Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture,”
in Proceedings of the 54th ACM Symposium on Theory of Computing (STOC),
2022, pp. 19–32.'
mla: 'Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the
Quantum PCP Conjecture.” Proceedings of the 54th ACM Symposium on Theory of
Computing (STOC), 2022, pp. 19–32.'
short: 'S. Gharibian, F.L. Gall, in: Proceedings of the 54th ACM Symposium on Theory
of Computing (STOC), 2022, pp. 19–32.'
date_created: 2021-11-18T07:32:56Z
date_updated: 2023-10-09T04:17:29Z
department:
- _id: '623'
- _id: '7'
external_id:
arxiv:
- '2111.09079'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2111.09079
oa: '1'
page: 19-32
publication: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)
publication_status: published
status: public
title: 'Dequantizing the Quantum Singular Value Transformation: Hardness and Applications
to Quantum Chemistry and the Quantum PCP Conjecture'
type: conference
user_id: '71541'
year: '2022'
...
---
_id: '34700'
article_number: '13'
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). Computational Complexity.
2022;31(2). doi:10.1007/s00037-022-00231-8
apa: Gharibian, S., Santha, M., Sikora, J., Sundaram, A., & Yirka, J. (2022).
Quantum generalizations of the polynomial hierarchy with applications to QMA(2).
Computational Complexity, 31(2), Article 13. https://doi.org/10.1007/s00037-022-00231-8
bibtex: '@article{Gharibian_Santha_Sikora_Sundaram_Yirka_2022, title={Quantum generalizations
of the polynomial hierarchy with applications to QMA(2)}, volume={31}, DOI={10.1007/s00037-022-00231-8},
number={213}, journal={Computational Complexity}, publisher={Springer Science
and Business Media LLC}, author={Gharibian, Sevag and Santha, Miklos and Sikora,
Jamie and Sundaram, Aarthi and Yirka, Justin}, year={2022} }'
chicago: Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin
Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications
to QMA(2).” Computational Complexity 31, no. 2 (2022). https://doi.org/10.1007/s00037-022-00231-8.
ieee: 'S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum generalizations
of the polynomial hierarchy with applications to QMA(2),” Computational Complexity,
vol. 31, no. 2, Art. no. 13, 2022, doi: 10.1007/s00037-022-00231-8.'
mla: Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy
with Applications to QMA(2).” Computational Complexity, vol. 31, no. 2,
13, Springer Science and Business Media LLC, 2022, doi:10.1007/s00037-022-00231-8.
short: S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational
Complexity 31 (2022).
date_created: 2022-12-21T10:53:52Z
date_updated: 2023-02-28T11:07:02Z
department:
- _id: '623'
- _id: '7'
doi: 10.1007/s00037-022-00231-8
intvolume: ' 31'
issue: '2'
keyword:
- Computational Mathematics
- Computational Theory and Mathematics
- General Mathematics
- Theoretical Computer Science
language:
- iso: eng
publication: Computational Complexity
publication_identifier:
issn:
- 1016-3328
- 1420-8954
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
type: journal_article
user_id: '71541'
volume: 31
year: '2022'
...
---
_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
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: 2023-02-28T11:07:56Z
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'
...