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:quant-ph/0408035 · Physical Review A

Quantum computing and hidden variables

Scott Aaronson

Published Mar 18, 2005• 54 citations
arXivHTMLPDF

Abstract

This paper initiates the study of hidden variables from a quantum computing perspective. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list five axioms that we might want such a theory to satisfy and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we propose a new hidden-variable theory based on network flows. In a second part of the paper, we show that if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom, we could solve the graph isomorphism problem in polynomial time, and could search an $N$-item database using $O({N}^{1∕3})$ queries, as opposed to $O({N}^{1∕2})$ queries with Grover's search algorithm. On the other hand, the ${N}^{1∕3}$ bound is optimal, meaning that we could probably not solve $\mathrm{NP}$-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.

DOI
10.1103/physreva.71.032325

Related papers

Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories

Scott Aaronson

This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also search an N-item database using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.

arXiv:quant-ph/0408119•Aug 19, 2004•10 citations

Quantum Computing and Dynamical Quantum Models

Scott Aaronson

A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a distribution over classical histories of a quantum state. We study what can be computed by sampling from that distribution, i.e., by examining an observer's entire history. We show that, relative to an oracle, one can solve problems in polynomial time that are intractable even for quantum computers; and can search an N-element list in order N^{1/3} steps (though not fewer).

arXiv:quant-ph/0205059•May 11, 2002•2 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations

Robustness of Hidden-Variable Theories and Matrix Scaling

Giulio Malavolta, Harold Nieuwboer, Akshay Ramachandran +1 more

Motivated by quantum foundations and complexity theory, Aaronson formalized a hidden-variable theory inspired by a proposal by Schrödinger. To any quantum state and unitary, this Schrödinger theory assigns a joint probability distribution via the Sinkhorn algorithm: rescale the columns and rows of the entrywise modulus of the unitary so that the marginals match the Born rule for the initial and final quantum states, respectively. He conjectured that this map is robust, i.e., inverse polynomially small perturbations in the inputs lead to inverse polynomially small perturbations of the joint distribution, which is important for complexity theoretic applications. We present a counterexample to this conjecture: We construct a pure state and two unitaries that are exponentially close, yet the joint probability distributions assigned by the Schrödinger theory differ by at least an inverse-linear term in at least one entry, and by a constant in total variation distance. We also propose a modified version of Schrödinger's theory that satisfies robustness, while retaining all of its other desirable properties. This yields a complete picture of which axioms of Aaronson can be simultaneously satisfied by hidden-variable theories.

quant-pharXiv:2609.14519•Sep 15, 2026•0 citations

Can Hidden Variables Theories Meet Quantum Computation?

Koji Nagata, Tadao Nakamura

We study the relation between hidden variables theories and quantum computation.We discuss an inconsistency between a hidden variables theory and controllability of quantum computation.To derive the inconsistency, we use the maximum value of the square of an expected value.We propose a solution of the problem by using new hidden variables theory.Also we discuss an inconsistency between hidden variables theories and the double-slit experiment as the most basic experiment in quantum mechanics.This experiment can be an easy detector to Pauli observable.We cannot accept hidden variables theories to simulate the double-slit experiment in a specific case.Hidden variables theories may not depicture quantum detector.This is a quantum measurement theoretical profound problem.

OALib•Jan 1, 2015•0 citations
This paper initiates the study of hidden variables from a quantum computing perspective. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list five axioms that we might want such a theory to satisfy and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we propose a new hidden-variable theory based on network flows. In a second part of the paper, we show that if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom, we could solve the graph isomorphism problem in polynomial time, and could search an NNN-item database using O(N1∕3)O({N}^{1∕3})O(N1∕3) queries, as opposed to O(N1∕2)O({N}^{1∕2})O(N1∕2) queries with Grover's search algorithm. On the other hand, the N1∕3{N}^{1∕3}N1∕3 bound is optimal, meaning that we could probably not solve NP\mathrm{NP}NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.
This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also search an N-item database using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.
A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a distribution over classical histories of a quantum state. We study what can be computed by sampling from that distribution, i.e., by examining an observer's entire history. We show that, relative to an oracle, one can solve problems in polynomial time that are intractable even for quantum computers; and can search an N-element list in order N^{1/3} steps (though not fewer).
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.
Motivated by quantum foundations and complexity theory, Aaronson formalized a hidden-variable theory inspired by a proposal by Schrödinger. To any quantum state and unitary, this Schrödinger theory assigns a joint probability distribution via the Sinkhorn algorithm: rescale the columns and rows of the entrywise modulus of the unitary so that the marginals match the Born rule for the initial and final quantum states, respectively. He conjectured that this map is robust, i.e., inverse polynomially small perturbations in the inputs lead to inverse polynomially small perturbations of the joint distribution, which is important for complexity theoretic applications. We present a counterexample to this conjecture: We construct a pure state and two unitaries that are exponentially close, yet the joint probability distributions assigned by the Schrödinger theory differ by at least an inverse-linear term in at least one entry, and by a constant in total variation distance. We also propose a modified version of Schrödinger's theory that satisfies robustness, while retaining all of its other desirable properties. This yields a complete picture of which axioms of Aaronson can be simultaneously satisfied by hidden-variable theories.
We study the relation between hidden variables theories and quantum computation.We discuss an inconsistency between a hidden variables theory and controllability of quantum computation.To derive the inconsistency, we use the maximum value of the square of an expected value.We propose a solution of the problem by using new hidden variables theory.Also we discuss an inconsistency between hidden variables theories and the double-slit experiment as the most basic experiment in quantum mechanics.This experiment can be an easy detector to Pauli observable.We cannot accept hidden variables theories to simulate the double-slit experiment in a specific case.Hidden variables theories may not depicture quantum detector.This is a quantum measurement theoretical profound problem.