Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1604.01384 · Leibniz international proceedings in informatics

A Complete Characterization of Unitary Quantum Space

Bill Fefferman, Cedric Yen-Yu Lin

Published Apr 5, 2016• 39 citations
arXivHTMLPDF

Abstract

Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded $2^{k(n)}\times 2^{k(n)}$ matrix is complete for the class of problems solvable by quantum circuits acting on $\mathcal{O}(k(n))$ qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian $2^{k(n)}\times 2^{k(n)}$ matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma [STOC '13] by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.

DOI
10.4230/lipics.itcs.2018.4

Related papers

Quantum Merlin Arthur with Exponentially Small Gap

Bill Fefferman, Cedric Yen-Yu Lin

We study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems solvable with a polynomial amount of memory. As applications we show that a "precise" version of the Local Hamiltonian problem is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states is not as powerful as the ability to prepare the ground state of general Local Hamiltonians.

arXiv:1601.01975•Jan 8, 2016•24 citations

Space-Efficient Error Reduction for Unitary Quantum Computations

Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin +2 more

This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.

arXiv:1604.08192•Leibniz international proceedings in informatics•Jan 1, 2016•11 citations

Space-bounded quantum state testing via space-efficient quantum singular value transformation

François Le Gall, Yupan Liu, Qisheng Wang

Abstract Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary ) and two-sided error ( ), approached from a quantum (mixed) state testing perspective: The first family of natural complete problems for unitary $$\text {\textsf {coRQL}} $$ coRQL , namely space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance; A new family of (arguably simpler) natural complete problems for , namely space-bounded quantum state testing for trace distance, Hilbert–Schmidt distance, and (von Neumann) entropy difference. In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as $$Q_0$$ Q 0 and $$Q_1$$ Q 1 , which prepare quantum states $$\rho _0$$ ρ 0 and $$\rho _1$$ ρ 1 , respectively, with access to their “source code”. Our goal is to decide whether $$\rho _0$$ ρ 0 is $$\epsilon _1$$ ϵ 1 -close to or $$\epsilon _2$$ ϵ 2 -far from $$\rho _1$$ ρ 1 with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, which exhibit computational hardness depending on the chosen distance-like measure (either -complete or -complete), our results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states. Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gilyén, Su, Low, and Wiebe (STOC 2019), which is of independent interest. Our technique provides a unified approach for designing space-bounded quantum algorithms. Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for (special forms of) the projected unitary encoding.

arXiv:2308.05079•Computational Complexity•Nov 10, 2026•23 citations

Power of Quantum Computation with Few Clean Qubits

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae +3 more

This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining qubits are initially in the totally mixed state. No initializations of qubits are allowed during the computation, nor intermediate measurements. The main results of this paper are unexpectedly strong error-reducible properties of such quantum computations. It is proved that any problem solvable by a polynomial-time quantum computation with one-sided bounded error that uses logarithmically many clean qubits can also be solvable with exponentially small one-sided error using just two clean qubits, and with polynomially small one-sided error using just one clean qubit. It is further proved in the case of two-sided bounded error that any problem solvable by such a computation with a constant gap between completeness and soundness using logarithmically many clean qubits can also be solvable with exponentially small two-sided error using just two clean qubits. If only one clean qubit is available, the problem is again still solvable with exponentially small error in one of the completeness and soundness and polynomially small error in the other. As an immediate consequence of the above result for the two-sided-error case, it follows that the TRACE ESTIMATION problem defined with fixed constant threshold parameters is complete for the classes of problems solvable by polynomial-time quantum computations with completeness 2/3 and soundness 1/3 using logarithmically many clean qubits and just one clean qubit. The techniques used for proving the error-reduction results may be of independent interest in themselves, and one of the technical tools can also be used to show the hardness of weak classical simulations of one-clean-qubit computations (i.e., DQC1 computations).

arXiv:1509.07276•Leibniz international proceedings in informatics•Sep 24, 2015•25 citations

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1 more

The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.

quant-pharXiv:2602.14379•Leibniz international proceedings in informatics•Feb 17, 2026•2 citations

Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms

Kazuki Sakamoto, Keisuke Fujii

The Berry phase is a fundamental geometric quantity for characterizing the geometry and topology of quantum many-body systems. Previous work established a super-polynomial quantum advantage in Berry phase estimation at inverse-polynomial precision, given an ansatz state approximating the initial ground state. However, whether this hardness persists for Berry phases quantized by symmetry, which can be distinguished at constant precision, remained open. In this work, we characterize the computational complexity of quantized Berry phase estimation. First, we prove that deciding whether the Berry phase is exactly $0$ or $π$ is $\mathsf{BQP}$-complete when the spectral gap is inverse-polynomially small. This result implies that distinguishing the quantized Berry phase still has a super-polynomial quantum advantage, assuming $\mathsf{BPP}\neq \mathsf{BQP}$. To prove this result, we introduce an encoding that maps the output of any quantum computation to a Berry phase that is exactly $0$ or $π$. Second, we extend this hardness to physically motivated Hamiltonians on a 2D square lattice, including Heisenberg and XY interactions. Third, we provide a classical polynomial-time algorithm for geometrically local Hamiltonians on fixed-dimensional lattices with constant spectral gaps. Therefore we identify that the spectral gap is a key resource for the classical tractability, rather than precision. These results establish a super-polynomial quantum advantage for computing a quantized topological invariant that is unchanged under symmetry- and gap-preserving deformations, and provide new steps towards practical quantum advantage in quantum physics.

quant-pharXiv:2609.37199•Sep 30, 2026•0 citations
Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded 2k(n)×2k(n)2^{k(n)}\times 2^{k(n)}2k(n)×2k(n) matrix is complete for the class of problems solvable by quantum circuits acting on O(k(n))\mathcal{O}(k(n))O(k(n)) qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian 2k(n)×2k(n)2^{k(n)}\times 2^{k(n)}2k(n)×2k(n) matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma [STOC '13] by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.
This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.
Abstract Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary ) and two-sided error ( ), approached from a quantum (mixed) state testing perspective: The first family of natural complete problems for unitary coRQL\text {\textsf {coRQL}} coRQL coRQL , namely space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance; A new family of (arguably simpler) natural complete problems for , namely space-bounded quantum state testing for trace distance, Hilbert–Schmidt distance, and (von Neumann) entropy difference. In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as Q0Q_0Q0​ Q 0 and Q1Q_1Q1​ Q 1 , which prepare quantum states ρ0\rho _0ρ0​ ρ 0 and ρ1\rho _1ρ1​ ρ 1 , respectively, with access to their “source code”. Our goal is to decide whether ρ0\rho _0ρ0​ ρ 0 is ϵ1\epsilon _1ϵ1​ ϵ 1 -close to or ϵ2\epsilon _2ϵ2​ ϵ 2 -far from ρ1\rho _1ρ1​ ρ 1 with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, which exhibit computational hardness depending on the chosen distance-like measure (either -complete or -complete), our results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states. Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gilyén, Su, Low, and Wiebe (STOC 2019), which is of independent interest. Our technique provides a unified approach for designing space-bounded quantum algorithms. Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for (special forms of) the projected unitary encoding.
This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining qubits are initially in the totally mixed state. No initializations of qubits are allowed during the computation, nor intermediate measurements. The main results of this paper are unexpectedly strong error-reducible properties of such quantum computations. It is proved that any problem solvable by a polynomial-time quantum computation with one-sided bounded error that uses logarithmically many clean qubits can also be solvable with exponentially small one-sided error using just two clean qubits, and with polynomially small one-sided error using just one clean qubit. It is further proved in the case of two-sided bounded error that any problem solvable by such a computation with a constant gap between completeness and soundness using logarithmically many clean qubits can also be solvable with exponentially small two-sided error using just two clean qubits. If only one clean qubit is available, the problem is again still solvable with exponentially small error in one of the completeness and soundness and polynomially small error in the other. As an immediate consequence of the above result for the two-sided-error case, it follows that the TRACE ESTIMATION problem defined with fixed constant threshold parameters is complete for the classes of problems solvable by polynomial-time quantum computations with completeness 2/3 and soundness 1/3 using logarithmically many clean qubits and just one clean qubit. The techniques used for proving the error-reduction results may be of independent interest in themselves, and one of the technical tools can also be used to show the hardness of weak classical simulations of one-clean-qubit computations (i.e., DQC1 computations).
The local Hamiltonian (LH) problem is the canonical QMA\mathsf{QMA}QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on nnn qubits cannot be solved classically in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n) for any ε>0\varepsilon>0ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2)O(2^{(1-\varepsilon)n/2})O(2(1−ε)n/2) for any ε>0\varepsilon>0ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA\mathsf{QMA}QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n)O(\sqrt{2^n})O(2n​) time for an arbitrary 1/poly(n)1/\mathrm{poly}(n)1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a TTT-time quantum circuit acting on NNN qubits into a (d+1)(d+1)(d+1)-local Hamiltonian acting on N+O(T1/d)N+O(T^{1/d})N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T)N+O(T)N+O(T) qubits.
The Berry phase is a fundamental geometric quantity for characterizing the geometry and topology of quantum many-body systems. Previous work established a super-polynomial quantum advantage in Berry phase estimation at inverse-polynomial precision, given an ansatz state approximating the initial ground state. However, whether this hardness persists for Berry phases quantized by symmetry, which can be distinguished at constant precision, remained open. In this work, we characterize the computational complexity of quantized Berry phase estimation. First, we prove that deciding whether the Berry phase is exactly 000 or πππ is BQP\mathsf{BQP}BQP-complete when the spectral gap is inverse-polynomially small. This result implies that distinguishing the quantized Berry phase still has a super-polynomial quantum advantage, assuming BPP≠BQP\mathsf{BPP}\neq \mathsf{BQP}BPP=BQP. To prove this result, we introduce an encoding that maps the output of any quantum computation to a Berry phase that is exactly 000 or πππ. Second, we extend this hardness to physically motivated Hamiltonians on a 2D square lattice, including Heisenberg and XY interactions. Third, we provide a classical polynomial-time algorithm for geometrically local Hamiltonians on fixed-dimensional lattices with constant spectral gaps. Therefore we identify that the spectral gap is a key resource for the classical tractability, rather than precision. These results establish a super-polynomial quantum advantage for computing a quantized topological invariant that is unchanged under symmetry- and gap-preserving deformations, and provide new steps towards practical quantum advantage in quantum physics.