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:1503.08545

Limiting the complexity of quantum states: a toy theory

Valerio Scarani

Published Mar 30, 2015• 0 citations
arXivHTMLPDF

Abstract

This paper discusses a restriction of quantum theory, in which very complex states would be excluded. The toy theory is phrased in the language of the circuit model for quantum computing, its key ingredient being a limitation on the number of interactions that \textit{each} qubit may undergo. As long as one stays in the circuit model, the toy theory is consistent and may even match what we shall be ever able to do in a controlled laboratory experiment. The direct extension of the restriction beyond the circuit model conflicts with observed facts: the possibility of restricting the complexity of quantum state, while saving phenomena, remains an open question.

DOI
10.48550/arxiv.1503.08545

Related papers

How to control decoherence and entanglement in quantum complex systems?

V. M. Akulin, Gershon Kurizki, Daniel A. Lidar

Theory and experiment have not fully resolved the apparent dichotomy , which has agonized physics for the past eighty years: on the one hand, the description of microsystems by quantum mechanics and, on the other, the description of macrosystems by classical dynamics or statistical mechanics. Derivations of the time-irreversible Liouville equation for an open quantum system, based on projecting out its environment, have narrowed the gap between the quantum and classical descriptions. Yet our `classical' intuition continues to be confronted by quantum-mechanical results like the Einstein--Podolsky--Rosen paradox that challenges the classical notion of locality, or the quantum Zeno effect which suggests that the isolation of a system is not the only way to preserve its quantum state. There are two key concepts in any discussion of such issues. The first, which is responsible for the most salient nonclassical properties, is entanglement , that is partial or complete correlation or, more generally, inseparability of the elements comprising a quantum ensemble . Even after their interaction has ceased, this inseparability, originating from their past interaction, can affect the state of one element when another element is subject to a nonunitary action, such as its measurement, tracing- out, or thermalization. The second key concept is decoherence of open quantum systems, which is the consequence of their entanglement with their environment, a `meter' or a thermal `reservoir', followed by the tracing-out of the latter. Despite new insights into entanglement and decoherence, there are still no complete, unequivocal answers to the fundamental questions of the transition from quantal to classical behaviour: how do irreversibility and classicality emerge from unitarity as systems and their environments become increasingly complex ? At what stage does system--meter entanglement give rise to a classical readout of the meter? Is there an upper limit on the size or complexity of systems displaying entanglement? Major developments have opened new vistas into controlled entanglement , which is the resource of quantum information processing. However, these developments have mainly focused on ensembles of simple two- and three-level systems that are thoroughly isolated from their environments. Treatments of coherence in quantum computing have mostly assumed that only a single or a few the elements of the quantum ensemble may simultaneously undergo an uncontrolled intervention---a quantum error. Decoherence-control protocols for more general types of errors are still incomplete. In order to resolve the outstanding issues of the quantum--classical transition, and study the control of entanglement and decoherence without the foregoing restrictions, we must venture into the domain of Quantum Complex Systems (QUACS), either consisting of a large number of inseparable elements or having many coupled degrees of freedom. Our conviction is that fundamental understanding and manipulation of entanglement within QUACS or their entanglement with the environment or a meter, call for the creation of a new conceptual framework or paradigm, that would encompass phenomena common to cold atoms in laser fields, large molecules, Josephson junctions, quantum gases and solids, with the view of employing these systems for quantum information processing and computing. Progress within this paradigm should allow us to answer the questions: does entanglement play an essential role in the evolution of large collections of complex systems? What are the size and complexity limits of systems and ensembles still controllable by an external intervention? What are the most appropriate decoherence protection schemes and control algorithms? This special issue addresses the challenge of understanding in depth and manipulating the basic quantum properties of optical, atomic, molecular and condensed-matter QUACS, and large ensembles thereof. In view of the interdisciplinary character of this issue, we find it expedient to look at the presented articles not only according to the physical objects they describe, but also from a unifying standpoint. Several unifying themes may be discerned: memory effects in dephasing and relaxation; protection of quantum information by its distribution throughout the ensemble; control of decoherence and entanglement by time-dependent interventions or measurements; manifestations of entanglement in scattering off statistical ensembles; measurment-induced dynamics. The concerted discussion of the topics outlined above should help us advance the new paradigm that addresses our abilities to diagnose and manipulate the entangled states of complex quantum objects and their robustness against decoherence. These abilities are required for quantum information (QI) applications in matter--wave interferometry in molecular, semiconducting or superconducting systems. On the fundamental level, this book may help establish the notion of dynamical information exchange between quantum systems and chart in detail the route from unitarity to classicality. Further developments within the outlined paradigm should yield novel, advantageous QI processing schemes and high-sensitivity interferometers, owing to decoherence suppression and effective control of many degrees of freedom. In the long run, these strategies may prove to be the first step towards the (hitherto unattempted) use of entanglement in nanotechnology, metrology and chemistry, with potentially remarkable novel applications.

Journal of Physics B Atomic Molecular and Optical Physics•Apr 18, 2007•2 citations

Quantum State Complexity in Computationally Tractable Quantum Circuits

Jason Iaconis

Using an approach based on the synergy between the techniques of quantum information and many-body physics, a study of quantum circuits indicates that the quality of being classically simulated can coexist with having high complexity.

arXiv:2009.05512•PRX Quantum•Feb 23, 2021•38 citations

Unconditional and exponentially large violation of classicality

Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans +2 more

Testing the predictions of quantum mechanics has been one of the main experimental endeavors for decades. Recent advancements in technology led to a number of demonstrations which test non-classicality via specific computational tasks. Limitations of these experiments include dependence on complexity theory assumptions, susceptibility to hardware noise and inefficient verification, raising questions about their scalability. We propose to test non-classicality using a game based on complement sampling, an efficiently verifiable problem that achieves the largest possible separation between quantum and classical computation when both input and output represent samples from probability distributions. When restricting the input to instances inspired by the Bernstein-Vazirani problem, our game admits an exponentially large violation of classicality unconditionally, i.e. without relying on computational hardness assumptions. We demonstrate the game on Quantinuum System Model H2 trapped-ion quantum computers, with experiments consisting of thousands of different circuits on up to 55 qubits. The observed scores can be explained by a systematic adoption of a quantum strategy, further corroborating the quantum nature of the hardware in an efficient and scalable way.

quant-pharXiv:2511.11008•Nature Communications•Nov 17, 2025•0 citations

Toys for quantum computation

A. Keimpema

A formal definition of a computer would be that it is a system whose mechanical time evolution is used to do computation. A computer just like an dassical computer has the bit as unit of information, in the context of computation called a qubit. Because a computer operates in the mechanical domain, a collection of qubits can hold not one value but a superposition of many values. This quantum parallelism is a fundamental advantage that a computer has over a classical computer and algorithms that exploit this feature can be significantly faster than any classical algorithm. That said, the number of algorithm available today is small and their usefulness is limited. Several hardware implementations of computers have been made. Unfortunately existing hardware technology limits the size of these experimental computers to just a few qubits. In chapter 1 we review the field of computation and introduce an interesting new hardware candidate, dubbed the quantum by its creators. This toy is a metallic ring with three embedded ferromagnets. In certain configurations these ferromagnets can induce a current in the ring. In fact the configurations that will or will not induce a current can be identified with an CNOT(XOR) gate. This motivates us to explore the viability of this system using computer simulations. The toy system is related to a long standing problem in condensed matter physics, that of the persistent currents. When a small metal ring is placed in a static magnetic field, the magnetic field will induce a current in the ring. Persistent currents have been observed experimentally and a great discrepancy between theory and experiment was found. The qualitative features of the phenomenon are explained well by theory, but the size of the current measured was one to two orders of magnitude larger then that predicted by experiment. As a second object of this master thesis we will study persistent current numerically using a simple fight-binding model and compare this to existing theory and experiment. In chapter two we review the field of persistent currents and we give an overview of existing theory. To make a simulation tool of a mechanical system basically means that we have to solve the Schrodinger equation numerically. In chapter 3 we briefly discuss two such method, namely the Cranck- Nicholson method and the Suzuki-Trotter method. We will use the latter in our simulation tool. The actual simulation is described in chapter 4. In this chapter we detail the development of the numerical tool and show its correctness at each step. We find that the simulations qualitatively show the same features as we would expect theoretically and experimentally. The size of current is a different matter. When compared to experiment we find that although our results are of the same order of magnitude we cannot make an accurate fit to the experimental data using our simple model. In the last chapter we investigate the properties of the toy system by computer simulations. We will explore its application for computation and its use as a measurement device. Upon investigating how a toy system can be used in a circuit, we find that the toy is not useful for computation. We then focus on the second application1 that of a measurement device. The idea being that we can exploit the dependence of the induced current to the direction of the embedded ferromagnets. To verify if such a scheme will work, we need to investigate if we can reproduce the theoretical values of the induced current. We found major discrepancies between theory and our simulations. We found for instance that the induced current has an erratic dependence on the electron density. We then split our investigation between the single electron case and the half-filled case found in most metals. The single electron case only matches the theory qualitatively. We find that indeed such a single electron system can be build and be used as a measurement device. In the half-filled case we find that the dependence of the current on the various parameters is so erratic that we condude that according to our simulations, a metallic toy could not be used as a measurement device. An explanation for the difference between theory and our simulations could unfortunately not be found. To investigate this we would have to repeat the original calculations, which is outside the scope of this master thesis

•Jan 1, 2004•0 citations

Adiabatic computation: A toy model

Pedro Ribeiro, Rémy Mosseri

We discuss a toy model for adiabatic quantum computation which displays some phenomenological properties expected in more realistic implementations. This model has two free parameters: the adiabatic evolution parameter $s$ and the $\ensuremath{\alpha}$ parameter, which emulates many-variable constraints in the classical computational problem. The proposed model presents, in the $s\text{\ensuremath{-}}\ensuremath{\alpha}$ plane, a line of first-order quantum phase transition that ends at a second-order point. The relation between computation complexity and the occurrence of quantum phase transitions is discussed. We analyze the behavior of the ground and first excited states near the quantum phase transition, the gap, and the entanglement content of the ground state.

arXiv:quant-ph/0606194•Physical Review A•Oct 26, 2006•5 citations

IQP circuits for 2-Forrelation

Quentin Buzet, André Chailloux

The $2$-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating $\mathsf{BQP}$ and $\mathsf{PH}$ relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that $2$-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($\mathsf{IQP}$) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed $2$-Forrelation can be solved by a classical random choice between two one-query $\mathsf{IQP}$ circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle $O$ such that $\mathsf{IQP}^O \not\subseteq \mathsf{PH}^O$, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between $\mathsf{IQP}$ and $\mathsf{DQC}_1$. We prove Fourier growth bounds for multi-query $\mathsf{IQP}$ circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted $\mathsf{IQP}$ model. The key ingredient is an algebraic identity of the quadratic function $Q(x) = \sum_{i < j} x_ix_j$ that allows extracting inner-product phases within an $\mathsf{IQP}$ circuit.

quant-pharXiv:2604.15248•Apr 17, 2026•0 citations
This paper discusses a restriction of quantum theory, in which very complex states would be excluded. The toy theory is phrased in the language of the circuit model for quantum computing, its key ingredient being a limitation on the number of interactions that \textit{each} qubit may undergo. As long as one stays in the circuit model, the toy theory is consistent and may even match what we shall be ever able to do in a controlled laboratory experiment. The direct extension of the restriction beyond the circuit model conflicts with observed facts: the possibility of restricting the complexity of quantum state, while saving phenomena, remains an open question.
Theory and experiment have not fully resolved the apparent dichotomy , which has agonized physics for the past eighty years: on the one hand, the description of microsystems by quantum mechanics and, on the other, the description of macrosystems by classical dynamics or statistical mechanics. Derivations of the time-irreversible Liouville equation for an open quantum system, based on projecting out its environment, have narrowed the gap between the quantum and classical descriptions. Yet our `classical' intuition continues to be confronted by quantum-mechanical results like the Einstein--Podolsky--Rosen paradox that challenges the classical notion of locality, or the quantum Zeno effect which suggests that the isolation of a system is not the only way to preserve its quantum state. There are two key concepts in any discussion of such issues. The first, which is responsible for the most salient nonclassical properties, is entanglement , that is partial or complete correlation or, more generally, inseparability of the elements comprising a quantum ensemble . Even after their interaction has ceased, this inseparability, originating from their past interaction, can affect the state of one element when another element is subject to a nonunitary action, such as its measurement, tracing- out, or thermalization. The second key concept is decoherence of open quantum systems, which is the consequence of their entanglement with their environment, a `meter' or a thermal `reservoir', followed by the tracing-out of the latter. Despite new insights into entanglement and decoherence, there are still no complete, unequivocal answers to the fundamental questions of the transition from quantal to classical behaviour: how do irreversibility and classicality emerge from unitarity as systems and their environments become increasingly complex ? At what stage does system--meter entanglement give rise to a classical readout of the meter? Is there an upper limit on the size or complexity of systems displaying entanglement? Major developments have opened new vistas into controlled entanglement , which is the resource of quantum information processing. However, these developments have mainly focused on ensembles of simple two- and three-level systems that are thoroughly isolated from their environments. Treatments of coherence in quantum computing have mostly assumed that only a single or a few the elements of the quantum ensemble may simultaneously undergo an uncontrolled intervention---a quantum error. Decoherence-control protocols for more general types of errors are still incomplete. In order to resolve the outstanding issues of the quantum--classical transition, and study the control of entanglement and decoherence without the foregoing restrictions, we must venture into the domain of Quantum Complex Systems (QUACS), either consisting of a large number of inseparable elements or having many coupled degrees of freedom. Our conviction is that fundamental understanding and manipulation of entanglement within QUACS or their entanglement with the environment or a meter, call for the creation of a new conceptual framework or paradigm, that would encompass phenomena common to cold atoms in laser fields, large molecules, Josephson junctions, quantum gases and solids, with the view of employing these systems for quantum information processing and computing. Progress within this paradigm should allow us to answer the questions: does entanglement play an essential role in the evolution of large collections of complex systems? What are the size and complexity limits of systems and ensembles still controllable by an external intervention? What are the most appropriate decoherence protection schemes and control algorithms? This special issue addresses the challenge of understanding in depth and manipulating the basic quantum properties of optical, atomic, molecular and condensed-matter QUACS, and large ensembles thereof. In view of the interdisciplinary character of this issue, we find it expedient to look at the presented articles not only according to the physical objects they describe, but also from a unifying standpoint. Several unifying themes may be discerned: memory effects in dephasing and relaxation; protection of quantum information by its distribution throughout the ensemble; control of decoherence and entanglement by time-dependent interventions or measurements; manifestations of entanglement in scattering off statistical ensembles; measurment-induced dynamics. The concerted discussion of the topics outlined above should help us advance the new paradigm that addresses our abilities to diagnose and manipulate the entangled states of complex quantum objects and their robustness against decoherence. These abilities are required for quantum information (QI) applications in matter--wave interferometry in molecular, semiconducting or superconducting systems. On the fundamental level, this book may help establish the notion of dynamical information exchange between quantum systems and chart in detail the route from unitarity to classicality. Further developments within the outlined paradigm should yield novel, advantageous QI processing schemes and high-sensitivity interferometers, owing to decoherence suppression and effective control of many degrees of freedom. In the long run, these strategies may prove to be the first step towards the (hitherto unattempted) use of entanglement in nanotechnology, metrology and chemistry, with potentially remarkable novel applications.
Testing the predictions of quantum mechanics has been one of the main experimental endeavors for decades. Recent advancements in technology led to a number of demonstrations which test non-classicality via specific computational tasks. Limitations of these experiments include dependence on complexity theory assumptions, susceptibility to hardware noise and inefficient verification, raising questions about their scalability. We propose to test non-classicality using a game based on complement sampling, an efficiently verifiable problem that achieves the largest possible separation between quantum and classical computation when both input and output represent samples from probability distributions. When restricting the input to instances inspired by the Bernstein-Vazirani problem, our game admits an exponentially large violation of classicality unconditionally, i.e. without relying on computational hardness assumptions. We demonstrate the game on Quantinuum System Model H2 trapped-ion quantum computers, with experiments consisting of thousands of different circuits on up to 55 qubits. The observed scores can be explained by a systematic adoption of a quantum strategy, further corroborating the quantum nature of the hardware in an efficient and scalable way.
A formal definition of a computer would be that it is a system whose mechanical time evolution is used to do computation. A computer just like an dassical computer has the bit as unit of information, in the context of computation called a qubit. Because a computer operates in the mechanical domain, a collection of qubits can hold not one value but a superposition of many values. This quantum parallelism is a fundamental advantage that a computer has over a classical computer and algorithms that exploit this feature can be significantly faster than any classical algorithm. That said, the number of algorithm available today is small and their usefulness is limited. Several hardware implementations of computers have been made. Unfortunately existing hardware technology limits the size of these experimental computers to just a few qubits. In chapter 1 we review the field of computation and introduce an interesting new hardware candidate, dubbed the quantum by its creators. This toy is a metallic ring with three embedded ferromagnets. In certain configurations these ferromagnets can induce a current in the ring. In fact the configurations that will or will not induce a current can be identified with an CNOT(XOR) gate. This motivates us to explore the viability of this system using computer simulations. The toy system is related to a long standing problem in condensed matter physics, that of the persistent currents. When a small metal ring is placed in a static magnetic field, the magnetic field will induce a current in the ring. Persistent currents have been observed experimentally and a great discrepancy between theory and experiment was found. The qualitative features of the phenomenon are explained well by theory, but the size of the current measured was one to two orders of magnitude larger then that predicted by experiment. As a second object of this master thesis we will study persistent current numerically using a simple fight-binding model and compare this to existing theory and experiment. In chapter two we review the field of persistent currents and we give an overview of existing theory. To make a simulation tool of a mechanical system basically means that we have to solve the Schrodinger equation numerically. In chapter 3 we briefly discuss two such method, namely the Cranck- Nicholson method and the Suzuki-Trotter method. We will use the latter in our simulation tool. The actual simulation is described in chapter 4. In this chapter we detail the development of the numerical tool and show its correctness at each step. We find that the simulations qualitatively show the same features as we would expect theoretically and experimentally. The size of current is a different matter. When compared to experiment we find that although our results are of the same order of magnitude we cannot make an accurate fit to the experimental data using our simple model. In the last chapter we investigate the properties of the toy system by computer simulations. We will explore its application for computation and its use as a measurement device. Upon investigating how a toy system can be used in a circuit, we find that the toy is not useful for computation. We then focus on the second application1 that of a measurement device. The idea being that we can exploit the dependence of the induced current to the direction of the embedded ferromagnets. To verify if such a scheme will work, we need to investigate if we can reproduce the theoretical values of the induced current. We found major discrepancies between theory and our simulations. We found for instance that the induced current has an erratic dependence on the electron density. We then split our investigation between the single electron case and the half-filled case found in most metals. The single electron case only matches the theory qualitatively. We find that indeed such a single electron system can be build and be used as a measurement device. In the half-filled case we find that the dependence of the current on the various parameters is so erratic that we condude that according to our simulations, a metallic toy could not be used as a measurement device. An explanation for the difference between theory and our simulations could unfortunately not be found. To investigate this we would have to repeat the original calculations, which is outside the scope of this master thesis
We discuss a toy model for adiabatic quantum computation which displays some phenomenological properties expected in more realistic implementations. This model has two free parameters: the adiabatic evolution parameter sss and the $\ensuremath{\alpha}$ parameter, which emulates many-variable constraints in the classical computational problem. The proposed model presents, in the $s\text{\ensuremath{-}}\ensuremath{\alpha}$ plane, a line of first-order quantum phase transition that ends at a second-order point. The relation between computation complexity and the occurrence of quantum phase transitions is discussed. We analyze the behavior of the ground and first excited states near the quantum phase transition, the gap, and the entanglement content of the ground state.
The 222-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP\mathsf{BQP}BQP and PH\mathsf{PH}PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 222-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP\mathsf{IQP}IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 222-Forrelation can be solved by a classical random choice between two one-query IQP\mathsf{IQP}IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle OOO such that IQPO⊈PHO\mathsf{IQP}^O \not\subseteq \mathsf{PH}^OIQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP\mathsf{IQP}IQP and DQC1\mathsf{DQC}_1DQC1​. We prove Fourier growth bounds for multi-query IQP\mathsf{IQP}IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted IQP\mathsf{IQP}IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixjQ(x) = \sum_{i < j} x_ix_jQ(x)=∑i<j​xi​xj​ that allows extracting inner-product phases within an IQP\mathsf{IQP}IQP circuit.