2 citations · 3 across the 8 of their papers we have counts for
11 papers
A physical and universal model of bosonic computations with Solovay-Kitaev theorem
Dorian Rudolph, Arsalan Motamedi, Dhruva Sambrani +4
Bosonic quantum systems are among the leading architectures for quantum information processing, offering continuous-variable degrees of freedom with strong error-correction capabil…
Verification Complexity and Extension of Classical Shadows
Georgios Karaiskos, Asad Raza, Dorian Rudolph +2
Classical shadows are an influential framework for compressing copies of a given quantum state into classical data , enabling many properties of to be predicted from rel…
Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
Sevag Gharibian, Carsten Hecht, Dorian Rudolph
We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on . We consider semidefinite pr…
Energy, Bosons and Computational Complexity
Dorian Rudolph, Arsalan Motamedi, Dhruva Sambrani +4
We investigate the role of energy, i.e. average photon number, as a resource in the computational complexity of bosonic systems. We show three sets of results: (1. Energy growth ra…
How hard is it to verify a classical shadow?
Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer +2
Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state rho, while only requiring measurements…
Quantum k-SAT Related Hypergraph Problems
Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian
The Quantum k-SAT problem is the quantum generalization of the k-SAT problem. It is the problem whether a given local Hamiltonian is frustration-free. Frustration-free means that t…
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
Marco Aldi, Sevag Gharibian, Dorian Rudolph
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intract…
Quantum 2-SAT on low dimensional systems is -complete: Direct embeddings and black-box simulation
Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the c…
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1
The Polynomial-Time Hierarchy () is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum adv…
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
Sevag Gharibian, Dorian Rudolph
Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), whe…
On polynomially many queries to NP or QMA oracles
Sevag Gharibian, Dorian Rudolph
We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as and , respective…