text:
Code covered by the BSD License

Teaching System Dynamics with MATLAB & Simulink

Jerry Brusher (view profile)

MATLAB, Simulink, MuPAD, & Simscape models of 2nd order systems used in “Teaching System Dynamics.”

publish_spring_mass_damper_free_response.m
%% Transient Behavior and Location of Characteristic Roots in the Complex Plane
% Copyright 2011 The MathWorks, Inc.
%% Initial Value Problem
%
% Consider the system described by the following second-order,
% ordinary differential equation and associated initial conditions:
%
% $$\frac{d^2x}{dt^2} + 2\zeta\omega_n\frac{dx}{dt} + \omega_n^2x = 0; x(0)=x0,\frac{dx}{dt}(0)=0$$
%
% We would like to examine the behavior of the free response of the
% system as the damping ratio changes.  This will be done first by solving
% the initial value problem for various damping ratios and plotting the
% results.  Then, we will explore changes in the damping ratio affect the
% characteristic roots.  (Recall that the characteristic roots dictate the
% free-response behavior.)

%% Set physical and derived parameters.
%
% To enable numerical solution of the differential equation, we will set
% specific values for the mass and (linear) spring rate.  We will then use
% these to derive the (circular) natural frequency.
%
param.m = 1;                            % Mass [kg]
param.k = 1;                            % Spring rate [N/m]
param.wn = sqrt(param.k/param.m);       % (Circular) natural frequency [rad/s]

%% Set initial conditions.
%
% To solve our 2nd order differential equation, we need two initial
% conditions: one on position, the other on velocity.  Moreover, recall
% from the accompanying PowerPoint slides that we have represented our
% 2nd order linear ODE into a system of 1st order ODE's amenable to
% solution using MATLAB. Having defined position and velocity as our
% system states, we must define an initial state vector.

x0 = 1;              % Position [m]
x0_dot = 0;          % Velocity [m/s]
z0 = [x0 ; x0_dot];  % Initial condition on state vector

%% Set simulation parameters.
%
% We will define the duration of our simulation to be approximately 4
% periods.  To accommodate changes in physical parameters, we will
% parameterize the duration by the natural frequency.  We then define the
% associated time step and vector of simulation time.  Note that the time
% step dt serves to define the times at which output will be provided, not
% the solver time step.

tend = 4*round((2*pi)/param.wn);    % Simulate for approximately 4 periods [s]
dt = round((2*pi)/param.wn)/1000;   % Time step [s]
tsim = 0:dt:tend;                   % Vector of simulation times [s]

%% Undamped system.
%
% We first consider an undamped system, characterized by a damping ratio of
% zero.  Physically, this represents a system with zero dissipation of
% energy.  We will plot the free response to confirm the expected behavior.
%
% To solve the system of 1st order ODE's, we will use the baseline ode45
% solver.  The solver requires a vector of state derivatives; in this
% case, we call upon a function to define them.

param.zeta = 0;     % Damping ratio

[t,z] = ode45(@(t,z) odesys( t,z,param ),tsim,z0);
x(:,1) = z(:,1);    % Save solution for future plotting.

plot(t,x(:,1),'linewidth',2);grid on;hold all

ylim([-1 1])
xlabel('Time [s]');
ylabel('Position [m]')
title('Free Response: Undamped 2nd Order System');

%% Consider several damping ratios.
%
% Now we will consider four distinct values of the damping ratio
% corresponding to four distinct types of system behavior: undamped,
% underdamped, critically damped, and overdamped.  These terms refer to the
% behavior of the system as it returns to its equilibrium state.  We will
% plot and compare the free responses for these cases.

zetavals = [0 1/sqrt(2) 1 1.5]; % Damping ratios to consider.

case1 = 'Undamped: zeta = 0' ;
case2 = 'Underdamped: zeta = 0.707' ;
case3 = 'Critically Damped: zeta = 1' ;
case4 = 'Overdamped: zeta = 1.5' ;

for i = 2: length(zetavals)

param.zeta = zetavals(i); % Set current damping ratio.
[t,z] = ode45(@(t,z) odesys( t,z,param ),tsim,z0); % Compute free response.
x(:,i) = z(:,1); % Save solution for future plotting.

end;

figure      % Plot results

plot(t,x,'linewidth',2);grid on
xlabel('Time [s]');
ylabel('Position [m]')
title('Free Response of 2nd Order System for Various Damping Ratios');
legend(case1,case2,case3,case4,0)

%% Track characteristic roots as damping ratio increases.
%
% Recalling that the free response of a system is governed by its
% characteristic roots, we will examine the changes in these roots as the
% damping ratio changes over a more finely spaced set of values.  Since the
% roots may have real and imaginary parts, we will plot them in the complex
% plane.  For each value of the damping ratio, we will compute the
% characteristic roots as the eigenvalues of the associated state matrix.

zeta_range = 0:0.01:1.5;          % Damping ratio: undamped to overdamped.
S = zeros(2,length(zeta_range));  % Initialize characteristic roots array.

for i = 1:length(zeta_range)

S(:,i) = eig([0 1; -param.wn^2 -2*zeta_range(i)*param.wn]); % Characteristic roots.

end;

figure      % Plot characteristic roots in complex plane.

plot(S,'bx','linewidth',2,'markersize',5); grid on;
set(gca,'YAxisLocation','right')
xlabel('Real Axis','Position',[-1.5 -0.1 1])
ylabel('Imaginary Axis')
title('Loci of Characteristic Roots in Complex Plane for Various Damping Ratios')

%% Show the "odesys" function.
%
% Here we record the function used to define the state matrix
% corresponding to our system of ordinary differential equations.

type odesys.m


text:
lag {stats} R Documentation

## Lag a Time Series

### Description

Compute a lagged version of a time series, shifting the time base back by a given number of observations.

lag is a generic function; this page documents its default method.

### Usage

lag(x, ...)

## Default S3 method:
lag(x, k = 1, ...)

### Arguments

 x A vector or matrix or univariate or multivariate time series k The number of lags (in units of observations). ... further arguments to be passed to or from methods.

### Details

Vector or matrix arguments x are given a tsp attribute via hasTsp.

### Value

A time series object with the same class as x.

### Note

Note the sign of k: a series lagged by a positive k starts earlier.

### References

Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) The New S Language. Wadsworth & Brooks/Cole.

diff, deltat
lag(ldeaths, 12) # starts one year earlier

format: plain


text:
# Why does $i^2 = -1$?

I understand that $i = \sqrt{-1}$, but it seems as if $i^2$ would be:

$$\sqrt{-1}\sqrt{-1} = \sqrt{1} = \pm 1$$

Why is this not the case?

-
Because $\sqrt{1}=1$, not $\pm 1$. –  JohnD Feb 4 '13 at 20:06
By definition, $\sqrt{1} > 0$ and so $\sqrt{1} \neq -1$. If $x^2=1$ then $x = \pm\sqrt{1} = \pm 1$. –  Fly by Night Feb 4 '13 at 20:06
Then why is √1 by definition greater than 0? √25, for instance is ±5, no? –  Smovies Feb 4 '13 at 20:09
No. The solution to the equation $x^2=25$ is $x=\pm 5$ because $(5)^2=(-5)^2=25$. By definition, the symbol $\sqrt{25}$ means the positive number whose square is 25. That's why you get $\pm \sqrt{25}$ in solutions, one is positive: namely $\sqrt{25}$ and one is negative: namely $-\sqrt{25}$. –  Fly by Night Feb 4 '13 at 20:12
This was a double-whammy of misconceptions :) –  rschwieb Feb 4 '13 at 20:22

If I understand correctly, you're thinking is as follows: $$\ \sqrt{-1}\sqrt{-1} = \sqrt{(-1)(-1)} = \sqrt{1} = \pm 1.$$

I'll address the primary question here: in writing this, you are assuming the "rule" that tells us: $$\sqrt{ab} = \sqrt{a}\sqrt{b}$$ also applies to $a, b$ when both are negative. However:

$\sqrt{ab} = \sqrt a\sqrt b\;$ if and only if $a$ and $b$ are not both negative real numbers.

The usual laws of exponents (and roots) do not apply to complex imaginary numbers, nor, in the case of the square root, do they apply to negative numbers of any sort.

-
It seems that if either a OR b were negative, though, the usual rule would apply, as in: (√5)(√-3) = √-15 ? –  Smovies Feb 4 '13 at 20:11
Yes, then you could write $\sqrt{-15}$ as $i\sqrt {15}$, or rather, $\sqrt 5 \sqrt {-3} = i\sqrt 5 \sqrt 3 = i\sqrt{15}$ –  amWhy Feb 4 '13 at 20:12
@amWhy Not exactly. "However: √ab =√a√b if and only if a,b are non-negative real numbers." We just showed above that √ab = √a√b when a OR b is negative, no? As in: (√a)(√-b) = √-ab –  Smovies Feb 4 '13 at 20:30
As Smovies points out, the "if and only if" part as stated is false. For real $a,b$, the rule $\sqrt{ab}=\sqrt{a}\sqrt{b}$ will be true if and only if $a,b$ are not both negative, i.e. if $a$ or (not and) $b$ is nonnegative. –  anon Feb 4 '13 at 21:16
In order to ask meaningfully whether $\sqrt{ab}=\sqrt{a}\sqrt{b}$ is true, one has to have definitions fixed for what $\sqrt{ab}$, $\sqrt{a}$, and $\sqrt{b}$ mean. Only in the case where $a\geq 0$ and $b\geq 0$ is there a fairly universal canonical definition of $\sqrt a$ and $\sqrt b$. When extending the notation $\sqrt{a}$ by defining particular branches of the square root on subsets of the complex plane, whether or not such identities hold will depend on the branches chosen and the particular $a$,$b$ chosen. It will hold sometimes when neither $a$ nor $b$ is real. –  Jonas Meyer Feb 5 '13 at 2:15

The rule that $\sqrt{ab} = \sqrt{a}\sqrt{b}$ only holds when $a, b$ are positive.

To add some more context: these rules hold only for positive numbers for a few reasons, but in general, the existence of complex numbers is something necessitated by an inadequacy of the reals to solve certain types of problems.

In a way, we might look at $i^2 = -1$ as a definitive property of $i$ (that is, a property that holds because we define it to be so), rather than a consequential property.

Complex arithmetic is essentially synthetic: it's something we made up. It happens that the rules we chose are very useful and have exceptionally nice properties, so we stick with them.

But in the end, we define $(a,b)(c,d) = (ac-bd,ad+bc)$. This is exactly equivalent to defining $i^2 = (0,1)(0,1) = (-1,0)$.

-
Isn't defining property less odd? –  Mariano Suárez-Alvarez Feb 4 '13 at 20:13
@MarianoSuárez-Alvarez That's perhaps a question for English.SE. –  Arkamis Feb 4 '13 at 20:15
Not really: I have never seem definitive used in that way in the many, many years I have spent reading math, and always seen defining. I have seen definitive used that way in other contexts, though. –  Mariano Suárez-Alvarez Feb 4 '13 at 20:17
The participle as an adjective is a crude option when a perfectly suitable---and much more pleasant sounding---alternative is available, regardless of discipline. ;) –  Arkamis Feb 4 '13 at 20:19
In fact, I would say that this at least confusing. I do not care that much really. –  Mariano Suárez-Alvarez Feb 4 '13 at 20:28

It seems like you are thinking that $$\ \sqrt{-1}\sqrt{-1} = \sqrt{(-1)(-1)} = \sqrt{1} = 1.$$ As others have already mentioned, in doing this, you are assuming that $$\sqrt{ab} = \sqrt{a}\sqrt{b}$$ but this rule only holds for non-negative real numbers.

One way to think about $i$ is simply as something whose square is $-1$. You can then defined the complex numbers as all linear combinations $a + bi$, where $a$ and $b$ are real numbers. Now when you start to manipulate/use algebra with these complex numbers you just remember that $i^2 = -1$ (by definition). Likewise some math books will simply define that for a positive real number $a$ $\sqrt{-a}$ is $i\sqrt{a}$.

The morale of all this is that when you move on to something "new" in math, you have to be very careful because the "usual" rules don't always apply.

-
Ah, that's clearer. I undertand it, for sure, taking i^2 = -1 as a first principle. It just seems inelegant to have to that and I wanted to understand it from the perspective of the first principle i = √-1 –  Smovies Feb 4 '13 at 20:15

A main misconception here is that $\sqrt{a^2}=\pm a$. That is not true, but $\sqrt{a^2}=|a|$ is true for any real number $a$.

What you are confusing it with is solving the equation $x^2=c$. Some students are taught to "take the square root of both sides, but to avoid dropping a solution, use $\pm$":

$$x=\pm\sqrt{c}$$

It's important not to confuse these two things: finding the square root of a number, and solving an equation of the form $x^2=c$.

-
$\sqrt{a^2}=|a|$ is true when $a$ is real and $\sqrt{}:[0,\infty)\to[0,\infty)$. (I thought it might be worth mentioning because there are also nonreal numbers in the question.) –  Jonas Meyer Feb 5 '13 at 2:09
@JonasMeyer That's worth adding: thanks. –  rschwieb Feb 5 '13 at 12:50

It may help to avoid using the $\sqrt{}$ notation, but rather exponents. Remember that $\sqrt a$ is actually $a^{1/2}$.

Your argument is then this. Why cannot we do: $(-1^{1/2})(-1^{1/2}) = (-1\cdot -1)^{1/2} = 1^{1/2} = 1$?

But how the product of powers of the same base actually works is this: $x^ax^b = x^{a+b}$.

So, in other words, $-1^{\frac{1}{2} + \frac{1}{2}} = -1^1 = -1$.

We cannot simply take things out from under the exponent and multiply them out!

In the case that $a = b$, it reduces to $x^ax^a = x^{2a}$.

So then the pattern you're trying to follow looks like this, with exponents: $x^ax^a = x^{2a} = (x^2)^a = (xx)^a$. Now, that is actually correct depending on the nature of the $x$ and $a$, but not when $x$ is negative and $a$ is fractional.

The problem is that the exponent law $x^{(mn)} = (x^m)^n$ does not hold in general. It does not hold when $x$ is negative and $m$ or $n$ are fractional.

-

if you square the square root of 'something', the result is equal to the 'something' i.e. the (square root of two) squared is equal to two

-


text:
# Multiple Choice Questions on Transformer |13

1. A 300 kVA, single phase transformer is designed to have resistance of 1.5 % and max. efficiency occurs at load of 173.2 kVA. When supplying the full load at 0.8 p.f. lagging at normal voltage the efficiency will be

$\%R=\frac{full\; load\; copper\; loss}{full\; load \;V_2I_2}\times100$
$1.5=\frac{full\; load\; copper\; loss}{300\times1000}\times100$
$Therefore, full\; load\; copper\; loss = \frac{1.5\times300\times1000}{100} = 4500\;watt$
$Also,\; 173.2 = 300 \sqrt{\frac{iron\;loss}{4500}}\;or\;iron\; loss = 1500\;watt$
$Total\; full\; load\; loss\; = 4500 + 1500 = 6 \;kW$
$Full\; load\; efficiency\; \eta\;at\; 0.8 \;p.f. =\frac{300\times0.8}{300\times0.8+6}\times100 = 97.6\%$

2. The maximum efficiency of 100 kVA; single phase transformer is 95 % and occurs at 80 % of full load at 0.8 p.f. If the leakage impedance of the transformer is 5 % the voltage regulation at rated load of 0.8 p.f lagging will be

Since maximum efficiency occurs at 80 % of full load at 0.8 p.f., the output at ηmax is $100\times0.8\times0.8 = 64kW\;Input = \frac{64}{0.98}=65.3\; kW$
∴ Total loss = 65.3 - 64 = 1.3 kW.
This loss is divided equally between Cu and Iron.
$Therefore,\; Cu\; loss\; at\; 80\% \;of\; full\; load\; = \frac{1.3}{2}= 0.65 kW$
$Cu\; loss\; at\; full\; load\; =\frac{0.65}{0.8^2} = 1 kW$
$\%R = \frac{Cu\; loss}{V_2I_2}\times100 = 1\times\frac{100}{100} = 1\% = v_r; and\;v_x = 5\%(Given)$
$Therefore, \%\; regulation = \frac{(1\times0.8+5\times0.6)+1}{200(5\times0.8-1\times0.6)^2} = 0.166\%$

3. Emf equation a transformer is equal to

Emf equation of a transformer is E = 4.44 φfT.
Where f = frequency in Hz, φ = flux in weber, T = no. of turns.

4. Which loss occur in magnetic core of transformer?

Loss that occurs in magnetic core of transformer is iron losses which is sum of the hysteresis loss and eddy current loss. Hysteresis loss and eddy current loss, both depend upon magnetic properties of the materials for construction of transformer core and its design. So these losses in transformer are fixed and do not depend upon the load current.

5. In open circuit (O.C) test of transformer which side is kept open?

Open circuit is performed with HV side ( high voltage ) side kept open. The open circuit test or no-load test, is one of the methods used to determine the no-load impedance in the excitation branch of a transformer.

6. In short circuit test LV side is

In short circuit test low voltage winding LV side is short circuited. The test is conducted on the high voltage (HV) side of the transformer where the low voltage (LV) side or the secondary is short circuited.

7. All day energy efficiency is related to which of the transformer?

Distribution transformer is connected to the line for 24 hrs / day.
All day energy efficiency = ratio of the energy output to that of energy input taken over 24 hours.

8. There are how many three phase transformer groups?

There are 4 groups- Gr - I (no phase displacement)
Gr - II ( 180° phase displacement )
Gr - III ( - 30° phase displacement )
Gr - IV ( + 30° phase displacement).

9. When the iron and full load copper loss in transformer are 900 W and 1600 W respectively the maximum efficiency occurs at

Maximum efficiency at = kVA × √( Wi / Wcu )
= kVA × √ ( 900 / 1600 ) = 75 % of full load.
Where Wi = iron loss, Wcu = copper loss.

10. With 30 % tapping on its auto transformer stater the staring torque of a 3 phase induction motor is 100 N-m if 60 % tapping is utilized the new starting torque would be

Since T ∝ V2, when 60% of tapping is used voltage applied to motor is doubled when compared to 30 % of tapping hence torque becomes 4 times.

11. The individual maximum demands on feeder connected to a transformer are 100, 200, 80, 50, 70 kW if the max. Demand experienced by the transformer is 300 kW the diversity factor of the load on it is.

Diversity factor = sum of maximum demand / maximum demand = 100 + 120 + 80 + 50 + 70 / 300 = 1.4.

12. The energy supplied to a HT consumer is recorded by an energy meter in conjunction with PT of 11 KV / 110 V and CTs of 50 / 5 A. If the meter records 10000 units the actual energy supplied is

CT ratio = 50 / 5 , PT ratio = 11000 / 110 = 100
Actual energy supplied = meter reading × PT ratio × CT ratio = 1000 × 100 × 10 = 10 million units.


text:
convert - Maple Help

# Online Help

###### All Products    Maple    MapleSim

The convert Function in the Natural Units Environment

Description

 • In the Natural Units environment, the global convert function is replaced by a convert function that converts any unevaluated arithmetic operators, equalities, or inequalities to their global equivalents.  The first argument is tested to check whether it is a valid unit name.
 • For more information about this function, see the global convert help page.
 > with(Units[Natural]):
 > :-convert('m', 'units', 'ft');  # the 'm' is not interpreted as a meter
 > convert('m', 'units', 'ft');
 $\frac{{1250}}{{381}}{}⟦{\mathrm{ft}}⟧$ (1)

 See Also


text:
# Functional estimates for derivatives of the modified Bessel function and related exponential functions

Falletta, Silvia; Sauter, Stefan A (2014). Functional estimates for derivatives of the modified Bessel function and related exponential functions. Journal of Mathematical Analysis and Applications, 417(2):559-579.

## Abstract

Let K0K0 denote the modified Bessel function of second kind and zeroth order. In this paper we will study the function View the MathML sourceω˜n(x):=(−x)nK0(n)(x)n! for positive argument. The function View the MathML sourceω˜n plays an important role for the formulation of the wave equation in two spatial dimensions as a retarded potential integral equation. We will prove that the growth of the derivatives View the MathML sourceω˜n(m) with respect to n can be bounded by O((n+1)m/2)O((n+1)m/2) while for small and large arguments x the growth even becomes independent of n . These estimates are based on an integral representation of K0K0 which involves the function View the MathML sourcegn(t)=tnn!exp(−t) and its derivatives. The estimates then rely on a subtle analysis of gngn and its derivatives which we will also present in this paper.

## Abstract

Let K0K0 denote the modified Bessel function of second kind and zeroth order. In this paper we will study the function View the MathML sourceω˜n(x):=(−x)nK0(n)(x)n! for positive argument. The function View the MathML sourceω˜n plays an important role for the formulation of the wave equation in two spatial dimensions as a retarded potential integral equation. We will prove that the growth of the derivatives View the MathML sourceω˜n(m) with respect to n can be bounded by O((n+1)m/2)O((n+1)m/2) while for small and large arguments x the growth even becomes independent of n . These estimates are based on an integral representation of K0K0 which involves the function View the MathML sourcegn(t)=tnn!exp(−t) and its derivatives. The estimates then rely on a subtle analysis of gngn and its derivatives which we will also present in this paper.

## Statistics

### Citations

1 citation in Web of Science®
1 citation in Scopus®


text:
## Section2.1Strings: A First Look

Let $$n$$ be a positive integer. Throughout this text, we will use the shorthand notation $$[n]$$ to denote the $$n$$-element set $$\{1,2,\dots,n\}\text{.}$$ Now let $$X$$ be a set. Then a function $$s\colon[n]\rightarrow X$$ is also called an $$X$$-string of length $$n$$. In discussions of $$X$$-strings, it is customary to refer to the elements of $$X$$ as characters, while the element $$s(i)$$ is the $$i^{\text{th} }$$ character of $$s\text{.}$$ Whenever practical, we prefer to denote a string $$s$$ by writing $$s=$$“$$x_1x_2x_3\dots x_n$$”, rather than the more cumbersome notation $$s(1)=x_1\text{,}$$ $$s(2)=x_2\text{,}$$ …, $$s(n)=x_n\text{.}$$

There are a number of alternatives for the notation and terminology associated with strings. First, the characters in a string $$s$$ are frequently written using subscripts as $$s_1,s_2,\dots,s_n\text{,}$$ so the $$i^{\text{th} }$$-term of $$s$$ can be denoted $$s_i$$ rather than $$s(i)\text{.}$$ Strings are also called sequences, especially when $$X$$ is a set of numbers and the function $$s$$ is defined by an algebraic rule. For example, the sequence of odd integers is defined by $$s_i=2i-1\text{.}$$

Alternatively, strings are called words, the set $$X$$ is called the alphabet and the elements of $$X$$ are called letters. For example, $$aababbccabcbb$$ is a $$13$$-letter word on the $$3$$-letter alphabet $$\{a,b,c\}\text{.}$$

In many computing languages, strings are called arrays. Also, when the character $$s(i)$$ is constrained to belong to a subset $$X_i\subseteq X\text{,}$$ a string can be considered as an element of the cartesian product $$X_1\times X_2\times \dots\times X_n\text{,}$$ which is normally viewed as $$n$$-tuples of the form $$(x_1,x_2,\dots,x_n)$$ such that $$x_i\in X_i$$ for all $$i\in [n]\text{.}$$

###### Example2.1.

In the state of Georgia, license plates consist of four digits followed by a space followed by three capital letters. The first digit cannot be a $$0\text{.}$$ How many license plates are possible?

Solution.

Let $$X$$ consist of the digits $$\{0,1,2,\dots,9\}\text{,}$$ let $$Y$$ be the singleton set whose only element is a space, and let $$Z$$ denote the set of capital letters. A valid license plate is just a string from

\begin{equation*} (X-\{0\})\times X\times X\times X\times Y\times Z\times Z\times Z \end{equation*}

so the number of different license plates is $$9\times10^3\times1\times 26^3=158\,184\,000\text{,}$$ since the size of a product of sets is the product of the sets' sizes. We can get a feel for why this is the case by focusing just on the digit part of the string here. We can think about the digits portion as being four blanks that need to be filled. The first blank has $$9$$ options (the digits $$1$$ through $$9$$). If we focus on just the digit strings beginning with $$1\text{,}$$ one perspective is that they range from $$1000$$ to $$1999\text{,}$$ so there are $$1000$$ of them. However, we could also think about there being $$10$$ options for the second spot, $$10$$ options for the third spot, and $$10$$ options for the fourth. Multiplying $$10\times 10\times 10$$ gives $$1000\text{.}$$ Since our analysis of filling the remaining digit blanks didn't depend on our choice of a $$1$$ for the first position, we see that each of the $$9$$ choices of initial digit gives $$1\, 000$$ strings, for a total of $$9\,000 = 9\times 10^3\text{.}$$

In the case that $$X=\{0,1\}\text{,}$$ an $$X$$-string is called a $$0$$–$$1$$ string (also a binary string or bit string.). When $$X=\{0,1,2\}\text{,}$$ an $$X$$-string is also called a ternary string.

###### Example2.2.

A machine instruction in a $$32$$-bit operating system is just a bit string of length $$32\text{.}$$ Thus, there are $$2$$ options for each of $$32$$ positions to fill, making the number of such strings $$2^{32} = 4\,294\,967\,296\text{.}$$ In general, the number of bit strings of length $$n$$ is $$2^n\text{.}$$

###### Example2.3.

Suppose that a website allows its users to pick their own usernames for accounts, but imposes some restrictions. The first character must be an upper-case letter in the English alphabet. The second through sixth characters can be letters (both upper-case and lower-case allowed) in the English alphabet or decimal digits ($$0$$–$$9$$). The seventh position must be ‘@’ or ‘.’. The eighth through twelfth positions allow lower-case English letters, ‘*’, ‘%’, and ‘#’. The thirteenth position must be a digit. How many users can the website accept registrations from?

Solution.

We can visualize the options by thinking of the $$13$$ positions in the string as blanks that need to be filled in and putting the options for that blank above. In Figure 2.4, we've used U to denote the set of upper-case letters, L for the set of lower-case letters, and D for the set of digits.

Below each position in the string, we've written the number of options for that position. (For example, there are 62 options for the second position, since there are $$52$$ letters once both cases are accounted for and $$10$$ digits. We then multiply these possibilities together, since each choice is independent of the others. Therefore, we have

\begin{equation*} 26\times 62^5 \times 2 \times 29^5\times 10 = 9\,771\,287\,250\,890\,863\,360 \end{equation*}


text:
Tag Info

21

One major application of topology in semantics is the topological approach to computability. The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it ...

9

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of $n$ points $(x_i,y_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes ...

8

The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. For any fixed $\varepsilon>0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard. There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{... 7 The problem is$\mathsf{NP}$-hard. See [GT41] DIRECTED BANDWIDTH in Garey and Johnson. 6 Since you only care about embeddings in the plane, and every oriented homeomorphism of the plane is isotopic to the identity (Alexander's trick), testing whether two embedded graphs are isotopic is equivalent to testing whether they are congruent by an oriented homeomorphism. And this is a purely combinatorial notion: for example it is equivalent to the two ... 5 I wanted to add to JɛﬀE's comprehensive answer that to the best of my knowledge there are no lower bounds on the approximation factor for this problem. As far as we know, there can be an approximation algorithm that always gives a constant factor approximation (even if the genus is very small). The paper Chen, Kanchi, and Kanevsky [CKK '97] only says that ... 4 A combinatorial embedding or signed rotation system is a combinatorial representation of a cellular embedding of a graph on some surface. An embedding is a drawing of the graph such that no two edges cross; an embedding is cellular if every face is a disk. Consider an undirected graph$G=(V,E)$. It is helpful to regard each edge in$E$as a pair of ... 4 I had an answer here involving apex graphs but it fails the definition of not having an explicit obstruction set given in this question: there is a published algorithm for finding the obstruction set, even though is too slow to run so we don't actually know what the obstruction set is. So here's another parameterizable family of answers without that flaw (... 4 The 2004 Gödel Prize was shared between the papers: The Topological Structure of Asynchronous Computation. By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923 Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge. By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483. Quotes ... 4 Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been characterized using topology. Defining Liveness Alpern and Schneider Safety and Liveness in Branching time Manolios et. al. 3 (All of the below is assuming your graphs are connected.) Every isotopy class of graphs with$e$edges embedded in the sphere (which is almost the plane) corresponds to a pair of permutations$\sigma,\tau$on$2e$letters which satisfy$(\sigma\tau)^2 = 1$, and$\sigma,\tau$are determined up to simultaneous conjugacy (the dual graph corresponds to the pair ... 3 The additional constraint amounts to saying that the input DAG has width$\leq k$, i.e., there is no antichain of size$k+1$. In this case, if$k$is a constant, the decision version of the constrained topological sorting problem is in NL by Prop C.2 of https://arxiv.org/abs/1707.04310, which amounts to a PTIME dynamic programming algorithm. Reconstructing a ... 2 Regarding (3), yes, if a graph$M$has two vertex disjoint non-planar induced subgraphs$G$and$H$, then$G\cup H$(and hence$M$) is not toroidal. I don't know a reference but here's a proof sketch. Thinking of the torus as$T=S^1\times S^1$, if a non-planar$G$is embedded without crossing on$T$then its edges must meet every$S^1\times\{a\}$and$\{a\...

1

Iterate DAG-Shortest-Paths (in Cormen, Lesierson, Rivest, and Stein's text "Introduction to Algorithms").

1

[Reposting comment as an answer, based on the OP's response to the comment.] For a combinatorial definition, it seems like what you're looking for is a circular ordering around the vertices together with a map $f$ from the set of components to the set of faces such that $f(C_i)$ is the face of the graph that contains the component $C_i$. If you prefer a ...

1

Archdeacon's survey Topological Graph Theory was almost mentioned already: http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Program to count minimum semesters to cover all different courses in Python

PythonServer Side ProgrammingProgramming

#### Beyond Basic Programming - Intermediate Python

Most Popular

36 Lectures 3 hours

#### Practical Machine Learning using Python

Best Seller

91 Lectures 23.5 hours

#### Practical Data Science using Python

22 Lectures 6 hours

Suppose we have a number n, indicates that there are n different courses labeled from 1 to n. We also have an array called relations where relations[i] contains a pair (prevCourse_i, nextCourse_i), representing a prerequisite relationship between the course prevCourse_i and the course nextCourse_i: so course prevCourse_i has to be taken before the course nextCourse_i. And the last parameter we have that is k. In one semester, we can take at most k number of courses as long as we have taken all the prerequisites in the previous semester for the courses we are taking. We have to find the minimum number of semesters needed to take all courses.

So, if the input is like

then the output will be 3 because in the first semester we can take course 1 and 2, now we are eligible for course 3, 4 and 5, so if we take 5 and any one of 3 or 4 for the second semester, then we can end all courses in the next semester. So we need 3 semesters in total

To solve this, we will follow these steps −

• taken := a new set

• g1 := a list with n empty lists

• g2 := a new list of size n and fill with 0

• w := a new list of size n and fill with 0

• semester := 0

• for each x in relations, do

• insert x[0]-1 at the end of g1[x[1]-1]

• insert x[1]-1 at the end of g2[x[0]-1]

• weight := a new list from the length of all items in g1

• for i in range 0 to n - 1, do

• for each x in g1[i], do

• w[x] := maximum of w[x] and weight[i]

• while size of taken < n, do

• courses := a new list

• for i in range 0 to n - 1, do

• if g1[i] is empty and i is not in taken, then

• insert (i, w[i]) at the end of courses

• if size of courses > k, then

• courses = sort courses based on the second parameter in reverse order

• courses := list of first k courses

• semester := semester + 1

• for each x in courses, do

• for each y in g2[x[0]], do

• delete x[0] from g1[y]

• g2[x[0]] := empty list

• insert x[0] into taken

• return semester

## Example

Let us see the following implementation to get better understanding

def solve(n, relations, k):
taken = set()
g1 = [[] for _ in range(n)]
g2 = [[] for _ in range(n)]
w = [0] * n
semester = 0
for x in relations:
g1[x[1]-1].append(x[0]-1)
g2[x[0]-1].append(x[1]-1)

weight = list(map(len, g1))
for i in range(n):
for x in g1[i]:
w[x] = max(w[x], weight[i])

while len(taken) < n:
courses = []
for i in range(n):
if (not g1[i]) and (i not in taken):
courses.append([i,w[i]])
if len(courses) > k:
courses = sorted(courses, key = lambda x:x[1],reverse=True)
courses = courses[:k]

semester += 1

for x in courses:
for y in g2[x[0]]:
g1[y].remove(x[0])
g2[x[0]] = []
return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

## Input

6, [(1,3),(2,5),(2,4),(5,6)], 2

## Output

3
Updated on 06-Oct-2021 08:27:17


text:
Continuous quantum error correction for non-Markovian decoherence

# Continuous quantum error correction for non-Markovian decoherence

## Abstract

We study the effect of continuous quantum error correction in the case where each qubit in a codeword is subject to a general Hamiltonian interaction with an independent bath. We first consider the scheme in the case of a trivial single-qubit code, which provides useful insights into the workings of continuous error correction and the difference between Markovian and non-Markovian decoherence. We then study the model of a bit-flip code with each qubit coupled to an independent bath qubit and subject to continuous correction, and find its solution. We show that for sufficiently large error-correction rates, the encoded state approximately follows an evolution of the type of a single decohering qubit, but with an effectively decreased coupling constant. The factor by which the coupling constant is decreased scales quadratically with the error-correction rate. This is compared to the case of Markovian noise, where the decoherence rate is effectively decreased by a factor which scales only linearly with the rate of error correction. The quadratic enhancement depends on the existence of a Zeno regime in the Hamiltonian evolution which is absent in purely Markovian dynamics. We analyze the range of validity of this result and identify two relevant time scales. Finally, we extend the result to more general codes and argue that the performance of continuous error correction will exhibit the same qualitative characteristics.

## I Introduction

Reliable information processing requires the ability to store and manipulate information with practically negligible loss. Information carriers, however, constantly interact with their surroundings, which poses the risk of information being irreversibly dissipated. This problem is of particular significance in the case of quantum information, due to the inherent fragility of quantum superpositions in the presence of external interactions. Such interactions can quickly lead to entanglement between the system of interest and its environment, effectively resulting in the loss of information. This process, known as decoherence, is a major obstacle in the construction of large-scale quantum information devices, since as quantum systems grow in size, they also become increasingly difficult to isolate from their environment.

Even though decoherence may seem to be a fundamental difficulty, the development of the theory of quantum fault tolerance Sho96 (); ABO98 (); Kit97 (); KLZ98 (); Got97 () has shown that it is possible in principle to implement reliable quantum information processing with systems of any size. As long as the error rate per information unit per time step is kept below a certain threshold, quantum information can be processed with an arbitrarily small error. This result is based on the idea of quantum error correction Shor95 (); Steane96 (); Got97 (), where the quantum state of a single information unit, say a qubit, is encoded in the state of a larger number of qubits. The encoding is such that if a single qubit in the code undergoes an error, the original state can be recovered by applying an appropriate measurement on the codeword followed by a correcting operation. The success of this scheme depends on the assumption that individual qubits undergo independent errors with small probability, and thus that errors on multiple qubits have probabilities of higher order. This technique can be extended to multi-qubit errors by constructing more complicated codes or by concatenation KL96 ().

### i.1 Continuous quantum error correction

In general, error probabilities increase with time. No matter how complicated a code or how many levels of concatenation are involved, the probability of uncorrectable errors is never truly zero, and if the system is exposed to noise for a sufficiently long time the weight of uncorrectable errors can accumulate. To combat this, error correction must be applied repeatedly and sufficiently often. If one assumes that the time for an error-correcting operation is small compared to other relevant time scales of the system, error-correcting operations can be considered instantaneous. Then the scenario of repeated error correction leads to a discrete evolution which often may be difficult to describe. To study the evolution of a system in the limit of frequently applied instantaneous error correction, Paz and Zurek proposed to describe error correction as a continuous quantum jump process PZ98 (). In this model, the infinitesimal error-correcting transformation that the density matrix of the encoded system undergoes during a time step is

 ρ→(1−κdt)ρ+κdtΦ(ρ), (1)

where is the completely positive trace-preserving (CPTP) map describing a full error-correcting operation, and is the error-correction rate. The full error-correcting operation consists of a syndrome detection, followed (if necessary) by a unitary correction operation conditioned on the syndrome.

Consider, for example, the three-qubit bit-flip code whose purpose is to protect an unknown qubit state from bit-flip (Pauli ) errors. The code space is spanned by and , and the stabilizer generators are and . Here by , , and we denote the usual Pauli operators and the identity, respectively, and a string of three operators represents the tensor product of operators on each of the three qubits. The standard error-correction procedure involves a measurement of the stabilizer generators, which projects the state onto one of the subspaces spanned by and , and , and , or and ; the outcome of these measurements is the error syndrome. Assuming that the probability for two- or three-qubit errors is negligible, then with high probability the result of this measurement is either the original state with no errors, or with a single error on the first, the second, or the third qubit. Depending on the outcome, one then applies an gate to the erroneous qubit and transforms the state back to the original one. The CPTP map for this code can be written explicitly as

 Φ(ρ)=(|000⟩⟨000|+|111⟩⟨111|)ρ(|000⟩⟨000|+|111⟩⟨111|)+(|000⟩⟨100|+|111⟩⟨011|)ρ(|100⟩⟨000|+|011⟩⟨111|)+(|000⟩⟨010|+|111⟩⟨101|)ρ(|010⟩⟨000|+|101⟩⟨111|)+(|000⟩⟨001|+|111⟩⟨110|)ρ(|001⟩⟨000|+|110⟩⟨111|) (2)

The quantum-jump process (1) can be viewed as a smoothed version of the discrete scenario of repeated error correction, in which instantaneous full error-correcting operations are applied at random times with rate . It can also be looked upon as arising from a continuous sequence of infinitesimal CPTP maps of the type (1). In practice, such a weak map is never truly infinitesimal, but rather has the form

 ρ→(1−ε)ρ+εΦ(ρ), (3)

where is a small but finite parameter, and the weak operation takes a small but nonzero time . For times much greater than (), the weak error-correcting map (3) is well approximated by the infinitesimal form (1), where the rate of error correction is

 κ=ε/τc. (4)

A weak map of the form (3) could be implemented, for example, by a weak coupling between the system and an ancilla via an appropriate Hamiltonian, followed by discarding the ancilla. A closely related scenario, where the ancilla is continuously cooled in order to reset it to its initial state, was studied in SarMil05 ().

Another way of implementing the weak map is via weak measurements followed by weak unitaries dependent on the outcome. The corresponding weak measurements, however, are not weak versions of the strong measurements for syndrome detection; they are in a different basis OBinprep (). They can be regarded as weak versions of a different set of strong measurements which, when followed by an appropriate unitary, yield the same map on average. Thus, the workings of continuous error correction, when it is driven by weak measurements, does not translate directly into the error syndrome detection and correction of the standard paradigm. In this sense, the continuous approach can be regarded as a different paradigm for error correction—one based on weak measurements and weak unitary operations. The idea of using continuous weak measurements and unitary operations for error correction has been explored in the context of different heuristic schemes ADL02 (); SarMil05g (), some of which are based on a direct “continuization” of the syndrome measurements. In this paper we consider continuous error correction of the type given by Eq. (1).

### i.2 Markovian decoherence

So far, continuous quantum error correction has been studied only for Markovian error models. The Markovian approximation describes situations where the bath-correlation times are much shorter than any characteristic time scale of the system BrePet02 (). In this limit, the dynamics can be described by a semi-group master equation in the Lindblad form Lin76 ():

 dρdt=L(ρ)≡−i[H,ρ]+12∑jλj(2LjρL†j−L†jLjρ−ρL†jLj). (5)

Here is the system Hamiltonian and the are suitably normalized Lindblad operators describing different error channels with decoherence rates . For example, the Liouvillian

 L(ρ)=∑jλj(XjρXj−ρ), (6)

where denotes a local bit-flip operator acting on the -th qubit, describes independent Markovian bit-flip errors.

For a system undergoing Markovian decoherence and error correction of the type (1), the evolution is given by the equation

 dρdt=L(ρ)+κΓ(ρ), (7)

where . In PZ98 (), Paz and Zurek showed that if the set of errors are correctable by the code, in the limit of infinite error-correction rate (strong error-correcting operations applied continuously often) the state of the system freezes and is protected from errors at all times. The effect of freezing can be understood by noticing that the transformation arising from decoherence during a short time step , is

 ρ→ρ+L(ρ)Δt+O(Δt2), (8)

i.e., the weight of correctable errors emerging during this time interval is proportional to , whereas uncorrectable errors (e.g. multi-qubit bit flips in the case of the three-qubit bit-flip code) are of order . Thus, if errors are constantly corrected, in the limit uncorrectable errors cannot accumulate, and the evolution stops.

### i.3 The Zeno effect. Error correction versus error prevention

The effect of “freezing” in continuous error correction strongly resembles the quantum Zeno effect MisSud77 (), in which frequent measurements slow down the evolution of a system, freezing the state in the limit where they are applied continuously. The Zeno effect arises when the system and its environment are initially decoupled and they undergo a Hamiltonian-driven evolution, which leads to a quadratic change with time of the state during the initial moments NNP96 () (the so called Zeno regime). Let the initial state of the system plus the bath be . For small times, the fidelity of the system’s density matrix with the initial state can be approximated as

 α(t)=1−Ct2+O(t3). (9)

In terms of the Hamiltonian acting on the entire system, the coefficient is

 C=Tr{H2SB(|0⟩⟨0|S⊗ρB(0))}−Tr{HSB(|0⟩⟨0|S⊗IB)HSB(|0⟩⟨0|S⊗ρB(0))}. (10)

According to Eq. (9), if after a short time step the system is measured in an orthogonal basis which includes the initial state , the probability to find the system in a state other than the initial state is of order . Thus if the state is continuously measured (), this prevents the system from evolving.

It has been proposed to utilize the quantum Zeno effect in schemes for error prevention Zur84 (); BBDEJM97 (); VGW96 (), in which an unknown encoded state is prevented from errors simply by frequent measurements which keep it inside the code space. The approach is similar to error correction in that the errors for which the code is designed send a codeword to a space orthogonal to the code space. The difference is that different errors need not be distinguishable, since the procedure does not involve correction of errors, but their prevention. In VGW96 () it was shown that with this approach it is possible to use codes of smaller redundancy than those needed for error correction and a four-qubit encoding of a qubit was proposed, which is capable of preventing arbitrary independent errors arising from Hamiltonian interactions. The possibility of this approach implicitly assumes the existence of a Zeno regime, and fails if we assume Markovian decoherence for all times. This is because the probability of errors emerging during a time step in a Markovian model is proportional to (rather than ), and hence errors will accumulate with time if not corrected.

From the above observations we see that error correction is capable of achieving results in noise regimes where error prevention fails. Of course, this advantage is at the expense of a more complicated procedure—in addition to the measurements used in error prevention, error correction involves unitary correction operations, and in general requires codes with higher redundancy. At the same time, we see that in the Zeno regime it is possible to reduce decoherence using weaker resources than those needed in the case of Markovian noise. This suggests that in this regime error correction may exhibit higher performance than it does for Markovian decoherence.

### i.4 Non-Markovian decoherence

Markovian decoherence is an approximation valid for times much larger than the memory of the environment. In many situations of practical significance, however, the memory of the environment cannot be neglected and the evolution is highly non-Markovian BrePet02 (); QWJ97 (); BBP04 (); KORL07 (). Furthermore, no evolution is strictly Markovian, and for a system initially decoupled from its environment a Zeno regime is always present, short though it may be NNP96 (). If the time resolution of error-correcting operations is high enough so that they “see” the Zeno regime, this could give rise to different behavior.

The existence of a Zeno regime is not the only interesting feature of non-Markovian decoherence. The mechanism by which errors accumulate in a general Hamiltonian interaction with the environment may differ significantly from the Markovian case, since the system may develop nontrivial correlations with the environment. For example, imagine that some time after the initial encoding of a system, a strong error-correcting operation is applied. This brings the state inside the code space, but the state contains a nonzero portion of errors non-distinguishable by the code. Thus the new state is mixed and is generally correlated with the environment. A subsequent error-correcting operation can only aim at correcting errors arising after this point, since the errors already present inside the code space are in principle uncorrectable. Subsequent errors on the density matrix, however, may not be completely positive due to the correlations with the environment.

Nevertheless, it follows from a result in ShaLid06 () that an error-correction procedure which is capable of correcting a certain class of completely positive (CP) maps, can also correct any linear noise map whose operator elements can be expressed as linear combinations of the operator elements in a correctable CP map. This implies, in particular, that an error-correction procedure that can correct arbitrary single-qubit CP maps can correct arbitrary single-qubit linear maps. The effects of system-environment correlations in non-Markovian error models have also been studied from the perspective of fault tolerance, and it has been shown that the threshold theorem can be extended to various types of non-Markovian noise TB05 (); AGP06 (); AKP06 ().

Another important difference from the Markovian case is that error correction and the effective noise on the reduced density matrix of the system cannot be treated as independent processes. One could derive an equation for the effective evolution of the system alone subject to interaction with the environment, like the Nakajima-Zwanzig Nak58 (); Zwa60 () or the time-convolutionless (TCL) Shibata77 (); ShiAri80 () master equations, but the generator of transformations at a given moment in general will depend (implicitly or explicitly) on the entire history up to this moment. Therefore, adding error correction can nontrivially affect the effective error model. This means that in studying the performance of continuous error correction one either has to derive an equation for the effective evolution of the encoded system, taking into account error correction from the very beginning, or one has to look at the evolution of the entire system—including the bath—where the error generator and the generator of error correction can be considered independent. In the latter case, for sufficiently small , the evolution of the entire system including the bath can be described by

 dρdt=−i[H,ρ]+κΓ(ρ), (11)

where is the density matrix of the system plus bath, is the total Hamiltonian, and the error-correction generator acts locally on the encoded system. In this paper, we take this approach for a sufficiently simple bath model which allows us to find a solution for the evolution of the entire system.

### i.5 Plan of this paper

The rest of the paper is organized as follows. To develop understanding of the workings of continuous error correction, in Sec. II we look at a simple example: an error-correction code consisting of only one qubit which aims at protecting a known state. We discuss the difference in performance for Markovian and non-Markovian decoherence, and argue the implications it has for the case of multi-qubit codes. In Sec. III, we study the three-qubit bit-flip code. We first review the performance of continuous error correction in the case of Markovian bit-flip decoherence, which was first studied in PZ98 (). We then consider a non-Markovian model, where each qubit in the code is coupled to an independent bath qubit. This model is sufficiently simple so that we can solve for its evolution analytically. In the limit of large error-correction rates, the effective evolution approaches the evolution of a single qubit without error correction, but the coupling strength is now decreased by a factor which scales quadratically with the error-correction rate. This is opposed to the case of Markovian decoherence, where the same factor scales linearly with the rate of error-correction. In Sec. IV, we show that the quadratic enhancement in the performance over the case of Markovian noise can be attributed to the presence of a Zeno regime and argue that for general stabilizer codes and independent errors, the performance of continuous error correction would exhibit the same qualitative characteristics. In Sec. V, we conclude.

## Ii The single-qubit code

Consider the problem of protecting a qubit in state from bit-flip errors. This problem can be regarded as a trivial example of a stabilizer code, where the code space is spanned by and its stabilizer is . Let us consider the Markovian bit-flip model first. The evolution of the state subject to bit-flip errors and error correction is described by Eq. (7) with

 L(ρ)=λ(XρX−ρ), (12)

and

 Γ(ρ)=|0⟩⟨0|ρ|0⟩⟨0|+|0⟩⟨1|ρ|1⟩⟨0|−ρ. (13)

If the state lies on the z-axis of the Bloch sphere, it will never leave it, since both the noise generator (12) and the error-correction generator (13) keep it on the axis. We will take the qubit to be initially in the desired state , and therefore at any later moment it will have the form , . The coefficient has the interpretation of a fidelity with the trivial code space spanned by . For an infinitesimal time step , the effect of the noise is to decrease by the amount and that of the correcting operation is to increase it by . The net evolution is then described by

 dα(t)dt=−(κ+2λ)α(t)+(κ+λ). (14)

The solution is

 α(t)=(1−αM∗)e−(κ+2λ)t+αM∗, (15)

where

 αM∗=1−12+r, (16)

and is the ratio between the rate of error correction and the rate of decoherence. We see that the fidelity decays, but it is confined above its asymptotic value , which can be made arbitrarily close to 1 for a sufficiently large .

Now let us consider a non-Markovian error model. We choose the simple scenario where the system is coupled to a single bath qubit via the Hamiltonian

 H=γX⊗X, (17)

where is the coupling strength. This can be a good approximation for situations in which the coupling to a single spin from the bath dominates over other interactions KORL07 ().

We will assume that the bath qubit is initially in the maximally mixed state, which can be thought of as an equilibrium state at high temperature. From Eq. (11) one can verify that if the system is initially in the state , the state of the system plus the bath at any moment will have the form

 ρ(t)=(α(t)|0⟩⟨0|+(1−α(t))|1⟩⟨1|)⊗I2−β(t)Y⊗X2. (18)

In the tensor product, the first operator belongs to the Hilbert space of the system and the second to the Hilbert space of the bath. We have , and . The reduced density matrix of the system has the same form as the one for the Markovian case. The traceless term proportional to can be thought of as a “hidden” part, which nevertheless plays an important role in the error-creation process, since errors can be thought of as being transferred to the “visible” part from the “hidden” part (and vice versa). This can be seen from the fact that during an infinitesimal time step , the Hamiltonian changes the parameters and as follows:

 α→α−2βγdt, β→β+(2α−1)γdt. (19)

The effect of an infinitesimal error-correcting operation is

 α→α+(1−α)κdt, β→β−βκdt. (20)

Note that the hidden part is also being acted upon. Putting it all together, we get the system of equations

 dα(t)dt=κ(1−α(t))−2γβ(t), dβ(t)dt=γ(2α−1)−κβ(t). (21)

The solution for the fidelity is

 α(t)=2γ2+κ24γ2+κ2+e−κt(κγ4γ2+κ2sin2γt+2γ24γ2+κ2cos2γt). (22)

We see that as time increases, the fidelity stabilizes at the value

 αNM∗=2+R24+R2=1−24+R2, (23)

where is the ratio between the error-correction rate and the coupling strength. In Fig. 1 we have plotted the fidelity as a function of the dimensionless parameter for three different values of . For error-correction rates comparable to the coupling strength (), the fidelity undergoes a few partial recurrences before it stabilizes close to . For larger , however, the oscillations are already heavily damped and for the fidelity seems confined above . As increases, the evolution becomes closer to a decay like the one in the Markovian case.

A remarkable difference, however, is that the asymptotic weight outside the code space () decreases with as , whereas in the Markovian case the same quantity decreases as . The asymptotic value can be obtained as an equilibrium point at which the infinitesimal weight flowing out of the code space during a time step is equal to the weight flowing into it. The latter corresponds to vanishing right-hand sides in Eqs. (14) and (21). In Sec. IV, we will show that the difference in the equilibrium code-space fidelity for the two different types of decoherence arises from the difference in the corresponding evolutions during initial times.

For multi-qubit codes, error correction cannot preserve a high fidelity with the initial codeword for all times, because there will be multi-qubit errors that can lead to errors within the code space itself. But it is natural to expect that the code-space fidelity can be kept above a certain value, since the effect of the error-correcting map (1) is to oppose its decrease. If similarly to the single-qubit code there is a quadratic difference in the code-space fidelity for the cases of Markovian and non-Markovian decoherence, this could lead to a different performance of the error-correction scheme with respect to the rate of accumulation of uncorrectable errors inside the code space. This is because multi-qubit errors that can lead to transformations entirely within the code space during a time step are of order . This means that if the state is kept constantly inside the code space (as in the limit of an infinite error-correction rate), uncorrectable errors will never develop. But if there is a finite nonzero portion of correctable errors, by the error mechanism it will give rise to errors not distinguishable or misinterpreted by the code. Therefore, the weight outside the code space can be thought of as responsible for the accumulation of uncorrectable errors, and consequently a difference in its magnitude may lead to a difference in the overall performance. In the following sections we will see that this is indeed the case.

## Iii The three-qubit bit-flip code

### iii.1 A Markovian error model

Even though the three-qubit bit-flip code can correct only bit-flip errors, it captures most of the important characteristics of nontrivial stabilizer codes. Before we look at a non-Markovian model, we will review the Markovian case which was studied in PZ98 (). Let the system decohere through identical independent bit-flip channels, i.e., is of the form (6) with . Then one can verify that the density matrix at any moment can be written as

 ρ(t)=a(t)ρ(0)+b(t)ρ1+c(t)ρ2+d(t)ρ3, (24)

where

 ρ1=13(X1ρ(0)X1+X2ρ(0)X2+X3ρ(0)X3), ρ2=13(X1X2ρ(0)X1X2+X2X3ρ(0)X2X3+X1X3ρ(0)X1X3), (25) ρ3=X1X2X3ρ(0)X1X2X3,

are equally-weighted mixtures of single-qubit, two-qubit and three-qubit errors on the original state.

The effect of decoherence for a single time step is equivalent to the following transformation of the coefficients in Eq. (24):

 a→a−3aλdt+bλdt,b→b+3aλdt−3bλdt+2cλdt,c→c+2bλdt−3cλdt+3dλdt,d→d+cλdt−3dλdt. (26)

If the system is initially inside the code space, combining Eq. (26) with the effect of the weak error-correcting map , where is given in Eq. (2), yields the following system of first-order linear differential equations for the evolution of the system subject to decoherence plus error correction:

 da(t)dt=−3λa(t)+(λ+κ)b(t),db(t)dt=3λa(t)−(3λ+κ)b(t)+2λc(t),dc(t)dt=2λb(t)−(3λ+κ)c(t)+3λd(t),dd(t)dt=(λ+κ)c(t)−3λd(t). (27)

The exact solution has been found in PZ98 (). Here we just note that for the initial conditions , the exact solution for the weight outside the code space is

 b(t)+c(t)=34+r(1−e−(4+r)λt), (28)

where . We see that similarly to what we obtained for the trivial code in the previous section, the weight outside the code space quickly decays to its asymptotic value which scales as . But note that here the asymptotic value is roughly three times greater than that for the single-qubit model. This corresponds to the fact that there are three single-qubit channels. More precisely, it can be verified that if for a given the uncorrected weight by the single-qubit scheme is small, then the uncorrected weight by a multi-qubit code using the same and the same kind of decoherence for each qubit scales approximately linearly with the number of qubits OBinprep (). Similarly, the ratio required to preserve a given overlap with the code space scales linearly with the number of qubits in the code.

The most important difference from the single-qubit model is that in this model there are uncorrectable errors that cause a decay of the state’s fidelity inside the code space. Due to the finiteness of the resources employed by our scheme, there always remains a nonzero portion of the state outside the code space, which gives rise to uncorrectable three-qubit errors. To understand how the state decays inside the code space, we ignore the terms of the order of the weight outside the code space in the exact solution. We obtain:

 a(t)≈1+e−6r2λt2≈1−d(t), (29)
 b(t)≈c(t)≈0. (30)

Comparing this solution to the expression for the fidelity of a single decaying qubit without error correction—which can be seen from Eq. (15) for —we see that the encoded qubit decays roughly as if subject to bit-flip decoherence with rate . Therefore, for large this error-correction scheme can reduce the rate of decoherence approximately times. In the limit , it leads to perfect protection of the state for all times.

### iii.2 A non-Markovian error model

We consider a model where each qubit independently undergoes the same kind of non-Markovian decoherence as the one we studied for the single-qubit code. Here the system we look at consists of six qubits - three for the codeword and three for the environment. We assume that all system qubits are coupled to their corresponding environment qubits with the same coupling strength, i.e., the Hamiltonian is

 H=γ3∑i=1XSi⊗XBi, (31)

where the operators act on the system qubits and act on the corresponding bath qubits. The subscripts label the particular qubit on which they act. Obviously, the types of effective single-qubit errors on the density matrix of the system that can result from this Hamiltonian at any time, whether they are CP or not, will have operator elements which are linear combinations of and , i.e., they are correctable by the procedure according to ShaLid06 (). Considering the forms of the Hamiltonian (31) and the error-correcting map (2), one can see that the density matrix of the entire system at any moment is a linear combination of terms of the following type:

 ϱlmn,pqr≡Xl1Xm2Xn3ρ(0)Xp1Xq2Xr3⊗Xl+p12⊗Xm+q22⊗Xn+r32. (32)

Here the first term in the tensor product refers to the Hilbert space of the system, and the following three refer to the Hilbert spaces of the bath qubits that couple to the first, second and third qubits from the code, respectively. The powers take values and in all possible combinations, and , . Note that should not be mistaken for the components of the density matrix in the computational basis. Collecting these together, we can write the density matrix in the form

 ρ(t) = ∑l,m,n,p,q,r(−i)l+m+n(i)p+q+rClmn,pqr(t)×ϱlmn,pqr, (33)

where the coefficients are real. The coefficient is less than or equal to the codeword fidelity (with equality when or ). Since the scheme is intended to protect an unknown codeword, we are interested in its worst-case performance; we will therefore use as a lower bound on the codeword fidelity.

Using the symmetry with respect to permutations of the different system-bath pairs of qubits and the Hermiticity of the density matrix, we can reduce the description of the evolution to a system of equations for only of the coefficients. (In fact, coefficients are sufficient if we invoke the normalization condition , but we have found it more convenient to work with .) The equations are linear, and we write them as a single 13-dimensional vector equation:

 ddt⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣C000,000C100,000C110,000C100,010C100,100C110,001C111,000C110,100C110,110C110,011C111,100C111,110C111,111⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦=γ⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣0−6003R000000001−R−2−2−10000000002−R00−1−1−200000020−R0−20−2000000200−R00−40000000120−R000−2−10000300−3R0000−3000011100−R−1−1−10000000004−R00−20000002020−R0−200000011200−R−2000000000122−R−1000000003R0060⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦⋅⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣C000,000C100,000C110,000C100,010C100,100C110,001C111,000C110,100C110,110C110,011C111,100C111,110C111,111⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦ (34)

where . Each nonzero component in this matrix represents an allowed transition process for the quantum states; these transitions can be driven either by the decoherence process or the continuous error-correction process. We plot these allowed transitions in Fig. 2.

We can use the symmetries of the process to recover the 64 coefficients of the full state. Each of the 13 coefficients represents a set of coefficients having the same number of s on the left and the same number of s on the right, as well as the same number of places which have on both sides. All such coefficients are equal at all times. For example, the coefficient is equal to all coefficients with two s on the left, two s on the right and exactly one place with on both sides; there are exactly six such coefficients:

 C110,011=C110,101=C101,011=C101,110=C011,110=C011,101.

In determining the transfer rate from one coefficient to another in Fig. 2, one has to take into account the number of different coefficients of the first type which can make a transition to a coefficient of the second type of order according to Eq. (11). The sign of the flow is determined from the phases in front of the coefficients in Eq. (33).

The eigenvalues of the matrix in Eq. (34) up to the first two lowest orders in are presented in Table I.

Obviously all eigenvalues except the first one and the last two describe fast decays with rates . They correspond to terms in the solution which will vanish quickly after the beginning of the evolution. The eigenvalue corresponds to the asymptotic () solution, since all other terms will eventually decay. The last two eigenvalues are those that play the main role in the evolution on a time scale . We see that on such a time scale, the solution will contain an oscillation with an angular frequency approximately equal to which is damped by a decay factor with a rate of approximately . In Fig. 3 we have plotted the codeword fidelity as a function of the dimensionless parameter for . The graph indeed represents this type of behavior, except for very short times after the beginning (), where one can see a fast but small in magnitude decay (Fig. 4). The maximum magnitude of this quickly decaying term obviously decreases with , since in the limit of the fidelity should remain constantly equal to .

From the form of the eigenvalues one can see that as increases, the frequency of the main oscillation decreases as while the rate of decay decreases faster, as . Thus in the limit , the evolution approaches an oscillation with an angular frequency . (We formulate this statement more rigorously below.) This is the same type of evolution as that of a single qubit interacting with its environment, but the coupling constant is effectively reduced by a factor of .

While the coupling constant serves to characterize the decoherence process in this particular case, this is not valid in general. To handle the more general situation, we propose to use the instantaneous rate of decrease of the codeword fidelity as a measure of the effect of decoherence:

 Λ(Fcw(t))=−dFcw(t)dt. (35)

(In the present case, .) This quantity does not coincide with the decoherence rate in the Markovian case (which can be defined naturally from the Lindblad equation), but it is a good estimate of the rate of loss of fidelity and can be used for any decoherence model. From now on we will refer to it simply as an error rate, but we note that there are other possible definitions of instantaneous error rate suitable for non-Markovian decoherence, which in general may depend on the kind of errors they describe. Since the goal of error correction is to preserve the codeword fidelity, the quantity (35) is a useful indicator for the performance of a given scheme. Note that is a function of the codeword fidelity and therefore it makes sense to use it for a comparison between different cases only for identical values of . For our example, the fact that the coupling constant is effectively reduced approximately times implies that the error rate for a given value of is also reduced times. Similarly, the reduction of by the factor in the Markovian case implies a reduction of by the same factor. We see that the effective reduction of the error rate increases quadratically with in the non-Markovian case, whereas it increases only linearly with in the Markovian case.

Now let us rigorously derive the approximate solution to this model of non-Markovian decoherence with continuous error correction. Assuming that (or equivalently, ), the superoperator driving the evolution of the system during a time step can be written as

 eLδt = eLκδt+δt0∫dt′eLκ(δt−t′)LγeLκt′+δt∫0dt′δt∫t′dt′′eLκ(δt−t′′)LγeLκ(t′′−t′)LγeLκt′+ (36) + δt∫0dt′δt∫t′dt′′δt∫t′′dt′′′eLκ(δt−t′′′)LγeLκ(t′′′−t′′)LγeLκ(t′′−t′)LγeLκt′+...

We have denoted the Liouvillian by , where , and .

Let . We will derive an approximate differential equation for the evolution of by looking at the terms of order in the change of according to Eq. (36). When , we have , so the effect of on the state of the system can be seen from Eq. (34) with taken equal to . By the action of , the different terms of the density matrix transform as follows: remain unchanged, , , , and all other terms are changed as . Since , we will ignore terms of order . But from Eq. (36) it can be seen that all terms except will get multiplied by the factor by the action of in Eq. (36). The integrals in Eq. (36) also yield negligible factors, since every integral either gives rise to a factor of order when the integration variable is trivially integrated, or a factor of when the variable participates nontrivially in the exponent. Therefore, in the above approximation these terms of the density matrix can be neglected, which amounts to an effective evolution entirely within the code space. According to Eq. (34), the terms can couple to each other only by a triple or higher application of . This means that if we consider the expansion up to the lowest nontrivial order in , we only need to look at the triple integral in Eq. (36).

Let us consider the effect of on . Any change can come directly only from and . The first exponent acts on these terms as the identity. Under the action of the first operator each of these two terms can transform to six terms that can eventually be transformed to . They are , , , , , , and , , , , , , with appropriate factors. The action of the second exponent is to multiply each of these new terms by . After the action of the second , the action of the third exponent on the relevant resultant terms will be again to multiply them by a factor . Thus the second and the third exponents yield a net factor of . After the second and the third , the relevant terms that we get are and , , , each with a corresponding factor. Finally, the last exponent acts as the identity on and transforms each of the terms , , into . Counting the number of different terms that arise at each step, and taking into account the factors that accompany them, we obtain:

 C000,000 → C000,000+δt∫0dt′δt∫t′dt′′δt∫t′′dt′′′(24e−κ(t′′′−t′)−36e−κ(δt−t′))C111,000+⋯ (37) ≈ C000,000+C111,00024R2γδt+O(δt2).

Using that , in a similar way one obtains

 C111,000→C111,000−(2C000,000−1)12R2γδt+O(δt2). (38)

For times much larger than , we can write the approximate differential equations

 dC000,000dt=24R2γC111,000, dC111,000dt=−12R2γ(2C000,000−1). (39)

Comparing with Eq. (19), we see that the encoded qubit undergoes approximately the same type of evolution as that of a single qubit without error correction, but the coupling constant is effectively decreased times. The solution of Eq. (39) yields for the codeword fidelity

 C000,000(t)=1+cos(24R2γt)2. (40)

This solution is valid only with precision for times . This is because we ignored terms whose magnitudes are always of order and ignored changes of order per time step in the other terms. The latter changes could accumulate with time and become of the order of unity for times , which is why the approximate solution is invalid for such times. In fact, if one carries out the expansion (36) to fourth order in , one obtains the approximate equations

 dC000,000dt=24R2γC111,000−72R3γ(2C000,000−1), dC111,000dt=−12R2γ(2C000,000−1)−144R3γC111,000, (41)

which yield for the fidelity

 C000,000(t)=1+e−144γt/R3cos(24γt/R2)2. (42)

We see that in addition to the effective error process which is of the same type as that of a single qubit, there is an extra Markovian bit-flip process with rate . This Markovian behavior is due to the Markovian character of our error-correcting procedure which, at this level of approximation, is responsible for the direct transfer of weight between and , and between and . The exponential factor explicitly reveals the range of applicability of solution (40): with precision , it is valid only for times of up to order . For times of the order of , the decay becomes significant and cannot be neglected. The exponential factor may also play an important role for short times of up to order , where its contribution is bigger than that of the cosine. But in the latter regime the difference between the cosine and the exponent is of order , which is negligible for the precision that we consider.

In general, the effective evolution that one obtains in the limit of high error-correction rate does not have to approach a form identical to that of a single decohering qubit. The reason we obtain such behavior here is that for this particular model the lowest order of uncorrectable errors that transform the state within the code space is 3, and three-qubit errors have the form of an encoded operation. Furthermore, the symmetry of the problem ensured an identical evolution of the three qubits in the code. For general stabilizer codes, the errors that a single qubit can undergo are not limited to bit flips only. Therefore, different combinations of single-qubit errors may lead to different types of lowest-order uncorrectable errors inside the code space, none of which in principle has to represent an encoded version of the single-qubit operations that compose it. In addition, if the noise is different for the different qubits, there is no unique single-qubit error model to compare to. Nevertheless, we will show that with regard to the effective decrease in the error-correction rate, general stabilizer codes will exhibit the same qualitative performance.

## Iv Relation to the Zeno regime

The effective continuous evolution (39) was derived under the assumption that . The first inequality implies that can be considered within the Zeno time scale of the system’s evolution without error correction. On the other hand, from the relation between and in (4) we see that . Therefore, the time for implementing a weak error-correcting operation has to be sufficiently small so that on the Zeno time scale the error-correction procedure can be described approximately as a continuous Markovian process. This suggests a way of understanding the quadratic enhancement in the non-Markovian case based on the properties of the Zeno regime.

Let us consider again the single-qubit code from Sec. II, but this time let the error model be any Hamiltonian-driven process. We assume that the qubit is initially in the state , i.e., the state of the system including the bath has the form . For times smaller than the Zeno time , the evolution of the fidelity without error correction can be described by Eq. (9). Equation (9) naturally defines the Zeno regime in terms of itself:

 α≥αZ≡1−Cδt2Z. (43)

For a single time step , the change in the fidelity is

 α→α−2√C√1−αΔt+O(Δt2). (44)

On the other hand, the effect of error correction during a time step is

 α→α+κ(1−α)Δt+O(Δt2), (45)

i.e., it tends to oppose the effect of decoherence. If both processes happen simultaneously, the effect of decoherence will still be of the form (44), but the coefficient may vary with time. This is because the presence of error-correction opposes the decrease of the fidelity and consequently can lead to an increase in the time for which the fidelity remains within the Zeno range. If this time is sufficiently long, the state of the environment could change significantly under the action of the Hamiltonian, thus giving rise to a different value for in Eq. (44) according to Eq. (10).

Note that the strength of the Hamiltonian puts a limit on , and therefore this constant can vary only within a certain range. The equilibrium fidelity that we obtained for the error model in Sec. II, can be thought of as the point at which the effects of error and error correction cancel out. For a general model, where the coefficient may vary with time, this leads to a quasi-stationary equilibrium. From Eqs. (44) and (45), one obtains the equilibrium fidelity

 αNM∗≈1−4Cκ2. (46)

In agreement with what we obtained in Sec. II, the equilibrium fidelity differs from by a quantity proportional to . This quantity is generally quasi-stationary and can vary within a limited range. If one assumes a Markovian error model, for short times the fidelity changes linearly with time which leads to . Thus the difference can be attributed to the existence of a Zeno regime in the non-Markovian case.

But what happens in the case of non-trivial codes? As we saw, there the state decays inside the code space and therefore can be highly correlated with the environment. Can we talk about a Zeno regime then? It turns out that the answer is positive. Assuming that each qubit undergoes an independent error process, then up to first order in the Hamiltonian cannot map terms in the code space to other terms without detectable errors. (This includes both terms in the code space and terms from the hidden part, like in the example of the bit-flip code.) It can only transform terms from the code space into traceless terms from the hidden part which correspond to single-qubit errors (like in the same example). Let , be the two logical codewords and be an orthonormal basis that spans the space of all single-qubit errors. Then in the basis , , , all the terms that can be coupled directly to terms inside the code space are , , , . From the condition of positivity of the density matrix, one can show that the coefficients in front of these terms are at most in magnitude, where is the code-space fidelity. This implies that for small enough , the change in the code-space fidelity is of the type (44), which is Zeno-like behavior. Then using only the properties of the Zeno behavior as we did above, we can conclude that the weight outside the code space will be kept at a quasi-stationary value of order . Since uncorrectable errors enter the code space through the action of the error-correction procedure, which misinterprets some multi-qubit errors in the error space, the effective error rate will be limited by a factor proportional to the weight in the error space. That is, this will lead to an effective decrease of the error rate at least by a factor proportional to .

The accumulation of uncorrectable errors in the Markovian case is similar, except that in this case there is a direct transfer of errors between the code space and the visible part of the error space. In both cases, the error rate is effectively reduced by a factor which is roughly proportional to the inverse of the weight in the error space, and therefore the difference in the performance comes from the difference in this weight. The quasi-stationary equilibrium value of the code-space fidelity establishes a quasi-stationary flow between the code space and the error space. One can think that this flow effectively takes non-erroneous weight from the code space, transports it through the error space where it accumulates uncorrectable errors, and brings it back into the code space. Thus by minimizing the weight outside the code space, error correction creates a “bottleneck” which reduces the rate at which uncorrectable errors accumulate.

Finally, a brief remark about the resources needed for quadratic reduction of the error rate. As pointed out above, two conditions are involved: one concerns the rate of error correction; the other concerns the time resolution of the weak error-correcting operations. Both of these quantities must be sufficiently large. There is, however, an interplay between the two, which involves the strength of the interaction required to implement the weak error-correcting map (3). Let us imagine that the weak map is implemented by making the system interact weakly with an ancilla in a given state, after which the ancilla is discarded. The error-correction procedure consists of a sequence of such interactions, and can be thought of as a cooling process which takes away the entropy accumulated in the system as a result of correctable errors. If the time for which a single ancilla interacts with the system is , one can verify that the parameter in Eq. (3) would be proportional to , where is the coupling strength between the system and the ancilla. From Eq. (4) we then obtain that

 κ∝g2τc. (47)

The two parameters that can be controlled are the interaction time and the interaction strength, and they determine the error-correction rate. Thus if is kept constant, a decrease in the interaction time leads to a proportional decrease in , which may be undesirable. In order to achieve a good working regime, one may need to adjust both and . But it has to be pointed out that in some situations decreasing alone can prove advantageous, if it leads to a time resolution revealing the non-Markovian character of an error model which was previously described as Markovian. The quadratic enhancement of the performance as a function of may compensate the decrease in , thus leading to a seemingly paradoxical result: better performance with a lower error-correction rate.

## V Conclusion

In this paper we studied the performance of a particular continuous quantum error-correction scheme for non-Markovian errors. We analyzed the evolution of the single-qubit code and the three-qubit bit-flip code in the presence of continuous error correction for a simple non-Markovian bit-flip error model. This enabled us to understand the workings of the error-correction scheme, and the mechanism whereby uncorrectable errors accumulate. The fidelity of the state with the code space in both examples quickly reaches an equilibrium value, which can be made arbitrarily close to by a sufficiently high rate of error correction. The weight of the density matrix outside the code space scales as in the Markovian case, while it scales as in the non-Markovian case. Correspondingly, the rate at which uncorrectable errors accumulate in the three-qubit code is proportional to in the Markovian case, and to in the non-Markovian case. These differences have the same cause, since the equilibrium weight in the error space is closely related to the rate of uncorrectable error accumulation.

The quadratic difference in the error weight between the Markovian and non-Markovian cases can be attributed to the existence of a Zeno regime in the non-Markovian case. Regardless of the correlations between the density matrix inside the code space and the environment, if the lowest-order errors are correctable by the code, there exists a Zeno regime in the evolution of the code-space fidelity. The effective reduction of the error rate with the rate of error correction for non-Markovian error models depends crucially on the assumption that the time resolution of the continuous error correction is much shorter than the Zeno time scale of the evolution without error correction. This suggests that decreasing the time for a single (infinitesimal) error-correcting operation can lead to an increase in the performance of the scheme, even if the average error-correction rate goes down.

While in this paper we have only considered codes for the correction of single-qubit errors, our results can be extended to other types of codes and errors as well. As long as the error process only produces errors correctable by the code to lowest order, an argument analogous to the one given here shows that a Zeno regime will exist, which leads to an enhancement in the error-correction performance. Unfortunately, it is very difficult to describe the evolution of a system with a continuous correction protocol, based on a general error-correction code and subject to general non-Markovian interactions with the environment. This is especially true if one must include the evolution of a complicated environment in the description, as would be necessary in general. A more practical step in this direction might be to find an effective description for the evolution of the reduced density matrix of the system subject to decoherence plus error correction, using projection techniques like the Nakajima-Zwanzig or the TCL master equations. Since one is usually interested in the evolution during initial times before the codeword fidelity decreases significantly, a perturbation approach could be useful. This is a subject for further research.

## Acknowledgements

The authors would like to thank Kurt Jacobs for useful information, Daniel Lidar for inspiring conversations, and Shesha Raghunathan for his careful reading of the manuscript. This research was supported in part by NSF Grant No. EMT-0524822.

### References

1. P. Shor, in Proceedings of the Annual Symposium on Fundamentals of Computer Science, 56-65, IEEE Press, Los Alamitos, CA (1996).
2. D. Aharonov and M. Ben-Or, in Proceedings of the Annual ACM Symposium on Theory of Computing, 176, ACM, New York (1998).
3. A. Kitaev, Russian Math. Surveys 52, 1191 (1997).
4. E. Knill, R. Laflamme, and W. H. Zurek, Proc. R. Soc. London, Ser. A 454, 365 (1998).
5. D. Gottesman, Stabilizer codes and quantum error orrection, Ph.D. thesis, Caltech, 1997, quant-ph/9705052.
6. P. Shor, Phys. Rev. A 52, 2493 (1995).
7. A. M. Steane, Phys. Rev. Lett. 77, 793 (1996).
8. E. Knill, R. Laflamme, quant-ph/9608012.
9. J. P. Paz and W. H. Zurek, Proc. R. Soc. London, Ser. A 454, 355 (1998).
10. M. Sarovar and G. J. Milburn, Phys. Rev. A. 72 012306 (2005).
11. O. Oreshkov and T. A. Brun, in preparation.
12. C. Ahn, A. C. Doherty, and A. J. Landahl, Phys. Rev. A 65, 042301 (2002).
13. M. Sarovar and G. J. Milburn, Quantum Communication, Measurement Computing, (AIP Conference Proceeedings), p.121 (2004).
14. H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Oxford University Press, Oxford, 2002).
15. G. Lindblad, Commun. Math. Phys. 48, 119 (1976).
16. B. Misra and E.C.G Sudarshan, J. Math. Phys. 18, 756 (1977).
17. H. Nakazato, M. Namiki, and S. Pascazio, Int. J. Mod. Phys. B 10, 247 (1996).
18. W. H. Zurek, Phys. Rev. Lett. 53, 391 (1984).
19. A. Barenco, A. Berthiaume, D. Deutsch, A. Eckert, R. Jozsa, and C. Macchiavello, SIAM Journal on Computing 26, 1541 (1997).
20. L. Vaidman, L. Goldenberg, and S. Wiesner, Phys. Rev. A, 54, 1745 (1996).
21. T. Quang, M. Woldeyohannes, S. John, and G. S. Agraval, Phys. Rev. Lett. 79, 5238 (1997).
22. H.-P. Breuer, D. Burgarth, and F. Petruccione, Phys. Rev. B 70, 045323 (2004).
23. H. Krovi, O. Oreshkov, M Ryazonov, and D. Lidar, arXiv:0707.2096.
24. A. Shabani and D. Lidar, quant-ph/0610028.
25. B. M. Terhal and G. Burkard, Phys. Rev. A 71, 012336 (2005).
26. P. Aliferis, D. Gottesman, and J. Preskill, Quantum Inf. Comput. 6, 97 (2006).
27. D. Aharonov, A. Kitaev, and J. Preskill, Phys. Rev. Lett. 96, 050504 (2006).
28. S. Nakajima, Prog. Theor. Phys. 20, 948 (1958).
29. R. Zwanzig, J. Chem. Phys. 33, 1338 (1960).
30. F. Shibata, Y. Takahashi, and N. Hashitsume, J. Stat. Phys. 17, 171 (1977).
31. F. Shibata and T. Arimitsu, J. Phys. Soc. Jpn. 49, 891 (1980).
You are adding the first comment!
How to quickly get a good reply:
• Give credit where it’s due by listing out the positive aspects of a paper before getting into which changes should be made.
• Be specific in your critique, and provide supporting evidence with appropriate references to substantiate general statements.
• Your comment should inspire ideas to flow and help the author improves the paper.

The better we are at sharing our knowledge with each other, the faster we move forward.
The feedback must be of minimum 40 characters and the title a minimum of 5 characters


text:
# Optimizing what can be seen by a creature

This topic is 4826 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a program I'm optimizing. I have a bunch of spheres that are little creatures. Each creature has a 90 degree vision range. If there's another creature in its viewing range, and it hasn't seen a nearer creature already that cycle, it writes a number to a memory location the creature can access. Like this (but simplified, in reality the bot has 9 memory locations instead of 3). The creature is looking towards the blue arrow. Creature 1 will write numbers to eye cells 1 and 2, but not 3. The spheres are not necessarily uniform in size, but most are. Currently the program does these steps: 1. Caclulate distance between two spheres using their centers. 2. Calculate angle between two spheres. (uses atn((1.y - 2.y)/(1.x-2.x))) 3. If angle between spheres is within 45 degrees of creature 1's blue arrow then: 5. Find all eye cells that the creature in the distance is visible from. 6. If distance between the spheres is less than what is currently written to an eye cell, overwrite that eye cell. I've already optimized finding the distance between two cells. The only optimization left is to just use the square instead of the square root of the distance (which might not be a bad idea, I'm still evaluating). The problem is it's executed every cycle, becoming increasingly expensive as the number of creatures increases. At around 1000 creatures it hits a stand still. (like 2 cycles a second). I'd really like to double or even triple this, or even more! If you need to see the source code, I can post it. It's visual basic, so it shouldn't be too hard to understand (stop scoffing, it wasn't my idea!). Any ideas on how to combine steps or make steps faster would be awesome.

##### Share on other sites
The first obvious problem is the atan (dy/dx) as this involves division, which is slow, and a transendental function - which make division look speedy by comparison.

There's two ways to determine if one object is within the view angle of a second object that don't require angles. The first is:
let ab = vector from viewer to viewedlet f = viewer's look at direction, normalisednormalise abif ab dot f < cos 45O then object in view angle

which is OK apart from the normalisation of vector ab. Or there's the following:
rpn = normal to plane forming right hand edge of view frustrumlpn = normal to plane forming left hand edge of view frustrumab = vector from viewer to viewedif ab dot rpn >= 0 && ab dot lpn >= 0 then object in view angle

which is much better performance wise - the only operations are addition and multiplication.

The next problem is handling lots of objects. You need to look into some form of space division. The simplest would be a 2d array of lists of objects, each element of the array contains a list of objects in the same area such that:
array_index = ((object_x - origin_x) / cell_size) + ((object_y - origin_y) / cell_size) * array_width

Then, when an object moves, first remove it from the array cell it's currently in, move the object and add it to list for its new location. To search, start with the cell the object is in and the eight adjacent cells. If no object found then extend the search by one square and repeat.

Skizz

##### Share on other sites
Thanks, I'll give the second technique you showed a try, looks like it'll definately help. It actually looks simpler than what's going on right now.

Another programmer is working on adding a grid of squares roughly the size of the creatures to hold things like food sources etc. in the environment. I can adapt these to each hold a list of creatures that occupy the cell fairly easily.

If I were to use this system, how would you recommend using it to speed up the program? Other than what you've listed above of course (actually, could you explain that in a paragraph too?). Are there any other ways?

I have a few ideas, but I tend to reinvent alot of wheels. Duplication of effort is not my idea of a fun time.

##### Share on other sites
Well, what you're probably doing right now is something along the lines of:
for each object1 in world    for each object2 in world        if object1 can see object2 and object2 is the closest            do something with object2         endif    nextnext

Using a 2D array, assume the world is bounded thus:

(0,0) <= object pos < (max_x, max_y);

and that the 2D array is defined as:

map [map_size_x][map_size_y];

then, each element of the array is (max_x / map_size_x, max_y / map_size_y) in size.

Given a position P, the index into the map is:

map [Px * map_size_x / max_x][Py * map_size_y / max_y]

So, to search the map do the following:
org_x = Px * map_size_x / max_x;org_y = Py * map_size_y / max_y;size = 1for y = org_y - size to org_y + size    for x = org_x - size to org_x + size        for each object in map [x][y]            do object test        next    nextnextwhile no object found    size = size + 1    for y = org_y - size to org_y + size        for each object in map [org_x - size][y]            do object test        next        for each object in map [org_x + size][y]            do object test        next    next    for x = org_x - size  +1 to org_x + size - 1        for each object in map [x][org_y - size]            do object test        next        for each object in map [x][org_y + size]            do object test        next    nextwend

The food thing can also be added to the map array as a separate list - it will take up less memory than what you've suggested. You'd want the cell size to be about 4 times the size of a creature.

The downside to this algorithm is that the cells are fixed size. If you get a lot of creatures grouped together, the search time will increase. To get around this, you can look into things like quad trees which can dynamincally change the size of the cells.

Hope that helps.

Skizz

##### Share on other sites
Thanks, I'll give it a try.

##### Share on other sites
Is there a way to get to the angle of a vector defined in <x,y> form without using acos, asin, or atan?

##### Share on other sites
there is always a lookup table with interpolation. alternatively, if you are just partitioning something (i.e. -90 to -45, -45 to 0, 0 to 45, 45 to 90) you do not need an actual angle, as you could just leave the value as a cosine or sine or whatever.

if it is for small angles you can just a simple polynomial (taylor series expansion around your midpoint)

##### Share on other sites
Quote:
 Original post by NumsgilIs there a way to get to the angle of a vector defined in form without using acos, asin, or atan?

Perhaps you should ask yourself "Do I need to know the value of the angle?"
If it's for working out which sector the object is in (the 'Eyecell' in your diagram) then this can be worked out without knowing the angle:
let at = normalised forward vectorlet right = normalised right vector (perpendicular to at)let P = vector from observer to observed; project P into observer spaceP'x = P dot rightP'y = P dot at; you now have this:; y|   P';  |  /;  | /;  |/____ x; now determine point on y=1 where OP intersects:let n = P'x / P'y; now compare n against values for tan theta where theta is the angle defining the eyecell.; these values are constant so they can be precomputed and stored in an array

Skizz

##### Share on other sites
Hm.

I'd say as your number of creatures increase, the number of "empty" eyecells goes down to zero.
If this happens it would make sense to save the maximal distance of all creatures in all eyecells.

so if you have 3 eyecells at all (like in your example) with detected creatures at 100, 30 and 50; the maximum distance of a creature in your eyecells would be 100. now it wouldn't make sense to do any further calculation if you find out in your step 1 the distance of a creature is 101, as it never will be closer than any creature in your eyecell.

(you would still have to do all the work if you haven't found any creature in at least one eyecell)

sure this works only in an average case, if all creatures you have to view are in the same direction you will not benefit at all, but with MANY creatures you should get at least some speed boost.

##### Share on other sites
Small problem:

The P vector you gave is from the center of creature 1 to the center of creature two.

I'd like to have two vectors to get your system to work. P1 would be the vector to the right most visible edge of creature 2.

P2 would be the same but left most visible edge.

I've gotten this far:

where RadiusRightAngle is a vector of <x,y> and has these properties:

x/y = -P1y / P1x * y
x^2 + y^2 = creature's radius ^ 2

Then you have x = -P1y/P1x
creature's radius ^ 2 / (P1y^2/P1x^2 + 1) = y^2

y^2 can be calculated, then you get:

radius ^ 2 - y ^ 2 = x ^ 2

And then I'm stuck. I don't want to take the square root of any numbers.

Is there a better way?

• 10
• 19
• 14
• 19
• 15