Alexandru Gheorghiu

Alexandru Gheorghiu

We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time. As constant-depth quantum circuits can be learned from polynomially many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom. This separates pseudoentanglement from pseudorandomness in the shallow-circuit regime: the former is possible, while the latter is not. The construction is based on the quantum intractability of the Dense-Sparse Learning Parity with Noise problem introduced in [DJ25] and uses a bounded-fan-in, bounded-fan-out classical randomized encoding for linear maps $\mathbf{x} \mapsto \mathbf{Mx},$ which could be of independent interest. As applications, we obtain quantum hardness for the problem of learning the entanglement structure (across a fixed cut) of the ground-state of 1D and 2D local Hamiltonians. The 1D Hamiltonian has an inverse polynomial gap, whereas the 2D one has a constant gap. This complements the result of [BZZ24] that showed only factoring-based hardness for the 1D case, though achieving a volume versus area entanglement difference.

Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu et al.

We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation strategies based on locating outputs with large probabilities. We then prove that DQI can be simulated at a low level of the polynomial hierarchy, posing challenges to standard quantum supremacy arguments. We further show that DQI is a constructive solution to a classical coding-theoretic bound based on the MacWilliams identity. Lastly, we interpret DQI as preparing low-energy states of a quantum simple harmonic oscillator, a viewpoint we believe suggests a physics-motivated route to generalizing DQI.

Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban et al.

We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA $\cap$ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP $\cap$ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.

Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu et al.

We initiate the study of quantum agnostic learning of phase states with respect to a function class $\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$: given copies of an unknown $n$-qubit state $|ψ\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|φ_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathsf{C}$, output $|φ\rangle$ which has fidelity $|\langle φ| ψ\rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: (i) Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. (ii) $s$-term DNF formulas in time $\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state $|φ\rangle$ such that $|\langle φ|ψ\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$, into a strong learner which outputs a superposition of parity states $|φ'\rangle$ such that $|\langle φ'|ψ\rangle|^2\geq \textsf{opt} - \varepsilon$. Using quantum agnostic boosting, we obtain a $n^{O(\log \log n \cdot \log(1/\varepsilon))}$-time algorithm for learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform $\textsf{PAC}$ model given quantum examples, which is near-polynomial time for constant $\varepsilon$. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\textsf{PAC}$ model and our work answers this given quantum examples.

Alexandru Gheorghiu, Tony Metger, Alexander Poremba

Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation. The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared $n$ uniformly random BB84 states (up to a change of basis on his space). Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent $n$ random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.

Alexandru Gheorghiu, Thomas Vidick

We introduce a protocol between a classical polynomial-time verifier and a quantum polynomial-time prover that allows the verifier to securely delegate to the prover the preparation of certain single-qubit quantum states. The protocol realizes the following functionality, with computational security: the verifier chooses one of the observables $Z$, $X$, $Y$, $(X+Y)/\sqrt{2}$, $(X-Y)/\sqrt{2}$; the prover receives a uniformly random eigenstate of the observable chosen by the verifier; the verifier receives a classical description of that state. The prover is unaware of which state he received and moreover, the verifier can check with high confidence whether the preparation was successful. The delegated preparation of single-qubit states is an elementary building block in many quantum cryptographic protocols. We expect our implementation of "random remote state preparation with verification", a functionality first defined in (Dunjko and Kashefi 2014), to be useful for removing the need for quantum communication in such protocols while keeping functionality. The main application that we detail is to a protocol for blind and verifiable delegated quantum computation (DQC) that builds on the work of (Fitzsimons and Kashefi 2018), who provided such a protocol with quantum communication. Recently, both blind an verifiable DQC were shown to be possible, under computational assumptions, with a classical polynomial-time client (Mahadev 2017, Mahadev 2018). Compared to the work of Mahadev, our protocol is more modular, applies to the measurement-based model of computation (instead of the Hamiltonian model) and is composable. Our proof of security builds on ideas introduced in (Brakerski et al. 2018).

Alexandru Gheorghiu, Theodoros Kapourniotis, Elham Kashefi

Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification, has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.