Quantum
computation, randomness and chaos

Quantum mechanics has had an
enormous technological and societal impact. To grasp this point, it is
sufficient to cite the invention of the

transistor, perhaps the most remarkable among the countless other applications of quantum mechanics. It is also easy to see the enormous impact of computers on everyday life. The importance of computers is such that it is appropriate to say that we are now living in the information age. This information revolution became possible thanks to the invention of the transistor, that is, thanks to the synergy between computer science and quantum physics.

Today this synergy offers completely new opportunities and promises exciting advances in both fundamental science and technological application. We are referring here to the fact that quantum mechanics can be used to process and transmit information [1]

Miniaturization provides us with an intuitive way of understanding why, in the near future, quantum laws will become important for computation. The electronics industry for computers grows hand-in-hand with the decrease in size of integrated circuits. This miniaturization is necessary to increase

computational power, that is, the number of floating-point operations per second (flops) a computer can perform. The progress in the miniaturization process may be quantified empirically in Moore's law: the number of transistors on a single integrated-circuit chip doubles approximately

every 18-24 months. Extrapolating Moore's law, one would estimate that around the year 2020 we shall reach the atomic size for storing a single bit of

information. At that point, quantum effects will become unavoidably dominant.

Therefore, quantum physics sets fundamental limitations on the size of the circuit components.

The first question under debate is whether it would be more convenient to push the silicon-based transistor to its physical limits or instead to

develop alternative devices, such as quantum dots, single-electron transistors or molecular switches. A common feature of all these devices is that they are at the nanometre length scale, and therefore quantum effects play a crucial role.

So far, we have talked about quantum switches that could substitute silicon-based transistors and possibly be connected together to execute

classical algorithms based on Boolean logic. In this perspective, quantum effects are simply unavoidable corrections that must be taken into

account owing to the nanometre size of the switches. A quantum computer represents a radically different challenge: the aim is to build a machine based on quantum logic, that is, a machine that can process the information and perform logic operations in agreement with the laws of quantum mechanics.

transistor, perhaps the most remarkable among the countless other applications of quantum mechanics. It is also easy to see the enormous impact of computers on everyday life. The importance of computers is such that it is appropriate to say that we are now living in the information age. This information revolution became possible thanks to the invention of the transistor, that is, thanks to the synergy between computer science and quantum physics.

Today this synergy offers completely new opportunities and promises exciting advances in both fundamental science and technological application. We are referring here to the fact that quantum mechanics can be used to process and transmit information [1]

Miniaturization provides us with an intuitive way of understanding why, in the near future, quantum laws will become important for computation. The electronics industry for computers grows hand-in-hand with the decrease in size of integrated circuits. This miniaturization is necessary to increase

computational power, that is, the number of floating-point operations per second (flops) a computer can perform. The progress in the miniaturization process may be quantified empirically in Moore's law: the number of transistors on a single integrated-circuit chip doubles approximately

every 18-24 months. Extrapolating Moore's law, one would estimate that around the year 2020 we shall reach the atomic size for storing a single bit of

information. At that point, quantum effects will become unavoidably dominant.

Therefore, quantum physics sets fundamental limitations on the size of the circuit components.

The first question under debate is whether it would be more convenient to push the silicon-based transistor to its physical limits or instead to

develop alternative devices, such as quantum dots, single-electron transistors or molecular switches. A common feature of all these devices is that they are at the nanometre length scale, and therefore quantum effects play a crucial role.

So far, we have talked about quantum switches that could substitute silicon-based transistors and possibly be connected together to execute

classical algorithms based on Boolean logic. In this perspective, quantum effects are simply unavoidable corrections that must be taken into

account owing to the nanometre size of the switches. A quantum computer represents a radically different challenge: the aim is to build a machine based on quantum logic, that is, a machine that can process the information and perform logic operations in agreement with the laws of quantum mechanics.

Development of quantum algorithms for
dynamical systems

A relevant class of quantum algorithms is the simulation of dynamical systems.

We have proposed [2] a quantum algorithm which uses the number of qubits in an optimal way and efficiently simulates a physical model with rich and complex dynamics described by the quantum sawtooth map.

We have demonstrated that complex dynamics could be simulated already with less than 10 qubits, while 40 qubits would allow one to make computations inaccessible to present-day supercomputers.

Husimi functions for the
sawtooth map in action-angle variables, for n=6 (top left), n=9 (top
right), n=16 qubits (bottom left) and classical Poincare
section (bottom right).

Quantum
computation of dynamical localization

Dynamical localization is one of the most interesting phenomena that characterize the quantum behavior of classically chaotic systems: quantum interference effects suppress classical diffusion leading to exponentially localized wave functions.

We have shown [3] that quantum computers can simulate efficiently the quantum localization of classical chaos. The speed up with respect to classical computation is

quadratic. The localization effect was studied experimentally by the group of David Cory at MIT by emulating the dynamics if the quantum sawtooth map in the perturbative regime on a three-qubit nuclear magnetic resonance quantum information processor (see M.K. Henry, J. Emerson, R. Martinez, and D.G. Cory, Phys. Rev. A 74, 062317 (2006)).

Dynamical localization in the
sawtooth map model simulated using six qubits

Effects
of imperfections on the stability of quantum computation

We have studied the effect of
static imperfections in the quantum computer hardware on
the stability of quantum computation.

We have found that a reliable quantum computation is possible up to a time scale which is polynomial in the number of qubits.

The errors generated by these imperfections are more dangerous than the errors of random noise in gate operations [2].

We have found that a reliable quantum computation is possible up to a time scale which is polynomial in the number of qubits.

The errors generated by these imperfections are more dangerous than the errors of random noise in gate operations [2].

Husimi functions for the sawtooth map in action-angle variables, in the presence of static imperfections, for n=6 (top left), n=9 (top right), n=16 qubits (bottom left) and classical Poincare section (bottom right) in the presence of round-off errors.

Dynamics of entanglement in quantum
computers with imperfections

Objective: understand the time
scales for the stability of entanglement (a key resource for quantum
computation and information) under decoherence and imperfection effects.

We have studied [4] the evolution of the entanglement of formation between two nearest neighbor qubits in a lattice, which initially are maximally entangled or separable.

We have characterized three regimes:

a) Perturbative regime: the entanglement is stable against imperfections

b) Crossever regime: imperfections degrade the concurrence of an initially entangled pair but can also drive a significant entanglement generation

c) Ergodic regime: a pair of qubits becomes entangled with the rest of the lattice and the concurrence of the pair drops to zero

The stability of the entanglement of formation in an operating quantum computer has been investigated in [5].

We have discussed behavior of entanglement across a transition to chaos in [6].

We have studied [4] the evolution of the entanglement of formation between two nearest neighbor qubits in a lattice, which initially are maximally entangled or separable.

We have characterized three regimes:

a) Perturbative regime: the entanglement is stable against imperfections

b) Crossever regime: imperfections degrade the concurrence of an initially entangled pair but can also drive a significant entanglement generation

c) Ergodic regime: a pair of qubits becomes entangled with the rest of the lattice and the concurrence of the pair drops to zero

The stability of the entanglement of formation in an operating quantum computer has been investigated in [5].

We have discussed behavior of entanglement across a transition to chaos in [6].

Concurrence saturation values for
different number of qubits, starting from a Bell state (left) or a
separable state (right)

Entanglement, Bell's inequalities, randomness and the
classical limit

Robust and efficient generator of multipartite entanglement

Since
random states carry a lot of entanglement and entanglement
has no analogue in classical mechanics,
one can conclude that random states are highly non-classical. On the
other hand, for chaotic map the classical limit can be recovered when
the dimension of the Hilbert space diverges, and (ergodic) random
states in a way mimic classical microcanonical density. How can we
reconcile this apparent contradiction? We have considered [7] the detection of entanglement for
random states by means of witness
operators. While the entanglement content of random pure states
is almost maximal, we have shown that, due to the complexity of such
states, the detection of their entanglement is difficult. Moreover, the
entanglement detection probability drops exponentially when considering
mixtures of random states. Our results can be used to explain the
emergence of classicality in coarse
grained quantum chaotic dynamics. We also explored the violation of Bell's inequalities in the limit of high-dimensional systems [8], naturally arising when exploring the quantum-to-classical transition.

Schematic drawing of entanglement witnesses, see the review paper [9]

Schematic drawing of entanglement witnesses, see the review paper [9]

Robust and efficient generator of multipartite entanglement

Quantum chaotic maps can
efficiently generate pseudo-random states carrying almost maximal
multipartite entanglement, as characterized by the probability
distribution of bipartite entanglement between all possible
bipartitions of the system. We have shown [10] that such multipartite
entanglement is robust, in the sense that, when realistic noise is
considered, distillable entanglement of bipartitions remains almost
maximal up to a noise strength that drops only polynomially with the
number of qubits.

Stability border for distillable
entanglement of bipartitions

References

[1] G. Benenti, G. Casati and G. Strini, Principles of Quantum Computation and Information (World Scientific, Singapore, 2004-2007).

[2] G. Benenti, G. Casati, S. Montangero and D.L. Shepelyansky, Efficient quantum computing of complex dynamics, Phys. Rev. Lett. 87, 227901 (2001).

[3] G. Benenti, G. Casati, S. Montangero and D.L. Shepelyansky, Dynamical localization simulated on a few-qubit quantum computer, Phys. Rev. A 67, 052312 (2003).

[4] S. Montangero, G. Benenti and R. Fazio, Dynamics of entanglement in quantum computers with imperfections, Phys. Rev. Lett. 91, 187901 (2003).

[5] D. Rossini, G. Benenti and G. Casati, Entanglement echoes in quantum computation, Phys. Rev. A 69, 052317 (2004).

[6] C. Mejia-Monasterio, G. Benenti, G.G. Carlo and G. Casati, Entanglement across a transition to quantum chaos, Phys. Rev. A 71, 062324 (2005).

[7] M. Znidaric, T. Prosen, G. Benenti and G. Casati, Detecting entanglement of random states with an entanglement witness, J. Phys. A. 40, 13787 (2007).

[8] W. Weiss, G. Benenti, G. Casati, I. Guarneri, T. Calarco, M. Paternostro and S. Montangero, Violation of Bell inequalities in larger Hilbert spaces: robustness and challenges, New J. Phys. 18, 013021 (2016).

[9] G. Benenti, Entanglement, randomness and chaos, Riv. Nuovo Cimento 32, 105 (2009)

[10] D. Rossini and G. Benenti, Robust and efficient generator of almost maximal multipartite entanglement, Phys. Rev. Lett. 100, 060501 (2008).