text:
# 1 Description of the model.

## 1 Description of the model.

In the present article we develop a continuum field model of the street canyon. In the next article we will deal with numerical examples . The vehicular flow in the canyon is multilane bidirectional one-level rectilinear, and it is considered with two coordinated signalized junctions . The vehicles belong to different vehicular classes: passenger cars, and trucks. Emissions from the vehicles are based on technical measurements and many types of pollutants are considered (carbon monoxide CO, hydrocarbons HC, nitrogen oxides $`\mathrm{NO}_\mathrm{x}`$). The vehicular dynamics is based on a hydrodynamical approach . The governing equations are the continuity equation for the number of vehicles, and Greenshields’ equilibrium speed-density u-k model .

The model of dynamics of pollutants is also hydrodynamical. The model consists of a set of mutually interconnected nonlinear, three-dimensional, time-dependent, partial differential equations with nonzero right-hand sides (sources), and of boundary and of initial problem. The pollutants, oxygen, and the remaining gaseous constituents of air, are treated as mixture of noninteracting, Newtonian, viscous fluid (perfect or ideal gases). The complete model incorporates as variables the following fields: density of the mixture, mass concentrations of constituents of the mixture, velocity of mixture, temperature of mixture, pressure of mixture, intrinsic (internal) energy of mixture, densities of vehicles, and velocities of vehicles. The model is based on the assumption of local laws of balance (conservation) of: mass of the mixture, masses of its constituents, momentum and energy of the mixture, the numbers of the vehicles, as well as of the state equations (Clapeyron’s law and Greenshields’ model). The equations of dynamics are solved by the finite difference scheme.

The six separate monocriterial optimization problems are formulated by defining the functionals of total travel time, of global emissions of pollutants, and of global concentrations of pollutants, both in the studied street canyon and in its two nearest neighbour substitute canyons. The vector of control is a five-tuple composed of two cycle times, two green times, and one offset time between the traffic lights. The optimal control problem consists of minimization of the six functionals over the admissible control domain.

## 2 Equations of dynamics.

Under the above model specifications, the complete set of equations of dynamics of the model is formulated as follows (we follow the general idea presented in ):

E1. Balance of momentum of mixture - Navier Stokes equation.

$$\rho (\frac{𝐯}{t}+(𝐯)𝐯)+S𝐯=p+\eta \mathrm{\Delta }𝐯+(\xi +\frac{\eta }{3})(\mathrm{div}𝐯)+𝐅,$$
(1)
where $`\eta `$ is the first viscosity coefficient ($`\eta =18.110^6[\frac{\mathrm{kg}}{\mathrm{m}\mathrm{s}}]`$ for air at temperature $`T=293.16`$ \[K\]), $`\xi `$ is the second viscosity coefficient ($`\xi =15.610^6[\frac{\mathrm{kg}}{\mathrm{m}\mathrm{s}}]`$ for air at temperature $`T=293.16`$\[K\]), $`𝐅=\rho 𝐠`$ is the gravitational body force density, $`𝐠`$ is the gravitational acceleration of Earth ($`𝐠=(0,0,9.81)[\frac{\mathrm{m}}{\mathrm{s}^2}]`$), $`𝐯`$ is gradient of the vector (so it is a tensor of rank 2). We assume that the gaseous mixture is a compressible and viscous fluid.

E2. Balance of mass of mixture - Equation of continuity.

$$\frac{\rho }{t}+\mathrm{div}(\rho 𝐯)=S.$$
(2)
We have assumed the source D1.

E3. Balances of masses of constituents of mixture - Diffusion equations.

E3a.

$`\rho ({\displaystyle \frac{c_i}{t}}+𝐯c_i)=S_i^Ec_iS+`$ (3)
$`+{\displaystyle \underset{m=1}{\overset{N1}{}}}\{(D_{im}D_{iN})\mathrm{div}[\rho (c_m+{\displaystyle \frac{k_{T,m}}{T}}T)]\},i=1,\mathrm{},N_E.`$
E3b.

$`\rho ({\displaystyle \frac{c_i}{t}}+𝐯c_i)=c_iS+`$ (4)
$`+{\displaystyle \underset{m=1}{\overset{N1}{}}}\{(D_{im}D_{iN})\mathrm{div}[\rho (c_m+{\displaystyle \frac{k_{T,m}}{T}}T)]\},i=(N_E+1),\mathrm{},N,`$
where $`D_{im}=D_{mi}`$ is the mutual diffusivity coefficient from the $`i`$-th constituent to $`m`$-th one, and $`D_{ii}`$ is the autodiffusivity coefficient of the $`i`$-th constituent, and $`k_{T,m}`$ is the thermodiffusion ratio of the $`m`$-th constituent. The diffusivity coefficients and thermodiffusion ratios are constant and known). In E3a we have assumed the sources D1-D2. In E3b only the source D1 is taken into account. Since the mixture is in motion, we cannot neglect the convection term: $`𝐯c_i`$. We assume that the barodiffusion and gravitodiffusion coefficients are equal to zero.

E4. Balance of energy of mixture.

$$\rho (\frac{ϵ}{t}+𝐯ϵ)=(\frac{1}{2}𝐯^2+ϵ)S+𝐓:𝐯+\mathrm{div}(𝐪)+\sigma ,$$
(5)
where $`ϵ`$ is the mass density of intrinsic (internal) energy of the air mixture, $`𝐓`$ is the stress tensor, symbol $`:`$ denotes the contraction operation, $`𝐪`$ is the vector of flux of heat. We assume that :

$`ϵ={\displaystyle \underset{i=1}{\overset{N}{}}}ϵ_i,`$ (6)
$`ϵ_i={\displaystyle \frac{1}{m_i}}\{c_ik_BT\mathrm{exp}({\displaystyle \frac{m_i|𝐠|z}{k_BT}})[({\displaystyle \frac{z}{c}})(1\mathrm{exp}({\displaystyle \frac{m_i|𝐠|c}{k_BT}}))\mathrm{exp}({\displaystyle \frac{m_i|𝐠|c}{k_BT}})]\}+`$ (7)
$`+\stackrel{~}{\mu }_ic_i,`$
$`\stackrel{~}{\mu }_i={\displaystyle \frac{\mu _i}{m_i}},`$ (8)
$`\mu _i=k_BT\{\mathrm{ln}[(c_ip)(k_BT)^{\frac{c_{p,i}}{k_B}}({\displaystyle \frac{m_{\mathrm{air}}}{m_i}})({\displaystyle \frac{2\pi h^2}{m_i}})^{\frac{3}{2}}]\}+m_i|𝐠|z,`$ (9)
$`\mathrm{T}_{mk}=p\delta _{mk}+`$ (10)
$`+\eta [({\displaystyle \frac{v_m}{x_k}}+{\displaystyle \frac{v_k}{x_m}}{\displaystyle \frac{2}{3}}\delta _{mk}\mathrm{div}(𝐯)){\displaystyle \frac{v_k}{x_m}}]+\xi [(\delta _{mk}\mathrm{div}(𝐯))^2],m,k=1,\mathrm{},3,`$
$`𝐓:𝐯={\displaystyle \underset{m=1}{\overset{3}{}}}{\displaystyle \underset{k=1}{\overset{3}{}}}\mathrm{T}_{mk}{\displaystyle \frac{v_m}{x_k}},`$ (11)
$`𝐪={\displaystyle \underset{i=1}{\overset{N}{}}}\{[({\displaystyle \frac{\beta _iT}{\alpha _{ii}}}+\stackrel{~}{\mu }_i)𝐣_i]+[(\kappa )T]\},`$ (12)
$`𝐣_i=\rho D_{ii}(c_i+{\displaystyle \frac{k_{T,i}}{T}}T),`$ (13)
$`\alpha _{ii}={\displaystyle \frac{[\rho D_{ii}]}{[(\frac{\stackrel{~}{\mu }_i}{c_i})_{(c_n)_{n=1,\mathrm{},N,in},T,p}]}},`$ (14)
$`\beta _i=[\rho D_{ii}]\{{\displaystyle \frac{k_{T,i}}{T}}{\displaystyle \frac{[(\frac{\stackrel{~}{\mu }_i}{T})_{(c_n)_{n=1,\mathrm{},N},p}]}{[(\frac{\stackrel{~}{\mu }_i}{c_i})_{(c_n)_{n=1,\mathrm{},N,in},T,p}]}}\},`$ (15)
where $`ϵ_i`$ is the mass density of intrinsic (internal) energy of the $`i`$th constituent of the air mixture, $`m_i`$ the molecular mass of the $`i`$th constituent, $`k_B=1.380710^{23}[\frac{\mathrm{J}}{\mathrm{kg}}]`$ is Boltzmann’s constant, $`\mu _i`$ is the complete partial chemical potential of the $`i`$th constituent of the air mixture (it is complete since it is composed of chemical potential without external force field and of external potential), $`m_{\mathrm{air}}=28.966`$ \[u\] is the molecular mass of air ($`1[\mathrm{u}]=1.6605410^{27}`$ \[kg\]), $`\delta _{mk}`$ is Kronecker’s delta, $`c_{p,i}`$ is the specific heat at constant pressure of the $`i`$th constituent of air mixture, $`h=6.6260810^{34}`$ \[$`Js`$\] is Planck’s constant, $`𝐣_i`$ is the vector of flux of mass of the $`i`$th constituent of the air mixture, and $`\kappa `$ is the coefficient of thermal conductivity of air. These magnitudes are derived from Grand Canonical ensemble with external gravitational Newtonian field.

E5. Equation of state of the mixture - Constitutive equation - Clapeyron’s equation.

$$\frac{p}{\rho }=\frac{R}{m_{\mathrm{air}}}T$$
(16)
is Clapeyron’s equation of state for a gaseous mixture, where $`R=8.3145`$ \[$`\frac{\mathrm{J}}{\mathrm{mole}\mathrm{K}}`$\] is the gas constant.

$$p_i=c_i\frac{m_{\mathrm{air}}}{m_i}p$$
(17)
are partial pressures of constituents according to Dalton’s law.

E6. Balances of numbers of vehicles - Equations of continuity of vehicles.

$$\frac{k_{l,vt}^s}{t}+\mathrm{div}(k_{l,vt}^s𝐰_{l,vt}^s)=0.$$
(18)
E7. Equations of state of vehicles - Greenshields model.

$$𝐰_{l,vt}^s(x,t)=(w_{l,vt,f}^s(1\frac{k_{l,vt}^s(x,t)}{k_{l,vt,\mathrm{jam}}^s}),0,0).$$
(19)
The Greenshields equilibrium speed-density u-k model is assumed . The values of maximum free flow speed $`w_{l,vt,f}^s`$, and of jam vehicular densities $`k_{l,vt,\mathrm{jam}}^s`$, are given in Tables 3 and 8 of .

E8. Technical parameters.

The dependence of emissivity on the density and velocity of vehicles is assumed in the form:

E8a.

$$e_{l,ct,vt}^s(x,t)=k_{l,vt}^s(x,t)[(\frac{|𝐰_{l,vt}^s(x,t)|\stackrel{~}{w}_{ct,vt,i_l}}{\stackrel{~}{w}_{ct,vt,i_l+1}\stackrel{~}{w}_{ct,vt,i_l}})(\stackrel{~}{e}_{ct,vt,i_l+1}\stackrel{~}{e}_{ct,vt,i_l})+\stackrel{~}{e}_{ct,vt,i_l}],$$
(20)
where $`\stackrel{~}{w}_{ct,vt,i_l}`$ are experimental velocities, $`|𝐰_{l,vt}^s(x,t)|(\stackrel{~}{w}_{ct,vt,i_l},\stackrel{~}{w}_{ct,vt,i_l+1}),`$ $`\stackrel{~}{e}_{ct,vt,i_l},`$ are experimental emissions of the $`ct`$th exhaust gas from single vehicle of $`vt`$th type at velocities $`\stackrel{~}{w}_{ct,vt,i_l}`$, respectively, measured in \[$`\frac{\mathrm{kg}}{\mathrm{veh}\mathrm{s}}`$\], $`i_l=1,\mathrm{},N_{EM},`$ $`N_{EM}`$ is the number of experimental measurements. Similarly, the dependence of the change of the linear density of energy on the density and velocity of vehicles is taken in the form:

E8b.

$$\sigma _{l,vt}^s(x,t)=q_{vt}k_{l,vt}^s(x,t)[(\frac{|𝐰_{l,vt}^s(x,t)|\overline{w}_{vt,i_l}}{\overline{w}_{vt,i_l+1}\overline{w}_{vt,i_l}})(\sigma _{vt,i_l+1}\sigma _{vt,i_l})+\sigma _{vt,i_l}],$$
(21)
where $`\sigma _{vt,i_l},`$ are experimental values of consumption of gasoline/diesel for a single vehicle of $`vt`$th type at velocities $`\overline{w}_{vt,i_l},`$ respectively, measured in \[$`\frac{\mathrm{kg}}{\mathrm{veh}\mathrm{s}}`$\], $`q_{vt}`$ is the emitted combustion energy per unit mass of gasoline/diesel \[$`\frac{\mathrm{J}}{\mathrm{kg}}`$\].

## 3 Optimization problems.

Our control task is the minimization of the measures of the total travel time (TTT) , emissions (E), and concentrations (C) of exhaust gases in the street canyon, therefore the appropriate optimization problems may be formulated as follows :

F0. Vector of control.

$$𝐮=(g_1,C_1,g_2,C_2,F)U^{\mathrm{adm}},$$
(1)
where $`𝐮`$ is vector of boundary control, $`g_m`$ are green times, $`C_m`$ are cycle times, $`F`$ is offset time, and $`U^{\mathrm{adm}}`$ is a set of admissible control variables (compare A8, A9, B5, B5S, B5SS).

We define six functionals F1-F6 of the total travel time, emissions, and concentrations of pollutants in single canyon, and in canyon with the nearest neighbour substitute canyons, respectively.

F1. Total travel time for a single canyon.

$$J_{\mathrm{TTT}}(𝐮)=\underset{s=1}{\overset{2}{}}\underset{l=1}{\overset{n_s}{}}\underset{vt=1}{\overset{VT}{}}_0^a_0^{T_S}k_{l,vt}^s(x,t)𝑑x𝑑t.$$
(2)
F2. Global emission for a single canyon.

$$J_\mathrm{E}(𝐮)=\underset{s=1}{\overset{2}{}}\underset{l=1}{\overset{n_s}{}}\underset{ct=1}{\overset{CT}{}}\underset{vt=1}{\overset{VT}{}}_0^a_0^{T_S}e_{l,ct,vt}^s(x,t)𝑑x𝑑t.$$
(3)
F3. Global pollutants concentration for a single canyon.

$$J_\mathrm{C}(𝐮)=\rho _{\mathrm{STP}}\underset{i=1}{\overset{N_E1}{}}_0^a_0^b_0^c_0^{T_S}c_i(x,y,z,t)𝑑x𝑑y𝑑z𝑑t.$$
(4)
F4. Total travel time for the canyon in street subnetwork.

$`J_{\mathrm{TTT},\mathrm{ext}}(𝐮)=J_{\mathrm{TTT}}(𝐮)+`$ (5)
$`+a{\displaystyle \underset{s=1}{\overset{2}{}}}\alpha _{\mathrm{TTT},\mathrm{ext}}^s{\displaystyle \underset{l=1}{\overset{n_s}{}}}{\displaystyle \underset{vt=1}{\overset{VT}{}}}k_{l,vt,\mathrm{jam}}^s(C_sg_s).`$
F5. Global emission for the canyon in street subnetwork.

$`J_{\mathrm{E},\mathrm{ext}}(𝐮)=J_\mathrm{E}(𝐮)+`$ (6)
$`+a{\displaystyle \underset{s=1}{\overset{2}{}}}\alpha _{\mathrm{E},\mathrm{ext}}^s{\displaystyle \underset{l=1}{\overset{n_s}{}}}{\displaystyle \underset{ct=1}{\overset{CT}{}}}{\displaystyle \underset{vt=1}{\overset{VT}{}}}e_{l,ct,vt,\mathrm{jam}}^s(C_sg_s).`$
F6. Global pollutants concentration for the canyon in street subnetwork.

$`J_{\mathrm{C},\mathrm{ext}}(𝐮)=J_\mathrm{C}(𝐮)+`$ (7)
$`+\rho _{\mathrm{STP}}abc{\displaystyle \underset{i=1}{\overset{N_E1}{}}}c_{i,\mathrm{STP}}{\displaystyle \underset{s=1}{\overset{2}{}}}\alpha _{\mathrm{C},\mathrm{ext}}^s(C_sg_s).`$
The integrands $`k_{l,vt}^s,e_{l,ct,vt}^s,c_i`$ in functionals F1-F6 depend on the control vector $`𝐮`$ F0 through the boundary conditions B0-B8, through the equations of dynamics E1-E8, as well as, through the sources D0-D2. The value of the vector of control $`u`$ directly affects the boundary conditions B5, B5S, B5SS, and then the boundary conditions B6-B8 for vehicular densities, velocities, and emissivities. It also affects the sources D0-D2. Next, it propagates to the equations of dynamics E1-E8 and then it influences the values of functionals F1-F6. We only deal with six monocriterial optimization problems O1-O6, and not with one multicriterial problem. We put the scaling parameters equal to unity: $`\alpha _{\mathrm{TTT},\mathrm{ext}}^s=\alpha _{\mathrm{E},\mathrm{ext}}^s=\alpha _{\mathrm{C},\mathrm{ext}}^s=1.0,`$ in functionals F4-F6. $`\rho _{\mathrm{STP}}`$ is the density of air at standard temperature and pressure STP, $`c_{i,\mathrm{STP}}`$ is concentration of the $`i`$th constituent of air at standard temperature and pressure. $`J_{\mathrm{TTT}}`$ and $`J_{\mathrm{TTT},\mathrm{ext}}`$ are measured in \[$`vehs`$\], $`J_\mathrm{E}`$ and $`J_{\mathrm{E},\mathrm{ext}}`$ are measured in \[kg\], and $`J_\mathrm{C}`$ and $`J_{\mathrm{C},\mathrm{ext}}`$ are measured in \[$`kgs`$\], respectively.

Now we formulate six separate monocriterial optimization problems O1-O6 that consist in minimization of functionals F1-F6 with respect to control vector F0 over admissible domain, while the equations of dynamics E1-E8 are fulfilled.

O1. Minimization of total travel time for a single canyon.

$$J_{\mathrm{TTT}}^{}=J_{\mathrm{TTT}}(𝐮_{\mathrm{TTT}}^{})=\mathrm{min}\{𝐮U^{\mathrm{adm}}:J_{\mathrm{TTT}}(𝐮)\};$$
(8)
O2. Minimization of global emission for a single canyon.

$$J_\mathrm{E}^{}=J_\mathrm{E}(𝐮_\mathrm{E}^{})=\mathrm{min}\{𝐮U^{\mathrm{adm}}:J_\mathrm{E}(𝐮)\};$$
(9)
O3. Minimization of global pollutants concentration for a single canyon.

$$J_\mathrm{C}^{}=J_\mathrm{C}(𝐮_\mathrm{C}^{})=\mathrm{min}\{𝐮U^{\mathrm{adm}}:J_\mathrm{C}(𝐮)\};$$
(10)
O4. Minimization of total travel time for a canyon in street subnetwork.

$$J_{\mathrm{TTT},\mathrm{ext}}^{}=J_{\mathrm{TTT},\mathrm{ext}}(𝐮_{\mathrm{TTT},\mathrm{ext}}^{})=\mathrm{min}\{𝐮U^{\mathrm{adm}}:J_{\mathrm{TTT},\mathrm{ext}}(𝐮)\};$$
(11)
O5. Minimization of global emission for a canyon in street subnetwork.

$$J_{\mathrm{E},\mathrm{ext}}^{}=J_{\mathrm{E},\mathrm{ext}}(𝐮_{\mathrm{E},\mathrm{ext}}^{})=\mathrm{min}\{𝐮U^{\mathrm{adm}}:J_{\mathrm{E},\mathrm{ext}}(𝐮)\};$$
(12)
O6. Minimization of global pollutants concentration for a canyon in street subnetwork.

$$J_{\mathrm{C},\mathrm{ext}}^{}=J_{\mathrm{C},\mathrm{ext}}(𝐮_{\mathrm{C},\mathrm{ext}}^{})=\mathrm{min}\{𝐮U^{\mathrm{adm}}:J_{\mathrm{C},\mathrm{ext}}(𝐮)\},$$
(13)
where $`J_{\mathrm{TTT}}^{},J_\mathrm{E}^{},J_\mathrm{C}^{},J_{\mathrm{TTT},\mathrm{ext}}^{},J_{\mathrm{E},\mathrm{ext}}^{},J_{\mathrm{C},\mathrm{ext}}^{}`$, are the minimal values of the functionals F1-F6, and $`𝐮_{\mathrm{TTT}}^{},𝐮_\mathrm{E}^{},𝐮_\mathrm{C}^{},𝐮_{\mathrm{TTT},\mathrm{ext}}^{},𝐮_{\mathrm{E},\mathrm{ext}}^{},𝐮_{\mathrm{C},\mathrm{ext}}^{}`$, are control vectors at which the functionals reach the minima, respectively.

## 4 Conclusions.

The proecological traffic control idea and advanced model of the street canyon have been developed. It has been found that the proposed model represents the main features of complex air pollution phenomena.


format: text

text:
# Systematic Analysis of Majorization in Quantum Algorithms

## I Introduction

One of the main open problems in quantum computation theory is finding some mathematical structure underlying optimal quantum algorithms. There is a rather short list of ideas behind the design of fast algorithms. Grover’s quantum searching algorithm grover  exploits calls to an oracle by enhancing a particular state via a rotation in the relevant Hilbert space associated to the problem. Shor’s quantum factoring algorithm shor  exploits the periodicity of an initial quantum state using only a minimum of Hadamard gates at the core of the quantum Fourier transform. Based on more general quantum mechanical principles, the idea of using adiabatic evolution to carry quantum computation adiabatic  has proven suitable for performing Grover’s algorithm and has been numerically studied as a candidate for attacking NP-complete problems. More recently, deterministic random walks in continuous time have been proven to solve a classically hard problem in polynomial time qwalk . Many other quantum algorithms can be mapped to the above families and, therefore, bring no further insight.

Some attempts to uncover an underlying principle, common to all known optimal algorithms, have already been explored though not definite and satisfactory answer has been found. One relevant instance is the role of entanglement in quantum algorithms ent1 ; ent2 ; ent3 ; ent4 ; rmp ; guifre . Although entanglement is a natural resource to be exploited in quantum algorithm design, there are known examples of fast algorithms where the quantum register remains in a product state all along the computation. Our work will concentrate on quite a different proposal. The basic idea is that efficiency is related to a strong majorization principle. We shall investigate the way the probability distribution associated to the computational basis evolves along optimal quantum computations and find that it obeys a very constrained behavior we shall analyze in detail.

Let us recall that majorization theory arises as the natural framework to study the measure of disorder for classical probability distributions muirhead ; hardy ; marshall ; maj . The notion of ordering emerging from majorization is far more severe than the one quantified by the standard Shannon entropy. If one probability distribution majorizes another, a set of inequalities must hold to constrain the former probabilities with respect to the latter. These inequalities lead to entropy ordering, but the converse is not necessarily true. In quantum mechanics, it has been proven that majorization is at the heart of the solution of a large number of quantum information problems. Majorization plays a fundamental role in topics like ensemble realization, conversion of quantum states via local operations and classical communication, and characterization of positive operator valued measurements vid .

In the context of quantum algorithms, a majorization principle has been formulated, proven for Grover’s algorithm and verified for Shor’s algorithm in Ref. lat . Furthermore, a complete proof of majorization in quantum phase-estimation algorithms was presented in orus . The underlying idea behind these analysis is that the probability distribution associated to the quantum state in the computational basis is step-by-step majorized until it is maximally ordered. Then a measurement will provide the sought solution with high probability. It has also been proven that the way such a detailed majorization emerges in both algorithmic families is intrinsically different orus .

In this paper we analyze the consistency and universality of a possible Majorization Principle. More concretely, we have studied several different quantum algorithms based on distinct properties. First, we have considered the problem of finding a hidden affine function by means of calls to an oracle. This problem is relevant because it is a known fast quantum algorithm that uses no entanglement at all. Second, we have taken a non-efficient instance, namely the parity determination problem. This is a case where the final solution must match a global majorization, yet it does not obey step by step majorization neither presents any quantum speed-up. The third case considered here is the large class of quantum adiabatic evolution algorithms. Efficiency and optimality has been proven to depend on the interpolating time path taken along the evolution. It is a remarkable fact that optimality appears when step-by-step majorization is present. Finally, deterministic quantum random walks provide exponential speed-up over classical oracle based random walks. Again, a manifest strong majorization arrow is detected.

The conclusion of the accumulated research is that all the analyzed instances of quantum algorithms support a step-by-step Majorization Principle. That is, optimal quantum computation is systematically verified to correspond to a step by step detailed reordering of the whole probability distribution in the computational basis. Some of the instances show the extra feature that the initial state can be prepared in different ways. Then, an initial step-by-step reverse majorization period precedes the subsequent step-by-step majorization, closing an invertible cycle. The study of quantum computation by adiabatic evolution shows the possibility of slower algorithms that maintain majorization. This implies that step-by-step majorization may be a necessary but is definitely not sufficient condition for efficiency.

We have structured the paper as follows: in Sec. II we briefly review some concepts about majorization theory and how it is related to quantum algorithms. We develop an analysis of a quantum algorithm for solving a hidden affine function problem in Sec. III. In Sec. IV we study an optimal quantum algorithm solving the parity problem. We move to an investigation of adiabatic quantum computation in Sec. V, analyzing the effect of the evolution path in adiabatic searching algorithms in Sec. V.A and Sec. V.B, as well as the effect of the speed in the time variation of the Hamiltonian in Sec. V.C. A further example of adiabatic evolution solving the $`2`$-SAT “ring of agrees” problem is provided in Sec. V.D. In Sec. VI we examine a recently proposed quantum algorithm based on a continuous time quantum walk on a graph solving a classically hard problem. Finally, in Sec. VII we state a Majorization Principle based on all the previous results and collect our conclusions.

## II Majorization theory and its relation to quantum algorithms

Our approach to the mathematical study of quantum processes will be through majorization’s eye. We review in this section the contact point between majorization theory and quantum algorithms, as stated previously in lat  and orus . In particular, we also present here the concept of “natural majorization”, first stated in orus , which will eventually be used in this work.

### II.1 Majorization theory

Let us consider two vectors $`𝐱`$, $`𝐲^d`$ such that $`_{i=1}^dx_i=_{i=1}^dy_i=1`$, whose components represent two different probability distributions. We say that distribution $`𝐲`$ majorizes distribution $`𝐱`$, written as $`𝐱𝐲`$, if and only if there exist a set of permutation matrices $`P_j`$ and probabilities $`p_j`$ such that

$$𝐱=\underset{j}{}p_jP_j𝐲.$$
(1)
Because the probability distribution $`𝐱`$ can be obtained from $`𝐲`$ by means of a probabilistic sum, the definition given in equation (1) provides the intuitive notion that the $`𝐱`$ distribution is more disordered than $`𝐲`$. An alternative and usually more practical definition of majorization can be stated in terms of a set of inequalities to be held between the two distributions. Consider the components of the two vectors sorted in decreasing order, written as $`(z_1,\mathrm{}z_d)𝐳^{}`$. We say that $`𝐲^{}`$ majorizes $`𝐱^{}`$ if and only if the following relations are satisfied:

$$\underset{i=1}{\overset{k}{}}x_i\underset{i=1}{\overset{k}{}}y_ik=1\mathrm{}d.$$
(2)
In this paper we call probability sums similar to the ones appearing in the previous expression as “cumulants”. There is still a third way of defining majorization involving the use of doubly stochastic matrices. A real $`d\times d`$ matrix $`D=(D_{ij})`$ is said to be doubly stochastic if it has non-negative entries, and each row and column of $`D`$ sums to $`1`$. We say that $`𝐲`$ majorizes $`𝐱`$ if and only if there is a doubly stochastic matrix $`D`$ such that

$$𝐱=D𝐲.$$
(3)
The equivalence among the three given definitions can be proven maj . Complementarily, we say that the probability distribution $`𝐱`$ reversely majorizes distribution $`𝐲`$ if and only if $`𝐲`$ majorizes $`𝐱`$. A powerful relation involving majorization and the common Shannon entropy $`H(𝐱)_{i=1}^dx_i\mathrm{log}x_i`$ of probability distribution $`𝐱`$ is that if $`𝐱𝐲`$ then $`H(𝐲)H(𝐱)`$.

### II.2 Link between majorization theory and quantum algorithms

The way we relate majorization theory to quantum algorithms can be stated as follows: let $`|\psi ^{(m)}`$ be the pure state representing the register in a quantum computer at an operating stage labeled by $`m=1\mathrm{}M`$, where $`M`$ is the total number of steps in the algorithm, and let $`N`$ be the dimension of the Hilbert space. If we denote as $`\{|i\}_{i=1}^N`$ the basis in which the final measurement is performed in the algorithm, we can naturally associate a set of sorted probabilities $`p_i`$, $`i=1\mathrm{}N`$, to this quantum state in the following way: decompose the register state in the measurement basis such that

$$|\psi ^{(m)}=\underset{i=1}{\overset{N}{}}a_i^{(m)}|i.$$
(4)
The probability distribution associated to this state is

$$𝐩^{(m)}=\{p_i^{(m)}\}p_i^{(m)}|a_i^{(m)}|^2=|i|\psi ^{(m)}|^2$$
(5)
where $`i=1\mathrm{}N`$, which corresponds to the probabilities of all the possible outcomes if the computation were stopped at stage $`m`$ and a measurement were performed. A quantum algorithm will be said to majorize this probability distribution between steps $`m`$ and $`m+1`$ if and only if lat ; orus

$$𝐩^{(m)}𝐩^{(m+1)}.$$
(6)
Similarly, a quantum algorithm will be said to reversely majorize this probability distribution between steps $`m`$ and $`m+1`$ if and only if

$$𝐩^{(m+1)}𝐩^{(m)}.$$
(7)
If the situation given in equation (6) is step-by-step verified, there is a net flow of probability directed to the values of highest weight, in such a way that the probability distribution will be steeper as time flows. In physical terms, this can be stated as a very particular constructive interference behavior, namely, a constructive interference that has to step-by-step satisfy the constraints given in equation (2). The quantum algorithm builds up the solution at each time step by means of this very precise reordering of probability distribution.

It is important to note that majorization is checked on a particular basis. Step-by-step majorization is a basis dependent concept. Nevertheless there is a preferred basis, which is the basis defined by the physical implementation of the quantum computer or computational basis. The principle we analyze is rooted in the physical possibility to arbitrarily stop the computation at any time and perform a measurement. The claim pursued along the paper is that the probability distribution associated to this physically meaningful action obeys majorization.

### II.3 Natural majorization in quantum algorithms

Let us now define the concept of natural majorization for quantum algorithms as it was originally presented in orus . Working with probability amplitudes in the basis $`\{|i\}_{i=1}^N`$, the action of a particular unitary gate at step $`m`$ makes the amplitudes evolve to step $`m+1`$ in the following way:

$$a_i^{(m+1)}=\underset{j=1}{\overset{N}{}}U_{ij}a_j^{(m)},$$
(8)
where $`U_{ij}`$ are the matrix elements in the chosen basis of the unitary evolution operator (namely, the propagator from step $`m`$ to step $`m+1`$). Inverting the evolution, we can write

$$a_i^{(m)}=\underset{j=1}{\overset{N}{}}C_{ij}a_j^{(m+1)},$$
(9)
where $`C_{ij}`$ are the matrix elements of the inverse unitary evolution (which is unitary as well). Taking the square modulus we find

$$|a_i^{(m)}|^2=\underset{j=1}{\overset{N}{}}|C_{ij}|^2|a_j^{(m+1)}|^2+\mathrm{interference}\mathrm{terms}.$$
(10)
Should the interference terms disappear, majorization would be verified in a “natural” way between steps $`m`$ and $`m+1`$ because the initial probability distribution could be obtained from the final one only by the action of a doubly stochastic matrix with entries $`|C_{ij}|^2`$. This is the so-called “natural majorization”: majorization which naturally emerges from the unitary evolution due to the lack of interference terms when making the square modulus of the probability amplitudes. Similarly, we can define the concept of “natural reverse majorization”, which follows in a similar way: there will be “natural reverse majorization” between steps $`m`$ and $`m+1`$ if and only if there is “natural majorization” between time steps $`m+1`$ and $`m`$.

### II.4 Majorization in Grover’s and Shor’s quantum algorithms

In order to motivate the forthcoming study we briefly sketch here the main results found concerning the analysis of majorization in the two well-known quantum algorithms of Grover grover  and Shor shor . These results were already presented in Ref. lat  and orus , so we address the reader interested in precise details to these references.

On the one hand, Grover’s quantum searching algorithm was found in lat  to follow a step-by-step majorization. More concretely, each time the Grover’s operator is applied the probability distribution obtained from the computational basis obeys the set of constraints given in equation (2) until the searched state is found. Furthermore, because of the possibility of understanding Grover’s quantum evolution as a rotation in a two-dimensional Hilbert space (see for example nielsen ) it is seen that the quantum algorithm follows a step-by-step reverse majorization when evolving far away from the marked state, until the initial superposition of all possible computational states is obtained again. The quantum algorithm behaves such that majorization is present when approaching to the solution, while reverse majorization appears when escaping from it. A cycle of majorization and reverse majorization emerges in the process as we consider long enough time evolutions, due to the rotational nature of Grover’s operator.

On the other hand, Shor’s quantum algorithm was analyzed inside of the broad family of quantum phase-estimation algorithms. In lat  it was observed that a step-by-step majorization seemed to appear under the action of the last quantum Fourier transform when considered in the usual Coppersmith decomposition copper . One step further was taken in orus , were the complete mathematical proof of this property was provided. The result relies on the fact that those quantum states that can be mixed by a Hadamard operator coming from the decomposition of the quantum Fourier transform only differ by a phase all along the computation. Such a property entails as well the appearance of natural majorization, in the way presented above. Natural majorization was proven relevant for the case of Shor’s quantum Fourier transform. This particular algorithm manages step-by-step majorization in a most efficient way. No interference terms spoil the majorization introduced by the natural diagonal terms in the unitary evolution. It is still unclear the role that natural majorization plays in distinguishing different level of efficiency in quantum algorithms.

These two results suggest a possible relation between majorization and quantum algorithms. This is the point to be exploited in detail with further examples in the next sections.

## III Analysis of a quantum algorithm for solving a hidden affine function problem

The problem of finding hidden affine functions was initially proposed by Bernstein and Vazirani BZ  as a generalization of Deutsch’s problem deutsch . Further studies have investigated into this class of problems, providing a range of fast quantum algorithms for solving different generalizations cleve ; mosca . The case we present in this work is one of the multiple variations stated in Ref. mosca , but the main results we obtain can be verified as well for the whole set of quantum algorithms solving similar problems.

### III.1 Setting of the problem

Let us state the following problem (see mosca ):

*Given an integer N function $`f:xmx+b`$, where $`x,m,b_N`$, find $`m`$.*

The classical analysis reveals that no information about $`m`$ can be obtained with only one evaluation of the function $`f`$. Conversely, given the unitary operator $`U_f`$ acting in a reversible way in the Hilbert space $`_N_N`$ such that

$$U_f|x|y=|x|y+f(x),$$
(11)
(where the sum is to be interpreted as modulus $`N`$), there is a quantum algorithm solving this problem with only one query to $`U_f`$.

### III.2 Quantum algorithm

Let us take $`N=2^n`$, being $`n`$ the number of qubits. The quantum algorithm optimally solving the problem previously presented reads as follows:

* Prepare two registers of $`n`$ qubits in the state $`|0\mathrm{}0|\psi _1_N_N`$, where $`|\psi _1=QFT(N)^1|1`$, and $`QFT(N)^1`$ denotes the inverse quantum Fourier transform in a Hilbert space of dimension $`N`$.
* Apply $`QFT(N)`$ over the first register.
* Apply $`U_f`$ over the whole quantum state.
* Apply $`QFT(N)^1`$ over the first register.
* Measure the first register and output the measured value.

The different steps concerning this process are summarized in Fig. 1.

### III.3 Analysis of the quantum algorithm

We now show how the proposed quantum algorithm leads to the solution of the problem. Our analysis raises two observations concerning the way both entanglement and majorization behave in the computational process.

In the first step of the algorithm, the quantum state is separable, noting that the quantum Fourier transform (and its inverse) applied on a well defined state in the computational basis leads to a perfectly separable state (see, for example, cleve ) Actually, this separability holds also step-by-step when a decomposition for the quantum Fourier transform is considered, such as the Coppersmith’s decomposition copper . That is, the quantum state $`|0\mathrm{}0|\psi _1`$ is unentangled.

The second step of the algorithm corresponds to a quantum Fourier transform in the first register. This action leads to a step-by-step reverse majorization of the probability distribution of the possible outcomes while it does not use neither create any entanglement. Moreover, natural reverse majorization is at work due to the absence of interference terms.

Next, it is easy to verify that the quantum state

$$|\psi _1=\frac{1}{\sqrt{N}}\underset{j=0}{\overset{N1}{}}e^{2\pi \frac{j}{N}}|j$$
(12)
is an eigenstate of the operation $`|y|y+f(x)`$ with eigenvalue $`e^{2\pi i\frac{f(x)}{N}}`$. After the third step, the quantum state reads

$$\frac{1}{\sqrt{N}}\underset{x=0}{\overset{N1}{}}e^{2\pi i\frac{f(x)}{N}}|x|\psi _1=\frac{e^{2\pi i\frac{b}{N}}}{\sqrt{N}}\left(\underset{x=0}{\overset{N1}{}}e^{2\pi i\frac{mx}{N}}|x\right)|\psi _1.$$
(13)
The probability distribution of possible outcomes has not been modified, thus not affecting majorization. Furthermore, the pure quantum state of the first register can be written as $`QFT(N)|m`$ (up to a phase factor), so this step has not created any entanglement among the qubits of the system either.

In the fourth step of the algorithm, the action of the operator $`QFT(N)^1`$ over the first register leads to the state $`e^{2\pi i\frac{b}{N}}|m|\psi _1`$. A subsequent measurement in the computational basis over the first register provides the desired solution. Recalling the results found in orus , we see that the inverse quantum Fourier transform naturally majorizes step-by-step the probability distribution attached to the different outputs. On the other hand, the separability of the quantum state still holds step-by-step. Note that step-by-step majorization is in fact dependent on the specific implementation of the quantum Fourier transform operation, but nevertheless it holds true for other decompositions of the operator appart from the usual Coppersmith’s one (as we already stated in orus ).

It is clear that the quantum algorithm is faster than any of its possible classical counterparts, as it only needs of a single query to the unitary operator $`U_f`$ to get the solution. We can summarize our analysis of majorization for the present quantum algorithm as follows:

Result 1:  *The fast quantum algorithm for finding a hidden affine function shows a majorization cycle based on the action of a $`QFT(N)`$ and a $`QFT(N)^1`$.*

We understand that the algorithm is entanglement-free as long as we analyze it between the action of the different unitary gates. From a more physical point of view, the quantum registers may become highly entangled during the performance of multi-qubit gates, despite it is not present between two of them. Our assertion relies then on the study of the system at these particular steps in the computation, which we think to be the most natural steps to consider. It follows that there can exist quantum computational speed-up without the use of entanglement (in the way made precise before). In this case, it is seen that no resource increases exponentially. Yet, a majorization cycle is present in the process, which is indeed rooted in the structure of both the quantum Fourier transform and the quantum state.

## IV Analysis of an optimal quantum algorithm for solving the parity problem

The problem of finding the parity of a given function $`f:x_N\{1,+1\}`$, usually known as the parity problem, has been shown to be as hard for a quantum computer in the quantum oracular model of computation as it is for a classical computer parity1 ; parity2 : no quantum speed-up can be achieved in this case. We shall first present the problem and then analyze an optimal quantum algorithm proposed in parity1  from the point of view of majorization.

### IV.1 Setting of the problem

Let us state the parity problem in the following way (see parity1 ):

*Given a function $`f:x_N\{1,+1\}`$, evaluate the product of all the $`f(x)`$ for all the possible $`x`$.*

It has been proved that a quantum computer will need at least $`N/2`$ queries to the quantum oracle $`f`$ for solving this problem compared to the $`N`$ classical queries parity1 . Thus, a quantum computer is not faster than a classical one (in the limit of a very large input, where $`N`$ goes to infinity) when dealing with this situation: no better efficiencies can be obtained using the quantum computational paradigm in getting the desired result. The time complexity of the best possible quantum algorithm will be $`O(N)`$, without improvement with respect to the classical time complexity, because the quantum speed-up is only by a factor of two.

### IV.2 Quantum Algorithm

Let us briefly outline the main lines of an optimal quantum algorithm solving the parity problem in exactly $`N/2`$ queries to the oracular function $`f`$, which was initially presented in parity1 . We first introduce a series of definitions and notations: the function $`f(x)`$ will be evaluated through a quantum oracle acting in the following way

$`U_f|x,+1=|x,f(x)`$
$`U_f|x,1=|x,f(x),`$ (14)
where the second register is a qubit taking the values $`\pm 1`$. Let us define also the quantum state $`|x,a=\frac{1}{\sqrt{2}}\left(|x,+1|x,1\right)`$, which is seen to be a proper state of operator $`U_f`$ with eigenvalue $`f(x)`$. With this definitions, the quantum algorithm reads as follows:

* Prepare the initial quantum state $`|\psi _0=\frac{1}{\sqrt{N}}_{x=1}^N|x,a`$.
* Apply the following operations over the initial quantum state:

$$V_{N/2}U_fV_{N/21}U_f\mathrm{}V_1U_f|\psi _0|\psi _f,$$
(15)
where $`U_f`$ is defined as before, and the rest of operators are defined as $`V_{N/2}=1`$, $`V_i=ViN/2`$, with

$$\begin{array}{cc}\hfill V|x,a& =|x+1,ax=1,\mathrm{},\frac{N}{2}1\hfill \\ \hfill V|\frac{N}{2},a& =|1,a\hfill \\ \hfill V|x,a& =|x+1,ax=\frac{N}{2}+1,\mathrm{},N1\hfill \\ \hfill V|N,a& =|\frac{N}{2}+1,a.\hfill \end{array}$$
(16)
* Measure the observable $`|\psi _0\psi _0|`$ over $`|\psi _f`$ .

Note that the final measurement is to be made on a specific basis.

### IV.3 Analysis of the quantum algorithm

We now make an study of how this algorithm leads to the desired solution of the proposed problem. The analysis will show the way majorization behaves in this optimal but non-efficient quantum process.

We focus on how the operations in the second step affect the quantum state leading to the solution, and thus affect the probability distribution of possible outcomes for the final measurement. If we apply $`U_f`$ to the initial state, we get

$$U_f|\psi _0=\frac{1}{\sqrt{N}}\underset{x=1}{\overset{N}{}}f(x)|x,a.$$
(17)
After the application of operator $`V_1`$ the quantum state evolves to

$`V_1U_f|\psi _0`$ $`={\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{x=1}{\overset{N/2}{}}}f(x1)|x,a`$ (18)
$`+{\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{x=N/2+1}{\overset{N}{}}}f(x1)|x,a,`$
as can be directly checked (care must be taken with the possible values of $`x`$ in both sums). If we now apply again $`U_f`$ we get:

$`U_fV_1U_f|\psi _0`$ $`={\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{x=1}{\overset{N/2}{}}}f(x)f(x1)|x,a`$ (19)
$`+{\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{x=N/2+1}{\overset{N}{}}}f(x)f(x1)|x,a,`$
so we begin to recognize the pattern the algorithm follows. At the end of the computation the final state is

$`|\psi _f`$ $`={\displaystyle \frac{1}{\sqrt{N}}}f(1)\mathrm{}f(N/2){\displaystyle \underset{x=1}{\overset{N/2}{}}}|x,a`$ (20)
$`+{\displaystyle \frac{1}{\sqrt{N}}}f(N/2+1)\mathrm{}f(N){\displaystyle \underset{x=N/2+1}{\overset{N}{}}}|x,a,`$
and it is easily verified that this state is equal to $`|\psi _0`$ if the parity of the function is equal to $`+1`$, and orthogonal to $`|\psi _0`$ (say $`|\psi _0^{}`$) if the parity is $`1`$. A suitable measurement of the observable $`|\psi _0\psi _0|`$ can then distinguish between the two values.

Let us now analyze the way this algorithm behaves with respect to majorization. As stated in Sec. II.B, majorization must always be checked from the probability distribution of obtaining the different outcomes of the final measurement. In other words, the probability distribution subject of analysis must always be the one obtained from the final measurement basis. Such a basis turns usually to be the computational one, but it is not necessarily so. Here, we are dealing with one of these exceptional cases in which the final measurement basis differs from the computational one. Consequently, majorization must be studied in this unusual but natural basis for the quantum algorithm.

The only two vectors we know of this basis are $`|\psi _0`$ and $`|\psi _0^{}`$. We could extend them to a whole basis but it is not necessary for our purposes, as we can analyze the probability of being in each of these two states all along the computation. Should majorization be present step-by-step in the process, the probability of being in one of these two states would smoothly decrease in favor of the other one, which would parallely smoothly increase. In a naive way, this is what a *majorization arrow* means: as the process evolves the probability of being in the right state becomes bigger and bigger.

We can observe that this does not happen in the algorithm for the whole computational process, except for the last application of the oracle $`U_f`$ (compulsory if one wishes to distinguish between the two states). It is easily seen, because in all the steps of the computation the quantum state is an arbitrary superposition of computational states of amplitudes $`+1/\sqrt{N}`$ and $`1/\sqrt{N}`$, without any apparent structure, so the probabilities of being in $`|\psi _0`$ or $`|\psi _0^{}`$ evolve erratically. The full structure only appears when the last oracle $`U_f`$ is applied, thus providing the necessary majorization to be able to distinguish the two states with a measurement, but the important point is that this is not a majorization arrow, because there is no step-by-step majorization. This is stated in our second result:

Result 2:  *No step-by-step majorization is present along the non-efficient parity determination problem.*

Thus, no majorization cycle similar to the one found in the preceding section could ever appear. Interestingly enough, this is a problem in which quantum computers do not provide a better efficiency than classical ones.

## V Analysis of the adiabatic searching algorithms and of an adiabatic algorithm solving a $`2`$-SAT problem

We now turn to the analysis of the quantum adiabatic searching algorithm, observing the effects of a change of path between the initial and the problem hamiltonian under the majorization’s point of view lat . We see that those paths leading to optimality in the algorithm lead as well to step-by-step majorization, while the converse is not necessarily true. A different example of adiabatic evolution is analyzed in the last point of this section, namely, an adiabatic algorithm solving the $`2`$-SAT “ring of agrees” problem.

The adiabatic model of quantum computation was initially introduced in adiabatic , and can be briefly summarized as follows. We consider a physical system controlled by a a time dependent hamiltonian of the form

$$H(s(t))=(1s(t))H_0+s(t)H_p,$$
(21)
where $`H_0`$ and $`H_p`$ are the initial and problem hamiltonian respectively, and $`s(t)`$ is a time dependent function satisfying the boundary conditions $`s(0)=0`$ and $`s(T)=1`$ for a given $`T`$. The desired solution to a given problem is encoded in the ground state of $`H_p`$. The gap between the ground and the first excited state of the instantaneous hamiltonian at time $`t`$ will be called $`g(t)`$. Let us define $`g_{min}`$ as the global minimum of $`g(t)`$ for $`t`$ in the interval $`[0,T]`$. If at time $`T`$ the ground state is given by the state $`|E_0;T`$, the adiabatic theorem states that if we prepare the system in its ground state at $`t=0`$ (which is assumed to be easy to prepare) and let it evolve under this hamiltonian, then

$$|E_0;T|\psi (T)|^21ϵ^2$$
(22)
provided that

$$\frac{\mathrm{max}|\frac{dH_{1,0}}{dt}|}{g_{min}^2}ϵ$$
(23)
where $`H_{1,0}`$ is the hamiltonian matrix element between the ground and first excited state, $`ϵ1`$, and the maximization is taken over the whole time interval $`[0,T]`$ adiabatic ; wim . Because the problem hamiltonian encodes the solution to the problem in its ground state, we get the desired solution with high probability after a time $`T`$.

This quantum adiabatic evolution method has been applied to the searching problem (das ; roland ; wim ; jer ). Let the initial state be $`|\psi _0=\frac{1}{\sqrt{N}}_{x=1}^N|x`$, being $`N`$ the number of entries for the searching, and let the initial and problem hamiltonian be $`H_0=I|\psi _0\psi _0|`$ and $`H_p=I|mm|`$, being $`|m`$ the searched state. This scheme leads to different results depending on whether we apply the adiabatic condition globally (that is, in the whole time interval $`[0,T]`$) or locally (at each time $`t`$). In what follows we will consider these two situations without entering into precise details of the involved calculations. For further information, we refer the reader to das ; roland  and references therein.

### V.1 Analysis of the fastest global adiabatic evolution

Let us suppose that we demand the adiabatic condition given in equation (23) to be satisfied globally in the whole interval $`[0,T]`$. This does not involve any particular restriction on the form of $`s(t)`$, so we can then choose $`s(t)=t/T`$, leading to a linear evolution of the hamiltonian. Under these circumstances it can be proven roland  that the global adiabatic condition is verified provided that

$$T\frac{N}{ϵ}.$$
(24)
Hence, the algorithm needs $`O(N)`$ time to hit the solution with appreciable probability, so the global adiabatic searching does not lead to an increasing efficiency with respect to a classical searching (in contrast with the square root speed-up of Grover’s quantum algorithm).

Let us call $`P_+(t)`$ the probability of being at the searched state at time $`t`$ and similarly $`P_{}(t)`$ the probability of being at any different state from the desired one at time $`t`$. Note that, because of the symmetry of the problem, $`P_{}(t)`$ will be exactly the same for all those quantum states differing from the solution state all along the computational process. In order to analyze majorization, we recall the set of inequalities given in equation (2) to be satisfied at each majorizing time step. It is easy to see that the maximum probability at all times will be $`P_+(t)`$, while the rest of the probabilities will remain smaller to this quantity all along the computation and equal to $`P_{}(t)`$. In order to gain simplicity we have analyzed in detail the behaviour of the two non-trivial cumulants $`P_+(t)`$ and $`P_+(t)+P_{}(t)`$, as the rest of them will not lead to different conclusions from the ones emerging from our study.

We have performed numerical simulations in the fastest allowed case ($`T=\frac{N}{ϵ}`$) and have found the time evolution for the two cumulants. The results for $`ϵ=0.2`$ and $`N=32`$ are shown in Fig. 2.

From our numerical analysis we arrive at our third result:

Result 3: *A naive adiabatic quantum searching process does not produce an optimal algorithm neither verifies step-by-step majorization*.

This property is clearly seen as the two cumulants *decrease* in time for some time steps, thus not verifying majorization.

### V.2 Analysis of the local adiabatic evolution

The preceding global adiabatic method can be improved if we apply the adiabatic condition given in equation (23) locally. That is, let us divide the interval $`[0,T]`$ into many subintervals and let us apply (23) to each of the subintervals individually. Taking the limit of the size of the subintervals going to zero, we find that the adiabatic restriction has to be fulfilled locally at each time $`t`$:

$$\frac{|\frac{dH_{1,0}}{dt}|}{g^2(t)}ϵt.$$
(25)
This is a less demanding condition than (23) (if 23 is satisfied, so is 25, but the inverse is not necessarily true), and means that the adiabatic evolution must be satisfied at each infinitesimal time interval. It can be shown (see, for example, roland ) that proceeding in this way the function $`s(t)`$ must have a precise form which is given by the relation

$$t=\frac{1}{2ϵ}\frac{N}{\sqrt{N1}}\left(\mathrm{arctan}\left(\sqrt{N1}\left(2s1\right)\right)+\mathrm{arctan}\left(\sqrt{N1}\right)\right).$$
(26)
We can observe this dynamic evolution from Fig. 3, in the case of $`ϵ=0.2`$ and $`N=32`$. The local adiabatic process implies that the smaller the energy gap between the ground and first excited states, the slower the evolution of the hamiltonian (and viceversa).

With this information it can be proven as well roland  that the evolution time for the algorithm to succeed with appreciable probability is, in the limit where $`N1`$,

$$T=\frac{\pi }{2ϵ}\sqrt{N}.$$
(27)
Hence, in the case of local adiabatic evolution the computational process takes $`O(\sqrt{N})`$ time, just as in Grover’s quantum searching algorithm, obtaining an square root speed-up with respect to a classical searching.

Defining again $`P_+(t)`$ and $`P_{}(t)`$ in the same way as in Sec. V.A, we can restrict ourselves to the analysis of the two non-trivial cumulants $`P_+(t)`$ and $`P_+(t)+P_{}(t)`$ in order to observe the evolution of majorization in the quantum process. We have numerically solved the equations for $`ϵ=0.2`$ and $`N=32`$, and have found the evolution of the two quantities, which is given in Fig. 4.

From the numerical analysis the following result emerges:

Result 4: *A local adiabatic searching algorithm is optimal and verifies step-by-step majorization*.

This result can be straightforwardly verified since the set of inequalities of (2) are satisfied step-by-step, according to the plot in Fig. 4. Due to this behavior, *the whole computational process might lead to a majorization cycle*, such as the one observed in Sec. III, as long as the previous preparation of the initial quantum state of the computation at time $`t=0`$ leads to a step-by-step reverse majorization. This turns to be always possible, for example, by applying a set of Hadamard gates to the $`\mathrm{log}N`$-qubit quantum state $`|0\mathrm{}0`$ (assume that $`N`$ is a power of $`2`$, for simplicity), which would efficiently prepare a superposition of all the possible quantum states together linked to a reverse majorization arrow. Furthermore, this quantum process leads to an increasing efficiency with respect to a classical searching, exactly in the same fashion as Grover’s original quantum searching algorithm grover .

### V.3 Analysis of slower global adiabatic evolutions

Let us now address the situation of global adiabatic evolutions which are not necessarily tight in time, that is, extremely slow time variations for the hamiltonian, much slower than the minimum necessary for the adiabatic theorem to hold. In the case we are dealing with, that implies the consideration of the case in which $`T>\frac{N}{ϵ}`$, i.e., the adiabatic inequality (24) is not tight. This case is not very relevant from a computational point of view because the hitting time is not the minimum possible, but we think it is worthwhile to be studied also from the point of view of majorization theory in order to have a more complete picture of how majorization really works in this kind of quantum algorithms.

We have performed again numerical analysis for the time evolution of the two non-trivial cumulants, for $`ϵ=0.2`$, $`N=32`$, and $`T=320,480`$ (in both cases bigger than $`\frac{N}{ϵ}=160`$). The results are plotted in Fig. 5 and Fig. 6.

From these two plots, we observe with Fig. 2, that a step-by-step majorization appears as long as the evolution of the hamiltonian becomes slower and slower. Physically, this means that the probability of “jumping” to the first excited state diminishes as long as the evolution is performed with a very small velocity, thus satisfying better the assumptions of the adiabatic theorem. This leads to processes in which there is no quantum speed-up but there is indeed a majorization arrow. However, these processes are not optimal in time, as we can always find faster quantum algorithms for solving the problem. Consequently, we arrive at the following conclusion:

Result 5: *Non-optimal quantum algorithms may present step-by-step majorization. In particular, step-by-step majorization may appear in global adiabatic searching processes for a slow enough evolution rate.*

It follows that step-by-step majorization cannot be a sufficient condition for quantum speed-up.

We can get some further intuition of the set of results presented in this section. Adiabatic quantum searching algorithms can be understood (in the limit of large $`N`$) as a rotation from the initial state to the marked state as long as the adiabaticity (either global or local) of the evolution is conveniently satisfied (see jer  for details). The difference between the global and local conditions turns out to be the evolution rate of the rotation angle: local adiabatic evolution imposes a rotation at constant rate (as in the original Grover’s algorithm) whereas global adiabatic evolution does not. Because of this rotational picture, step-by-step majorization is verified as long as the quantum state remains in the instantaneous ground state all along the computation. We can now understand our results in a finer way. Global adiabatic evolution is not a strong enough condition for adiabaticity, thus we only see step-by-step majorization when the evolution is *really* slow, in which case the quantum state adiabatically rotates towards the solution because it remains very close to the ground state of the instantaneous hamiltonian. Local adiabatic evolution is a stronger condition for adiabaticity the quantum state remains always very close to the instantaneous ground state, thus performing the rotation towards the solution which in turn involves step-by-step majorization.

### V.4 A further example: a $`2`$-SAT quantum adiabatic algorithm solving the “ring of agrees” problem

Let us consider now a different example of adiabatic quantum computation, namely, an adiabatic quantum algorithm solving the $`2`$-SAT “ring of agrees” problem, as stated in adiabatic . As long as $`2`$-SAT can be efficiently solved by a classical algorithm in a time $`O(\mathrm{poly}(n))`$ (being $`n`$ the number of bits) 2sat , quantum computation can do no better than classical computation in this case. The problem hamiltonian $`H_p`$ is now a sum of hamiltonians involving each of the different clauses of the $`2`$-SAT problem, whereas the initial hamiltonian $`H_0`$ is such that its ground state is again an equal superposition of all the possible states of the computational basis. The “ring of agrees” problem over $`n`$ bits is defined such that clause $`j`$ acts on bits $`j`$ and $`j+1`$ where $`j`$ runs from $`1`$ to $`n`$ and bit $`n+1`$ is identified with bit $`1`$. Each clause is an “agree” clause, which means that $`00`$ and $`11`$ are the satisfying assignments. The eigenvectors of the hamiltonian associated with clause $`j`$ are the computational states, in such a way that those which “agree” in qubits $`j`$ and $`j+1`$ have zero energy (ground states) whereas those which “disagree” have energy one. Because the problem hamiltonian is a sum of the $`n`$ hamiltonians for the $`n`$ “agree” clauses, its ground states are $`|0|0\mathrm{}|0`$, $`|1|1\mathrm{}|1`$, or any linear combination of them.

We have made an analysis of the adiabatic quantum algorithm in which the interpolation between the initial and problem hamiltonian is linear, $`s(t)=t/T`$, for the case of $`4`$ qubits (Hibert space of dimension $`16`$), and choosing $`T=10`$. The evolution of the $`15`$ cumulants is plotted in Fig. 7.

Note the similarity between Fig. 7 and Fig. 2 in Sec. V.A, namely, no step-by-step majorization is present in the evolution because of the oscilatory behaviour of the cumulants. Both plots represent quantum algorithms which do not improve classical computation and which probabilities share the same behaviour under the point of view of majorization. Our observation is then the following:

Result 6: *A quantum adiabatic algorithm solving the $`2`$-SAT “ring of agrees” problem does not improve classical computation, neither verifies step-by-step majorization.*

This result reinforces the ones already found with respect to adiabatic searchig algorithms.

## VI Analysis of a quantum walk in continuous time with exponential algorithmic speed-up

The extension of classical random walks to the quantum world has been widely studied, yielding two different models of quantum random walks, namely, those which operate in discrete time by means of using a “coin operator” coin1 ; coin2 ; coin3  and those based on a hamiltonian evolution in continuous time cont1 ; cont2 ; qwalk . Regarding the discrete time model of quantum random walk two interesting algorithmic results have been found so far, namely, an exponentially faster hitting time in the hypercube with respect to the classical random walk kempe1  and a quantum searching algorithm achieving the Grover’s quadratic speed-up kempe2 . The first of these examples does not provide any algorithmic speed-up, as there exists a classical algorithm that solves the hitting problem in the hypercube exponentially faster than the naive classical random walk, that is, in a time $`O(\mathrm{poly}(\mathrm{log}N))`$ where $`N`$ is the number of nodes of the graph (see qwalk ). On the other hand, the second of these examples shows algorithmic advantage with respect to any possible classical computation. The analysis of the quantum random walk searching algorithm shows that the quantum evolution can be understood as an (approximate) rotation of the quantum state in a two-dimensional Hilbert space which is exact in the limit of a very large database (see kempe2  for details), resembling the original proposal of Grover’s searching algorithm which can be decomposed exactly in a two-dimensional Hilbert space. This rotational structure of the evolutin implies step-by-step majorization when approaching the marked state, exactly in the same fashion than the usual Grover’s searching algorithm (already analyzed in lat ).

In this section we restrict ourselves to the continuous time model of quantum walk and analyze a recently proposed quantum algorithm based on a quantum walk on continuous time solving a classically hard problem qwalk . Here we restrict ourselves to briefly sketch the main points and ideas of both the problem setting and its quantum efficient solution, since the whole development of the algorithm is not the purpose of the present paper. We address the interested reader to qwalk .

### VI.1 Setting of the problem

The problem we wish to solve is defined through a graph built in the following way (see qwalk ): suppose we are given two balanced binary trees of height $`n`$ with the $`2^n`$ leaves of the left tree identified with the $`2^n`$ leaves of the right tree in a simple way, as shown in Fig. 8. A way of modifying such a graph is by connecting the leaves by a random cycle that alternates between the leaves of the two trees, instead of identifying them directly. An example of such a graph is provided in Fig. 9.

Suppose that the edges of such a graph are assigned a consistent coloring (that is, not two edges incident in the same vertex have the same color), and that the vertices are each one given a different name (with a $`2n`$-bit string, so there are more possible names than the ones assigned). We now define a black box that takes two inputs, a name $`a`$ given as a $`2n`$-bit string and a color $`c`$, and acts in the following way: if the input name $`a`$ corresponds to a vertex that is incident with an edge of color $`c`$, then the output corresponds to the name of the vertex joined by that edge; if $`a`$ is not the name of a vertex or $`a`$ is the name of a vertex but there is no incident edge of color $`c`$, the output is the special $`2n`$-bit string $`11\mathrm{}1`$, which is not the name of any vertex.

Now, the problem we wish to solve reads as follows:

*Given a black box for a graph such as the one previously described, and given the name of the IN vertex, find the name of the OUT vertex.*

In qwalk  it was proven that no classical algorithm can transverse a graph such as the one in Fig. 9 in polynomial time, given such a black box. Furthermore, an explicit contruction of a quantum algorithm based on a continuous time quantum walk on the graph that succeeds in finding the solution for this oracular problem in polynomial time was given.

### VI.2 Quantum algorithm

The quantum algorithm of qwalk  can be briefly summarized as follows: consider the $`(2n+2)`$-dimensional subspace spanned by the states

$$|\mathrm{col}j=\frac{1}{\sqrt{N_j}}\underset{a\mathrm{column}j}{}|a,$$
(28)
where $`N_j=2^j`$ if $`0jn`$ and $`N_j=2^{2n+1j}`$ if $`n+1j2n+1`$. We will call this subspace the “column subspace”, and each state of the basis is an equally weighted sum of the states corresponding to the vertices lying on each column of the graph. We now define a hamiltonian acting on this subspace in the following way:

$$\mathrm{col}j\left|H\right|\mathrm{col}\left(j+1\right)=\{\begin{array}{cc}1\hfill & 0jn1,n+1j2n\hfill \\ \sqrt{2}\hfill & j=n\hfill \end{array}$$
(29)
with hermiticity of $`H`$ giving the other nonzero matrix elements. The action of this hamiltonian in the graph is nothing but promoting transitions between adjoint vertices, so a quantum walk on the graph (on the whole Hilbert space) generated by this hamiltonian is equivalent to a quantum walk on the line (on the column subspace). Consequently, from now on we only focus our attention in the quantum walk in the line generated by the hamiltonian of (29). Moreover, it can be proven that given the structure of the graph in the form of a black box such as the one already described, our hamiltonian can be efficiently simulated qwalk .

The quantum walk works as follows: at first the “wave packet” will be precisely localized at the IN vertex (the initial state will be $`|\mathrm{col}0`$). Due to unitary time evolution, it will initially spread out through the different vertices at the left hand side of the graph (those belonging to the left binary tree), but after a short time (once half the graph has been transversed) it will begin to spread through the vertices on the right hand side, interfering constructively in the OUT vertex as the time goes on. Physically, this is nothing but a wave propagation. Should we wait more time, the wave packet would come back to the entrance, and the process would be similarly repeated again. Actually, due to the “defect” of the hamiltonian in the middle vertices, it can be shown that the transmission through the central columns is not of $`100`$ percent (thus providing interferences in long enough time scales), but high enough for the OUT node to be achieved with a very high probability. In qwalk  the authors prove that the succeeding time is polynomial in $`n`$.

### VI.3 Analysis of the quantum algorithm

We have numerically simulated this quantum walk for the particular case of $`n=4`$, and have plotted the time evolution of the probability of success in Fig. 10. We observe that the numerical result fits with the prediction that the time the algorithm takes in achieving the OUT node is polynomial.

It is easy to observe that, in order to analyze majorization, for the case of $`n=4`$ there are only $`10`$ non-trivial probabilities to be studied. This is so due to the fact that all the states of the whole Hilbert space belonging to the same column always share the same probability amplitude. The relevant quantities to be studied are then the probabilities of being at each column state normalized to the number of nodes belonging to that column, that is, the probability of being in one node of each column. There are then $`2n+2`$ different probabilities to be considered at each time step. Given only this $`10`$ quantities, we are able to calculate the whole set of $`62`$ cumulants corresponding to all the sums of sorted probabilities, according with equation (2). In order to make the figures as clear as possible we only plot $`10`$ of these quantities in Fig. 11, corresponding to the cumulants arising from the sorted probabilities when only one node per column is considered. The rest of the cumulants can be shown to have a similar behavior to that of the ones appearing in Fig. 11.

We have also numerically simulated the algorithm in the case of a bigger graph, namely, in the case $`n=10`$. In this case there are $`2n+2=22`$ different probabilities to be considered at each time step. Proceeding in the same way than in the case $`n=4`$ (that is, not plotting all the cumulants, but the only the sorted sum of these 22 probabilities), we obtain a similar behaviour as in the case for $`n=4`$, as is shown in Fig. 12.

Therefore, we arrive at the following conclusion:

Result 7: *The continuous time quantum walk transversing a classically hard graph follows a step-by-step majorization cycle all along the computation until it reaches the OUT node*.

It is worth remarking as well that the time the algorithm spends reversely majorizing the probability distribution is about half of the time of the whole computation. The physical reason for this behavior is clear, as this is the time the “wave packet” spends spreading over the binary tree on the left hand side, thus leading to a destructive interference part. It is note worthy that such a destructive interference indeed strictly follows a step-by-step reverse majorization of probabilities (satisfying the inequalities given in equation (2) for the case of reverse majorization). Furthermore, we see combining Fig. 10 and Fig. 11 that the growing of the probability of success is linked to a step-by-step majorization. Physically, this is the part in which the algorithm constructively interferes into the OUT node once the wave packet is approximately in the right hand side binary tree. We see that this constructive interference follows a majorization arrow, thus verifying step-by-step the inequalities given in equation (2). Actually, the observed majorization cycle reminds us the one already found in the quantum algorithm of Sec. III, but in this case we have numerically checked that the present cycle does not seem to follow the rules of natural majorization. Complementarily, we have also observed that the probability amplitudes follow the interesting rule that those belonging to even columns are real and those belonging to odd columns are imaginary.

The deterministic search by quantum random walk heavily exploits the column structure of the problem. The register works on a superposition of columns, that is of states belonging to the same column with equal weight. It is then natural to ask whether a step-by-step majorization cycle operates also at the level of columns. The idea behind this analysis corresponds to accept that the final measurement will filter each columns as a whole. The result of the measurement would correspond to determining a particular column. The subtle point here is to find to what extend the success of finding the OUT state is related to the column structure of the algorithm. We have numerically considered the column amplitudes for $`n=4`$ and $`n=10`$ with a total of $`9`$ and $`21`$ cumulants to be calculated respectively from the sorted probabilities at each time step of being *at each column* of the graph. In Fig. 13 and Fig. 14 we plot the result, which shows that *there does not exist a majorization cycle when the final measurement is made on columns*.

The conclusion is that deterministic quantum walks cleverly exploit the column subspace structure of the problem to achieve step-by-step majorization on the individual states.

## VII Conclusion: a Majorization Principle

We can now collect all the results found in the analysis of majorization in the quantum algorithms we have studied so far and synthesize an emerging principle underlying all of them. There are a total of nine empirical observations about step-by-step majorization:

* Presence of step-by-step majorization in Grover’s quantum searching algorithm lat .
* Presence of a natural step-by-step majorization cycle in quantum phase estimation algorithms orus .
* Presence of natural step-by-step majorization cycle in the quantum algorithm for finding hidden affine functions (Sec. III.C).
* Absence of step-by-step majorization in an optimal, yet non-efficient, quantum algorithm for solving the parity problem (Sec. IV.C).
* Absence of step-by-step majorization in naive global quantum adiabatic searching algorithms (Sec. V.A).
* Presence of step-by-step majorization in appropriate local quantum adiabatic searching algorithms (Sec. V.B).
* Emergence of step-by-step majorization for a slow enough evolution rate in quantum adiabatic searching algorithms (Sec. V.C).
* Absence os step-by-step majorization in an adiabatic quantum algorithm solving the $`2`$-SAT “ring of agrees” problem (Sec. V.D).
* Presence of step-by-step majorization cycle in a deterministic quantum walk on a graph solving a classically hard problem (Sec. VI.C).

Note that our results concerning the analysis of adiabatic quantum algorithms can have an alternative valid interpretation: according to Fig. 2 and Fig. 7, we see that the part of the processes which does not obey step-by-step majorization only occurs when the probability of succes has almost achieved its highest value. We are then led to the consideration that absence of majorization only appears once the algorithms have already constructed the right solution, having already done their job. A redefinition of the algorithm by stopping the process once the probability of the winner is maximum would lead us to affirm that step-by-step majorization is naturally present in quantum algorithms by adiabatic evolution according to the evidence presented here. This new interpretation does not alter our final result.

Adiabatic algorithmic processes do lead as well to a reverse majorization of the probability distribution in order to efficiently prepare the initial quantum state of the computation. This can be efficiently performed by a set of Hadamard gates (which produce step-by-step natural reverse majorization). Nevertheless, this remark does not only hold for the adiabatic paradigm. The usual formulation of Grover’s algorithm in terms of quantum gates needs as well of a preparation of the initial quantum state which can be carried out exactly in the same way. Similarly, all algorithms accomodate to a reverse majorization-majorization cycle. We could argue that the initial step-by-step reverse majorization procedure at the beginning of the quantum algorithms is somehow trivial, as it only involves the application of (for instance) a set of hadamard gates (with the exception of the quantum walk algorithm, in which the initial step-by-step reverse majorization is by no means trivial in the sense we state here as it is carried by the structure of the graph). The fact that the quantum evolution accomodates to a step-by-step reverse majorization-majorization cycle is reminiscent of the reversibility of these quantum algorithms.

All the results found so far suggest that a step-by-step reverse majorization-majorization cycle seems to be a *necessary* condition for efficiency in quantum computational processes, although *not sufficient*. This can be promoted to a principle:

Majorization Principle:

*Optimal quantum algorithms must follow a majorization cycle.*

This principle fits well with all the observed results given so far. Note that those processes which are not optimal do not necessarily follow the majorization cycle pattern: the case of the optimal algorithm solving the parity problem does not, while the extremely slow and inefficient but majorizing adiabatic processes do. Step-by-step majorization may be viewed as a strong irreversibility condition for success probability necessary for optimal quantum algorithms.

All our results are also consistent with a stronger statement, namely that both step-by-step majorization and large entanglement complement each other and are needed for exponential speed-up. Entanglement brings the genuine quantum mechanical tool which has to be used in an optimal way, that is verifying step-by-step majorization.

Acknowledgments: We acknowledge financial support from the projects MCYT FPA2001-3598, GC2001SGR-00065, IST-1999-11053, PB98-0685 and BFM2000-1320-C02-01. One of us (R. O.) wishes to thank A. Childs, E. Deotto, E. Farhi, J. Goldstone, S. Gutmann, A. Landahl and R. Sharma for insightful comments and stimulating discussions.


text:
# New type of lenses based upon left-handed materials

## Abstract

New type of lenses which are a slab of a left-handed material embedded into a regular material is proposed. These two materials should have equal refractive indices. Lenses with a focal length larger than the width of the slab can be constructed. These lenses should be easier to make than the well known Veselago lens, because the materials of the Veselago lens should obey an additional matching condition. Lenses of new type have multiple foci and might be useful for the 3D imaging.

In his seminal work Veselago Veselago (1967) has introduced the concept of left-handed materials (LHM’s). In a simplest case the LHM’s are materials with simultaneously negative electric permittivity $`ϵ`$ and magnetic permeability $`\mu `$ in some frequency range. It is easy to show that in LHM the vectors $`𝐤,𝐄,𝐇`$ form a left-handed set, while in usual materials ($`ϵ>0`$, $`\mu >0`$) they form a right-handed set. If the imaginary parts of $`ϵ`$ and $`\mu `$ are small, the electromagnetic waves (EMW’s) propagate in the LHM but they have some unusual properties. All these properties originate from the fact that in the isotropic LHM the Poynting vector $`𝐒=𝐄\times 𝐇`$ is anti-parallel to the wave vector $`𝐤`$.

Consider a propagation of the EMW from a point source located at the point $`z=a`$ through an infinite slab of the LHM with the thickness $`d`$ and a usual right-handed material (RHM) at $`z<0`$ and $`z>d`$ (Fig.1). We assume below that refractive indices of the LHM and the RHM are the same. This assumption excludes the total internal reflection. Then transmission coefficient of the slab is non-zero and it is obvious that $`S_z>0`$ everywhere at $`z>a`$ because the energy propagates from its source. Directions of the vector $`𝐤`$ for different rays are shown by arrows. They should be chosen in such a way that at both interfaces tangential components of vector $`𝐤`$ for incident, reflected and refracted waves are the same. Another condition is that the component $`k_z`$ should be parallel to $`S_z`$ in the RHM and anti-parallel in the LHM. It follows that the Snell’s law for the RHM-LHM interfaces has an anomalous form: $`\mathrm{sin}i/\mathrm{sin}r=n^{}/n`$, where $`i`$ and $`r`$ are the angles of incidence and refraction respectively, $`n^{}=\sqrt{|ϵ^{}||\mu ^{}|/ϵ_0\mu _0}`$ and $`n=\sqrt{ϵ\mu /ϵ_0\mu _0}`$ are positive refractive indices for LHM and RHM respectively. The angles of reflection are equal to the angles of incidence. Refractive index in the LHM’s is often defined as negative.Garcia and Nieto-Vesperinas (2002); Valanju et al. (2002); Pendry (2000); Shelby et al. (2001) It has been shown recently that introduction of the negative refractive index for the LHM’s is unnecessary and even misleading.Pokrovsky and Efros (2002a)

The device shown in Fig.1(b) is a unique optical lens proposed by Veselago.Veselago (1967) In this lens $`ϵ=ϵ^{}`$ and $`\mu =\mu ^{}`$, then $`n^{}=n`$ and $`i=r`$. It is easy to show that in this case the reflected wave is completely absent. Since all rays going right from the source have $`i=r`$, all of them have foci at points $`z=a`$ and $`z=2da`$ as shown in Fig.1(b).

Recently a method of fabricating of the left-handed metamaterials on the basis of metallic photonic crystals has been found and the San Diego group has reported the first observation of the anomalous transmission Smith et al. (2000) and even the anomalous Snell’s law.Shelby et al. (2001) Both observations have been interpreted as the result of negative $`ϵ`$ and $`\mu `$. The speculations about the nature of negative $`ϵ`$ and $`\mu `$ in the proposed metamaterials are still controversialShelby et al. (2001); Pendry (2000); Markos and Soukoulis (2001); Pokrovsky and Efros (2002b), but the very existence of the LHM seems to be demonstrated.

Pendry has proposed that the Veselago lens (VL) is a perfect lens in a sense that the width of its foci does not have usual wave length limitation. This is still a controversial point.Pendry (2000); Garcia and Nieto-Vesperinas (2002); ’t Hooft (2001); Williams (2001); Haldane ; Pokrovsky and Efros  Our paper is based upon geometrical optics only so that this unresolved question does not appear.

In this paper we propose and analyze another type of lenses, which has geometrical construction similar to the VL. In these lenses $`ϵ^{}\mu ^{}=ϵ\mu `$ like in the VL, but $`ϵ^{}ϵ`$, $`\mu ^{}\mu `$. Since $`n^{}=n`$ the absolute value of the angles of incidence, reflection and refraction is the same and this system may also work as a lens (see Fig. 2). The most important difference between the new type of lenses and the VL is the presence of reflected waves. As a consequence, the new lenses produce a periodic array of 3D images of different intensity. The lenses should be a lot easier to manufacture than the VL, because the materials for them should obey one condition only ($`ϵ\mu =ϵ^{}\mu ^{}`$) instead of two in the case of the VL ($`ϵ=ϵ^{}`$, $`\mu =\mu ^{}`$). Another advantage is that the new lenses can have a focal length greater than the width of the slab $`d`$ and produce images of objects located at distances larger than $`d`$ (Fig. 2(B)). In contrast, VL produces real images of the objects located at a distance closer than $`d`$ from the lens only.

One can see that both the VL and the new lenses are absolute instruments because they image stigmatically three-dimensional domains and the optical length of any curve in the object space is equal to the optical length of their images.Born and Wolf (1980) Note, that the above properties of the absolute instrument should be valid in the limit of geometrical optics only. For the VL this 3D domain is limited by the condition $`dz0`$, while for the new lenses it is the whole half-space $`z<0`$. Since the LHM’s have been already obtained we think that the new lenses might be extremely important for 3D imaging.

In the rest of this paper we calculate the positions of the multiple foci of the new lenses and the distribution of intensities among these foci. Since the angles of incidence, reflection and refraction are equal to each other, a simple geometric construction gives the following equations for the positions of the foci

$`z=am_0d\mathrm{and}z=\pm (2dma),`$ $`m=m_0+1,m_0+2\mathrm{},`$ $`m_0\mathrm{even}(\mathrm{or}\mathrm{zero})`$
$`z=\pm (2dma),`$ $`m=m_0,m_0+1\mathrm{},`$ $`m_0\mathrm{odd},`$
where $`m_0=\mathrm{Int}[a/d]`$, $`a`$ is the distance from the point source to the slab.

To study the intensities in the foci one should know the reflection and transmission coefficients at the RHM-LHM and LHM-RHM interfaces. As has been shown by VeselagoVeselago (1967) one can get them from the regular Fresnel expressions by substituting the absolute values of $`ϵ^{}`$ and $`\mu ^{}`$. Then the reflection and transmission coefficients at the RHM-LHM interface $`r`$, $`t`$ and LHM-RHM interface $`r^{}`$, $`t^{}`$ have a form

$$t=\frac{2ϵ}{ϵ+|ϵ^{}|},r=\frac{|ϵ^{}|ϵ}{|ϵ^{}|+ϵ}$$
(1)
$$t^{}=\frac{2|ϵ^{}|}{ϵ+|ϵ^{}|},r^{}=\frac{ϵ|ϵ^{}|}{ϵ+|ϵ^{}|}$$
(2)
These equations are valid for an arbitrary angle of incidence and polarizationJackson (1998). The multiple scattering approach gives the following expression for the intensities in the foci in the case when $`a<d`$

$$I(a)=(1r^2)I_0$$
(3)
$$I(2dma)=(1r^2)^2r^{4m4}I_0,m=1,2\mathrm{}$$
(4)
$$I([2dma])=(1r^2)^2r^{4m2}I_0,m=1,2\mathrm{},$$
(5)
where $`I_0`$ is the intensity of the source. The sum of the intensities over all foci at the right of the slab is $`I_R=I_0(1r^2)/(1+r^2)`$. The net intensity in the foci at the left of the slab is $`I_L=I_0r^2(1r^2)/(1+r^2)`$. One can check that $`I_R+I_L+I_{\mathrm{lost}}=I_0`$, where $`I_{\mathrm{lost}}=r^2I_0`$ is the intensity of the light which did not contribute to any of the foci and which is the light reflected from the first interface. Another energy conservation statement is that the intensity in the focus inside the slab $`z=a`$ is equal to the sum of the intensities over all foci at the left and at the right of the slab: $`I_L+I_R=I(a)=(1r^2)I_0`$. At a given value of $`n^{}`$ lenses of the new type differ from each other by reflection coefficient $`r`$. For a specified refractive index $`n^{}`$ one might achieve different results by choosing proper values of $`r`$. To obtain maximum intensity in the closest to the lens focus one should make $`r`$ close to $`0`$ (the limit $`r=0`$ corresponds to the VL with one focus only outside of the slab). If $`r`$ close to $`1`$, the intensities change slowly from one focus to another, thus one obtains an array of images with almost equal intensity.

Now let us study the three dimensional images produced by our lens and their spatial orientation relatively to the source (Fig. 2(A)). One can see that the images at the left side of the slab are inverted, however the images at the right side have the same orientation as the source. The image inside the slab is also inverted.

When the distance from the source to the slab satisfies the relation $`d<a<2d`$, the intensities in the foci are

$$I(2da)=(1r^2)r^2I_0$$
(6)
$$I(2dma)=(1r^2)^2r^{4m4}I_0,m=2,3\mathrm{}$$
(7)
$$I([2dma])=(1r^2)^2r^{4m2}I_0,m=1,2\mathrm{}$$
(8)
The sum of the intensities over all foci at the right of the slab is $`I_R=I_0r^4(1r^2)/(1+r^2)`$. The net intensity in the foci at the left of the slab $`I_L=I_0r^2(1r^2)/(1+r^2)`$. It is easy to show that $`I_R+I_L+I_{\mathrm{lost}}=I_0`$, where in this case $`I_{\mathrm{lost}}=[r^2+(1r^2)^2]I_0`$ is the intensity of the light which did not contribute to any of the foci. As well as in the previously considered case of $`a<d`$ we have that $`I_L+I_R`$ is equal to the intensity in the focus inside the slab $`I(2da)=r^2(1r^2)`$. At $`r`$ close to $`1`$ the intensities in the foci outside the slab change slowly from one focus to another. Figure 2(B) also shows the 3D images and their orientations. In this case the images at the left side of the slab are inverted, while the images at the right side and the image inside the slab are not. Note, that at $`a>d`$ the VL does not have any real images.

Thus, we proposed a new type of lenses on the basis of the LHM. They are easier for manufacturing than the VL, they have multiple foci, and they can produce 3D images at the distances greater than the width of the LHM slab.

The work has been funded by the NSF grant DMR-0102964.


text:
# Implement Quantum Random Walks with Linear Optics Elements

## Abstract

The quantum random walk has drawn special interests because its remarkable features to the classical counterpart could lead to new quantum algorithms. In this paper, we propose a feasible scheme to implement quantum random walks on a line using only linear optics elements. With current single-photon interference technology, the steps that could be experimentally implemented can be extended to very large numbers. We also show that, by decohering the quantum states, our scheme for quantum random walk tends to be classical.

That quantum physics differs from classical physics is due to the quantum coherence, which has been utilized to perform quantum computation such as Shor’s factoring algorithm shor  and Grover’s database search algorithm grover . However finding quantum algorithms is very difficult. Recently, several groups have investigated the quantum random walk, with the hope that it might help construct new quantum algorithms aha ; far ; Na ; 7 ; 8 ; Tra ; 10 ; du . Indeed, the first quantum algorithms based on quantum walks with an exponential speedup have been reported al . Further, Travaglione et al. proposed a scheme to implement a discrete-time quantum random walk by an ion trap quantum computer Tra  and Dür et al. proposed to use neutral atoms trapped in optical lattices to realized such quantum walks. The first experimental implementation of the quantum random walk algorithm was reported by Du et al. du .

In this paper, we propose a feasible scheme to implement quantum random walks on a line using only linear optics elements. With the defined movement and the dynamic line, we demonstrate that our scheme fulfills all requirements of the quantum random walks. With current single-photon source and its interference technology, our scheme is at the reach of current experiment. The remarkable difference between the quantum and classical random walks could be investigated with a larger number of steps. Also, by decohering the quantum states, our scheme for quantum random walk tends to be classical.

Let us consider a particle performing the discrete-time quantum random walks on a line. Besides the position degrees of freedom, the particle has an additional degree of freedom, namely the “chirality”, which takes value “Left” and “Right”. The walk by such a particle can be described as follows: at every time step, its chirality undergoes the Hadamard transformation and then the particle moves according to its (new) chirality state. In details, the chirality state is denoted by a vector in the Hilbert space spanned by $`|\text{L}`$ (Left) and $`|\text{R}`$ (Right). If the chirality state is $`|\text{L}`$ the particle moves to the left, while if the chirality state is $`|\text{R}`$ the particle moves to the right. Generally, the chirality state might be a superposition of $`|\text{L}`$ and $`|\text{R}`$, this leads the particle moving coherently to both the left and the right. It is this quantum coherence that enables the quantum random walk to remarkably outperform the classical walk.

In order to implement this quantum random walk, the essential idea is to implement the movement depending upon its “chirality” and to perform the Hadamard operation for obtaining further “chirality” for the next step. In our scheme we use the polarization states of photons to represent the “chirality”. We represent the “chirality” state $`|\text{R}`$ by the horizontal polarization photon state $`|\text{H}`$, and $`|\text{L}`$ by vertical polarization state $`|\text{V}`$. The implementation is based on simple linear optical elements, e.g. polarization beam splitters (PBS) and half-wave plates (HWP). When a superposition state passes through a PBS as shown in FIG. 1a, the PBS will direct the photon into two output ports because it transmits only horizontal component and reflects only vertical component. In order to construct the equivalence to the quantum random walk on a line, we could denote the transmission as “Right” side and the reflection as the “Left” side when photons directly pass through the PBS. However,when a superposition state directly passes through a PBS from the “Left” side, it will meet some difficulty since the horizontal component is transmitted and the vertical component is reflected. Thus we need a “modified” PBS (the $`\overline{\text{PBS}}`$) which transmits the vertical component and reflects the horizontal component. The $`\overline{\text{PBS}}`$ could be realized by rotating the polarization of the photon by $`90^0`$ with a HWP (let the angle between the HWP axis and horizontal be $`45^0`$) followed by rotating back with two HWP’s after passing through the PBS (R90 as shown in FIG. 1b). After passing through the $`\overline{\text{PBS}}`$, the horizontal component moves to the “Right” and the vertical component to the “Left”. Also, because there are different components from the two directions, one could conveniently superpose them by one PBS as shown in FIG. 1c. Therefore, with the PBS and the $`\overline{\text{PBS}}`$ (the modified PBS), we defined the photonic movement depending upon its “chirality”, i.e. polarization degree of freedom of the photons.

During the quantum random walk, one needs to perform a Hadamard operation in each step. This can easily be implemented by rotating the photonic polarization by $`45^0`$ with a HWP (by letting the angle between the HWP axis and horizontal be $`22.5^0`$). After passing the HWP (R45) it will undergo the following Hadamard transformation,

$$|\text{H}\frac{1}{\sqrt{2}}\left(|\text{H}+|\text{V}\right),$$
(1)
$$|\text{V}\frac{1}{\sqrt{2}}\left(|\text{H}|\text{V}\right).$$
(2)
With the defined movement and the Hadamard operation, we can construct the optical network to implement the quantum random walk on a line. Consider the arrangement shown in FIG. 2a, each PBS or $`\overline{\text{PBS}}`$ denotes an integer point on the line. After the initial polarization photon state $`|\mathrm{\Psi }_0`$ undergoes a Hadamard transformation and then passes through the PBS0, the horizontal component moves to the right and the vertical component to the left. Then each $`45^0`$ rotation of the polarization for two components produces the new chirality so that it could proceed the next walk. The transmitted components move to the integer $`2`$ and $`2`$ respectively, and the horizontal component reflected from $`\overline{\text{PBS}}_1`$ and the vertical component from PBS1 will overlap at the PBS$`{}_{}{}^{^{}}{}_{0}{}^{}`$. Here it should be noted that, in order to let all components move forward and not mix with further input states, we shall introduce a new PBS$`{}_{}{}^{^{}}{}_{0}{}^{}`$ to replace the PBS0, which is equivalent to move the integer $`0`$ to $`0^{}`$. The integers $`1`$, $`0^{}`$, $`1`$ compose a new line, leading to convenient measurement after the random walk, as will be explained later. The state coming out from PBS1, PBS$`{}_{}{}^{^{}}{}_{0}{}^{}`$ and $`\overline{\text{PBS}}_1`$ further undergoes a Hadamard operation and then performs the next step of the walk. The transmitting components from PBS2 and $`\overline{\text{PBS}}_2`$ will move to the position $`3`$ and $`3`$ respectively. The two components reflected from PBS2 and PBS$`{}_{}{}^{}{}_{0}{}^{}`$ will overlap at PBS$`{}_{}{}^{}{}_{1}{}^{}`$ and the other components reflected from $`\overline{\text{PBS}}_2`$ and PBS$`{}_{}{}^{}{}_{0}{}^{}`$ will overlap at PBS$`{}_{}{}^{}{}_{1}{}^{}`$. Introducing PBS$`{}_{}{}^{}{}_{1}{}^{}`$ and PBS$`{}_{}{}^{}{}_{1}{}^{}`$ to replace the PBS1 and $`\overline{\text{PBS}}_1`$ has the same reason as introducing the PBS$`{}_{}{}^{}{}_{0}{}^{}`$. The integers $`3`$, $`1^{}`$, $`1`$, and $`3`$ assemble a new line and one can position four detectors behind them to measure the probability distribution after three steps. By iterating the above steps, we could implement random walk on a line with the unlimited steps in principle by simply adding more PBS’s, $`\overline{\text{PBS}}`$’s and HWP’s. This optical network for quantum random walk for arbitrary $`N`$ steps is shown in Fig. 2b.

The essential idea in our scheme is to introduce the dynamic line, which is equivalent to the original line on which the walk is performed. With the moving integer positions we could fulfill all the requirement for the quantum random walk in a line and the scheme provide us a convenient method to measure the distribution after certain steps. Furthermore, it is easily found that the general quantum random walk proposed in Ref. Na  can also be implemented in our scheme, by rotating the photonic polarization by arbitrary angle $`\theta `$ with the HWP (Rθ) rather than $`45^0`$ when performing the Hadamard transformation. Note that in this case the angle between the HWP axis and horizontal should be $`\theta /2`$.

So far, we have described the quantum random walk on a line. We now discuss how to realize it experimentally. To implement the quantum random walk, the source that produces single photons is demanded. It is available with quantum-dot single photon sources kim ; kur ; lou ; fod  or with parametric down conversion kwiat  by performing a measurement on one photon. In the quantum random walk, the probability distribution is strongly dependent upon its initial state. The general input $`|\mathrm{\Psi }_0=\mathrm{cos}\theta |\text{H}+e^{i\phi }\mathrm{sin}\theta |\text{V}`$ can be easily obtained by letting single-photon sources pass through two QWP’s and a HWP englert . The key requirement for the experimental realization is to overlap the horizontal component and the vertical one on the PBS in order to utilize the quantum coherence. This could be achieved, such as in the Rome teleportation experiments martini . Finally, the features of the quantum walks could be investigated by positioning detectors behind the PBS’s at the final step. All these requirements have been in the reach of the current technology of linear optics. Also, since the single photon source is very bright, the steps for the quantum random walk are scalable. This is comparative to other scheme such as ion trap Tra  or NMR system du  with only a few steps. Therefore, with our scheme one can investigate quantum random walks with any initial state for a large number of steps. It should be noted that, whenever taking odd steps or even steps, we need only measure the distribution in the odd positions or in even positions, respectively. But it will not lead to any contradiction because it is obvious that, for either the quantum random walk or the classical one, the probability is zero at even (odd) positions when taking odd (even) steps.

As described by many authors, the remarkably distinguished features between the quantum random walk and the classical one stem from the quantum coherence. However, one could implement the classical random walk by decohering quantum states in our scheme. With slight modification of our scheme, this can be realized by appropriately placing phase shifts more than coherence length of single photon in the optical network, so that the state of the quantum walk decoheres after each step. Therefore, our scheme could be fully used to compare the remarkable features such as the probability distribution and the standard deviation to the classical one for random walk on a line. Further, by changing the phase shift between zero and the coherence length, it is also possible to investigate the decoherence effect in the quantum random walk in experiments.

In conclusion, we have proposed a feasible scheme to implement the quantum random walk on a line with linear optics elements. In the scheme we construct the dynamic line so that we could conveniently measure the probability distribution after certain steps. With nowadays single photon interference technology and highly precise linear optics elements, our scheme are flexible and scalable, and could be implemented experimentally for any initial state with a large number of steps. The experimental realization of quantum random walk also provides us a valuable estimation for quantum computer with linear optics.

This work was supported by the National Natural Science Foundation of China, Chinese Academy of Sciences and the National Fundamental Research Program (Grants No. 2001CB309303 and 2001CB309300).