This paper explores the problem of quantum measurement complexity. In computability theory, the complexity of a problem is determined by how long it takes an effective algorithm to solve it. This complexity may be compared to the difficulty for a hypothetical oracle machine, the output of which may be verified by a computable function but cannot be simulated on a physical machine. We define a quantum oracle machine for measurements as one that can determine the state by examining a single copy. The complexity of measurement for a realizable machine will then be respect to the number of copies of the state that needs to be examined. A quantum oracle cannot perform simultaneous exact measurement of conjugate variables, although approximate measurement may be performed as circumscribed by the Heisenberg uncertainty relations. When considering the measurement of a variable, there might be residual uncertainty if the number of copies of the variable is limited. Specifically, we examine the quantum measurement complexity of linear polarization of photons that is used in several quantum cryptography schemes and we present a relation using information theoretic arguments. The idea of quantum measurement complexity is likely to find uses in measurements in biological systems.
This paper explores the problem of quantum measurement complexity. In computability theory, the complexity of a problem is determined by how long it takes an effective algorithm to solve it. This complexity may be compared to the difficulty for a hypothetical oracle machine, the output of which may be verified by a computable function but cannot be simulated on a physical machine. We define a quantum oracle machine for measurements as one that can determine the state by examining a single copy. The complexity of measurement for a realizable machine will then be respect to the number of copies of the state that needs to be examined. A quantum oracle cannot perform simultaneous exact measurement of conjugate variables, although approximate measurement may be performed as circumscribed by the Heisenberg uncertainty relations. When considering the measurement of a variable, there might be residual uncertainty if the number of copies of the variable is limited. Specifically, we examine the quantum measurement complexity of linear polarization of photons that is used in several quantum cryptography schemes and we present a relation using information theoretic arguments. The idea of quantum measurement complexity is likely to find uses in measurements in biological systems.
This paper explores the problem of quantum measurement complexity. In computability theory, the complexity of a problem is determined by how long it takes an effective algorithm to solve it. This complexity may be compared to the difficulty for a hypothetical oracle machine, the output of which may be verified by a computable function but cannot be simulated on a physical machine. We define a quantum oracle machine for measurements as one that can determine the state by examining a single copy. The complexity of measurement for a realizable machine will then be respect to the number of copies of the state that needs to be examined. A quantum oracle cannot perform simultaneous exact measurement of conjugate variables, although approximate measurement may be performed as circumscribed by the Heisenberg uncertainty relations. When considering the measurement of a variable, there might be residual uncertainty if the number of copies of the variable is limited. Specifically, we examine the quantum measurement complexity of linear polarization of photons that is used in several quantum cryptography schemes and we present a relation using information theoretic arguments. The idea of quantum measurement complexity is likely to find uses in measurements in biological systems.
From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that , where is a classical complexity class (known to be included in , hence ). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterized by local measurements), efficient computations are contained in . This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, , is equal to . Given only the assumption of tomographic locality, the inclusion in still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativized complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a 'classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include .
This paper explores the application of quantum information entropy to the theory of computational complexity. We posit that quantum information entropy can serve as a novel metric for quantifying the complexity of quantum algorithms and their associated resource requirements. The core argument is that traditional measures of computational complexity, such as circuit depth or quantum gate count, often fail to fully capture the inherent challenges posed by quantum systems. By leveraging entropy, we aim to provide a more nuanced and potentially more accurate assessment of the difficulty of quantum computations. This work introduces a framework for analyzing quantum algorithms through the lens of information entropy, exploring relationships between algorithmic complexity, entropy generation, and the resources needed to execute these algorithms. Specifically, we examine how entropy can be used to characterize the 'quantumness' of an algorithm and its impact on the overall computational cost. The ultimate goal is to develop a more robust and predictive model for quantum computation, leading to improved algorithm design and resource allocation. ---
In this paper, we consider the following problem (the subroutine problem).If the operation performed by an oracle is efficiently computable, can a non-oracle quantum computer simulate a quantum computer with this oracle efficiently ?Bennett et al. and Aharonov et al. respectively solved the subroutine problem when their oracles evaluate deterministic and probabilistic functions.However, both of them considered only the case where machines enter the query mode deterministically.We extend the notion of an oracle of a quantum computer to a device for performing a unitary transformation, and solve the subroutine problem in the general setting where a query state and a nonquery state may superpose.Using this result, we show that EQP and BQP are robust in the general setting, which extends the robustness of BQP shown by Bennett et al. in the case where machines enter the query mode deterministically.Moreover, we prove the robustness of ZQP by improving.themethod of Bennett et al. employed for the above BQP result.
Quantum query complexity studies the number of queries needed to learn some property of a black box. A closely related question is how well an algorithm can succeed with this learning task using only a fixed number of queries. In this work, we propose measuring an algorithm's performance using the mutual information between the output and the actual value. The task of optimizing this mutual information using a single query is similar to a basic task of quantum communication, where one attempts to maximize the mutual information of the sender and receiver. We make this analogy precise by splitting the algorithm between two agents, obtaining a communication protocol. The oracle's target property plays the role of a message that Alice encodes into a quantum state, which is subsequently sent over to Bob. The first part of the algorithm performs this encoding, and the second part measures the state and aims to deduce the message from the outcome. Moreover, we formally consider the oracle as a separate subsystem, whose state records the unknown oracle identity. Within this construction, Bob's optimal measurement basis minimizes the quantum correlations between the two subsystems. We also find a lower bound on the mutual information, which is related to quantum coherence. These results extend to multiple-query nonadaptive algorithms. As a result, we describe the optimal nonadaptive algorithm that uses at most a fixed number of queries, for any oracle classification problem. Crucially, this mutual-information perspective was shown elsewhere [A. Levi ., ] to have practical utility for algorithmic design, providing the theoretical foundation to optimize iterative subroutines in hybrid quantum-classical schemes. Within the present work, we apply this framework to analyze the stage-by-stage information flow and track partial progress in several standard quantum algorithms, including the Deutsch-Jozsa, Bernstein-Vazirani, and Shor-Kitaev algorithms.
This work presents a study of Kolmogorov complexity for general quantum states from the perspective of deterministic-control quantum Turing Machines (dcq-TM). We extend the dcq-TM model to incorporate mixed state inputs and outputs, and define dcq-computable states as those that can be approximated by a dcq-TM. Moreover, we introduce (conditional) Kolmogorov complexity of quantum states and use it to study three particular aspects of the algorithmic information contained in a quantum state: a comparison of the information in a quantum state with that of its classical representation as an array of real numbers, an exploration of the limits of quantum state copying in the context of algorithmic complexity, and study of the complexity of correlations in quantum systems, resulting in a correlation-aware definition for algorithmic mutual information that satisfies symmetry of information property.