Search

Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms., Full version of the MFCS 2022 paper. Typos fixed. Some minor clarifications and corrections

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes $P^{NP[\log]}$ and $P^{QMA[\log]}$, defined identically to $P^{NP}$ and $P^{QMA}$, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a $P^{NP}$ machine have a "query graph" which is a tree, then this computation can be simulated in $P^{NP[\log]}$. In this work, we first show that for any verification class $C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}$, any $P^C$ machine with a query graph of "separator number" $s$ can be simulated using deterministic time $\exp(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in O(1)$ (which includes the case of $O(1)$-treewidth, and thus also of trees), this gives an upper bound of $P^{C[\log]}$, and when $s\in O(\log^k(n))$, this yields bound $QP^{C[\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding $P^C$ computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial $p$ specified via an arithmetic circuit, if one can "weakly compress" $p$ so that its optimal value requires $m$ bits to represent, then $P^{NP}$ can be decided with only $m$ queries to an NP-oracle., 46 pages pages, 5 figures, to appear in ITCS 2022

Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Metger and Vidick, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ε must be poly(N,ε)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution [Metger et al., 2021] under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 64:1-64:19

A celebrated result in classical complexity theory is Savitch’s theorem, which states that non-deterministic polynomial-space computations (NPSPACE) can be simulated by deterministic poly-space computations (PSPACE). In this work, we initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), in which an exponentially long classical proof is streamed to a poly-space quantum verifier. We first show that a quantum analogue of Savitch’s theorem is unlikely to hold, in that SQCMASPACE = NEXP. For completeness, we also introduce the companion class Streaming-QMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE = QMAEXP (the quantum analogue of NEXP). Our primary focus, however, is on the study of exponentially long streaming classical proofs, where we next show the following two main results. The first result shows that, in strong contrast to the classical setting, the solution space of a quantum constraint satisfaction problem (i.e. a local Hamiltonian) is always connected when exponentially long proofs are permitted. For this, we show how to simulate any Lipschitz continuous path on the unit hypersphere via a sequence of local unitary gates, at the expense of blowing up the circuit size. This shows that quantum error-correcting codes can be unable to detect one codeword erroneously evolving to another if the evolution happens sufficiently slowly, and answers an open question of [Gharibian, Sikora, ICALP 2015] regarding the Ground State Connectivity problem. Our second main result is that any SQCMASPACE computation can be embedded into "unentanglement", i.e. into a quantum constraint satisfaction problem with unentangled provers. Formally, we show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, CCC 2012] (QMA(2)-complete for 1/poly promise gap), at the expense of scaling the promise gap with the streamed proof size. As a corollary, we obtain the first systematic construction for obtaining QMA(2)-type upper bounds on arbitrary multi-prover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof. Our construction uses a new technique for exploiting unentanglement to simulate quadratic Boolean functions, which in some sense allows history states to encode the future., LIPIcs, Vol. 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), pages 53:1-53:23

We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound., LIPIcs, Vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pages 69:1-69:23

We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “product” lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture PNP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).

In this work, we study Static and Dynamic Games on Large Networks of interacting agents, assuming that the players have some statistical description of the interaction graph, as well as some local information. Inspired by Statistical Physics, we consider statistical ensembles of games and define a Probabilistic Approximate equilibrium notion for such ensembles. A Necessary Information Complexity notion is introduced to quantify the minimum amount of information needed for the existence of a Probabilistic Approximate equilibrium. We then focus on some special classes of games for which it is possible to derive upper and/or lower bounds for the complexity. At first, static and dynamic games on random graphs are studied and their complexity is determined as a function of the graph connectivity. In the low complexity case, we compute Probabilistic Approximate equilibrium strategies. We then consider static games on lattices and derive upper and lower bounds for the complexity, using contraction mapping ideas. A LQ game on a large ring is also studied numerically. Using a reduction technique, approximate equilibrium strategies are computed and it turns out that the complexity is relatively low.

Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the exponential time hypothesis. We show that the maximum winning probability of free games can be estimated in polynomial time by linear programming. We also show that 3-SAT with m variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(m^{1/2})-player one-round non-local games, in which the players communicate O(m^{1/2}) bits all together. We show that the optimization of certain polynomials over the hypersphere can be performed in quasipolynomial time in the number of variables n by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a result due to Aaronson -- showing that given an unknown n qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information., 39 pages, no figure. v2: changes to references and other minor improvements. v3: added some explanations, mostly about Theorem 1 and Conjecture 5. STOC version. v4, v5. small improvements and fixes

The theory of quantum communication and technology have been one of hot research topics in information science and technology since 1980s. In this paper, we survey some research development of several mathematical problems in quantum information theory. Particularly, we focus on the important role of combinatorics (including graph theory), number theory, algebra and algebraic geometry (the arithmetic theory of algebraic curves over finite field) in investigating quantum measurement and quantum error-correction.

In this work, we use quantum complexity theory to quantify the difficulty of distinguishing eigenstates obeying the Eigenstate Thermalization Hypothesis (ETH). After identifying simple operators with an algebra of low-energy observables and tracing out the complementary high-energy Hilbert space, the ETH leads to an exponential suppression of trace distance between the coarse-grained eigenstates. Conversely, we show that an exponential hardness of distinguishing between states implies ETH-like matrix elements. The BBBV lower bound on the query complexity of Grover search then translates directly into a complexity-theoretic statement lower bounding the hardness of distinguishing these reduced states., 19 pages, 4 figures; minor changes

We extend the reach of fixed-parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed-parameter analysis, making use of the landscape of these new classes. On the one hand this unifies results that would not otherwise show their kinship, while on the other it allows for further exchange of insights between complexity theory and computability theory. In the landscape of our fixed-parameter decidability classes, we recover part of the classification of real numbers according to their computability. From this, using the structural properties of the landscape, we get a new proof of the existence of P-selective bi-immune sets. Furthermore, we show that parameter values in parameterized sets in our uniformly fixed-parameter decidability classes interact with both instance complexity and Kolmogorov complexity. By deriving a parameter based upper bound on instance complexity, we demonstrate how parameters convey a sense of randomness. Motivated by the instance complexity conjecture, we show that the upper bound on the instance complexity is infinitely often also an upper bound on the Kolmogorov complexity.

We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function with information complexity ≤ O ( k ), and distributional communication complexity ≥ 2 k . This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [2015], our gap is the largest possible. By a result of Braverman and Rao [2014], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold, answering a long-standing open problem. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

Which computational problems can be solved in polynomial-time and which cannot? Though seemingly technical, this question has wide-ranging implications and brings us to the heart of both theoretical computer science and modern physics.

The concepts of quantum correlation complexity and quantum communication complexity were recently proposed to quantify the minimum amount of resources needed in generating bipartite classical or quantum states in the single-shot setting. The former is the minimum size of the initially shared state $\sigma$ on which local operations by the two parties (without communication) can generate the target state $\rho$, and the latter is the minimum amount of communication needed when initially sharing nothing. In this paper, we generalize these two concepts to multipartite cases, for both exact and approximate state generation. Our results are summarized as follows. (1) For multipartite pure states, the correlation complexity can be completely characterized by local ranks of sybsystems. (2) We extend the notion of PSD-rank of matrices to that of tensors, and use it to bound the quantum correlation complexity for generating multipartite classical distributions. (3) For generating multipartite mixed quantum states, communication complexity is not always equal to correlation complexity (as opposed to bipartite case). But they differ by at most a factor of 2. Generating a multipartite mixed quantum state has the same communication complexity as generating its optimal purification. But for correlation complexity of these two tasks can be different (though still related by less than a factor of 2). (4) To generate a bipartite classical distribution $P(x,y)$ approximately, the quantum communication complexity is completely characterized by the approximate PSD-rank of $P$. The quantum correlation complexity of approximately generating multipartite pure states is bounded by approximate local ranks., Comment: 19 pages; some typos are corrected

Quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables. It generalizes, and on 1-dimensional Hilbert space coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic terms. It turns out that in dimension two both are also NP-complete. For higher-dimensional spaces R^d and C^d with d>2 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory; and extends the still relatively scarce family of NP_R-complete problems with one perhaps closest in spirit to the classical Cook-Levin Theorem. Our investigations on the dimensions a term is weakly/strongly satisfiable in lead to satisfiability problems in indefinite finite and finally in infinite dimension. Here, strong satisfiability turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations, full version to extended abstract [HeZi11]

We define a benchmark for definitions of complexity in systems with spatio-temporal dynamics and employ it in the study of Collective Motion. We show that LMC’s complexity displays interesting properties in such systems, while a statistical complexity model (SCM) based on autocorrelation reasonably meets our perception of complexity. However this SCM is not as general as desirable, as it does not merely depend on the system’s Probability Distribution Function. Inspired by the notion of Fisher information, we develop a SCM candidate, which we call the Fisher-gradient complexity, which exhibits nice properties from the viewpoint of our benchmark.

In the present work, we follow in chronological order the ideas, contributions and discoveries of the greatest Russian mathematician Andrei Kolmogorov in Computer Science. We interpret such Kolmogorov's concepts as algorithm, complexity, komputer mathematics, machine, in the context of the state-of-the art information theories and technologies. We conclude that in broad sense these theories and technologies follow the ways sketched and predicted by Kolmogorov about half century ago.

The trace distance between two quantum states, $\rho$ and $\sigma$, is an operationally meaningful quantity in quantum information theory. However, in general it is difficult to compute, involving the diagonalization of $\rho - \sigma$. In contrast, the Hilbert-Schmidt distance can be computed without diagonalization, although it is less operationally significant. Here, we relate the trace distance and the Hilbert-Schmidt distance with a bound that is particularly strong when either $\rho$ or $\sigma$ is low rank. Our bound is stronger than the bound one could obtain via the norm equivalence of the Frobenius and trace norms. We also consider bounds that are useful not only for low-rank states but also for low-entropy states. Our results have relevance to quantum information theory, quantum algorithms design, and quantum complexity theory., Comment: 6 pages, 1 figure

We consider the quantum complexity of computing Schatten $p$-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating $\text{Tr}\, (|A|^p)$ for a log-local $n$-qubit Hamiltonian $A$ and $p=\text{poly}(n)$, up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph., 28 pages

Part 2: Track B: Logic, Semantics, Specification and Verification; International audience; In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k ≥ 0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum $k$-SAT problem, each constraint is specified by a $k$-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum $k$-SAT with $k\geq 4$ is QMA$_1$-complete [S. Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT, eprint arXiv:quant-ph/0602108, 2006]. Quantum 3-SAT was known to be contained in QMA$_1$ [Bravyi, 2006], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA$_1$-hard, and therefore complete for this complexity class.

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA$_1$.

Bit commitment schemes are at the basis of modern cryptography. Since information-theoretic security is impossible both in the classical and the quantum regime, we need to look at computationally secure commitment schemes. In this paper, we study worst-case complexity assumptions that imply quantum bit-commitment schemes. First, we show that QSZK not included in QMA implies a computationally hiding and statistically binding auxiliary-input quantum commitment scheme. Additionally, we give auxiliary-input commitment schemes using quantum advice that depend on the much weaker assumption that QIP is not included in QMA (which is weaker than PSPACE not included in PP). Finally, we find a quantum oracle relative to which honest-verifier QSZK is not contained in QCMA, the class of languages that can be verified using a classical proof in quantum polynomial time., v2 30p

The state complexity of basic operations on regular languages considering complete deterministic finite automata (DFA) has been extensively studied in the literature. But, if incomplete DFAs are considered, transition complexity is also a significant measure. In this paper we study the incomplete (deterministic) state and transition complexity of some operations for regular and finite languages. For regular languages we give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al. For finite languages, we correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right operand is larger than the left one. We also present some experimental results to test the behavior of those operations on the average case, and we conjecture that for many operations and in practical applications the worst-case complexity is seldom reached.

Since the Shor algorithm showed that a quantum algorithm can efficiently calculate discrete log-arithms and factorize integers, it has been used to break the RSA, EIGamal, and ECC classical public key cryptosystems. This is therefore a significant issue in the context of ensuring communication security over in-secure channels. In this paper, we prove that there are no polynomial-size quantum circuits that can compute all Boolean functions (of which there are 22 n cases) in the standard quantum oracle model. Based on this, we propose the notion of data complexity under a quantum environment and suggest that it can be used as a condition for post-quantum computation. It is generally believed that NP-complete problems cannot be solved in polynomial time even with quantum computers. Therefore, a public key cryptosystem and signature scheme based on the difficulty of NP-complete problems and the notion of data complexity are presented here. Finally, we analyze the security of the proposed encryption and signature schemes.

Thirty years after the introduction of Valiant's PAC-learning framework in 1984, proving sharp sample complexity bounds in the standard, realizable framework is still an open problem. This is true for general concept classes but also for most natural families of classes. In this letter we will give sharp bounds on the sample complexity of PAC-learning intersection-closed classes. Our result settles an open problem posed by Auer and Ortner and supports a conjecture by Warmuth about the true sample complexity and the optimal PAC-learning algorithm for general classes.Furthermore this letter demonstrates a useful application of the disagreement coefficient-a complexity measure developed for agnostic learning by Gine and Koltchinskii based on the work of Alexander and, independently, by Hanneke-in the realizable PAC-learning framework. The optimal upper bound for learning intersection-closed concept classes.Proves an open question by Auer and Ortner and supports a conjecture by Warmuth.An improved upper bound on the sample complexity in PAC-learning.Comparison between different variants of disagreement coefficients.An application of the disagreement coefficient in realizable PAC-learning.

With the explosion of big data, higher requirements for computational efficiency have emerged. Compared with classical computing, quantum computing possesses quantum parallelism due to the unique nature of quantum systems. It has been found that many classical algorithms can be accelerated using quantum computing. In addition to factorizing a large integer, quantum computers can be used for data processing and analysis. In recent years, two frontiers, i.e., big data and quantum computing have begun to merge. Though practical quantum computers have not yet been built, theoretical studies have made some important progress. In this review, we introduce the basic principles of quantum computing. As a representative example, we describe the Grover search algorithm and its important generalizations. Quantum machine learning is the entry point for the integration of big data with quantum computation. We review in detail, the applications of quantum computation in data mining, the main application of machine learning. Other aspects of quantum computing in big data are also briefly summarized.

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding what is feasible. In this chapter I argue that the science of quantum computing illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact.

Brief consideration is given to some properties of three measures of complexity based on the length of minimal descriptive programs. Although the measures explicitly deal with finite sequences, the complexity of an infinite sequence can be regarded as a function mapping each positive integer n to the complexity of the initial segment of length n. Some properties of a complexity hierarchy of infinite sequences with respect to one of the measures is considered.

Simulating quantum algorithms is a hard problem on classical computers, it usually needs exponential time and space. Viamontes et al. proposed a new data structure the Quantum Information Decision Diagram (QuIDD) to overcome this problem and implemented it in the QuIDDPro software. Using this structure several algorithms can be simulated on classical computers with polynomial time and space. In this paper we suggest further improvement and analyse in detail its behavior on Grover’s search algorithm.