text:
# Solving Equations with Grover's Algorithm¶

This experiments is inspired by QISKITs introduction of the Grover algorithm, which can be found at https://qiskit.org/textbook/ch-algorithms/grover.html.

Grover algrithm is one of the most famous algorithms for Quantum Computers. It is often discussed as a kind of database search agorithm but this is, quite possibly a pretty bad misnomer. I do like to think of it as a solver for otherwise completely unstructured problems, i.e. problem where you have to brute force search the an entire solutions space of size $N$ for the best possible solution. Grover gives you a solution in $\sqrt{N}$ steps. For completeness sake: it does NOT speed up solutions exponentially (retaining polynomial speedup) and does thus not give an answer to the infamous $\mathbf{P=NP}$ conjecture.

We shall use it today to solve a simple mathematical problem, namely to find a solution to the problem $a+b=17$. This is, of course, NOT a completely unstructured problem and there are certainly MUCH quicker ways to solve the issue.

In [1]:
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, Aer, transpile
from qiskit.visualization import plot_bloch_multivector, plot_histogram
from numpy import pi
import numpy as np
import matplotlib.pylab as plt
sim = Aer.get_backend('aer_simulator')

<frozen importlib._bootstrap>:219: RuntimeWarning: scipy._lib.messagestream.MessageStream size changed, may indicate binary incompatibility. Expected 56 from C header, got 64 from PyObject

## Classical Problems on a Quantum Computer¶

Since classical Physics is a subclass of Quantum Phyics it probably comes as no big surprise for you to finde, that any classical computation can be carried out on a Quantum Computer (and then some). If you want to port a classical computer programm into a Quantum circuit you could simply break down the classical software into its computational gates and you would find that there only NAND-gates on a classical computer.

All other gates and hence all possible claculation a classical computer can implement can be composed of series of NAND-gates. See https://de.wikipedia.org/wiki/NAND-Gatter for a list, if you are interested. The Quantum Equivalent of the NAND gates can be implemented with the so-called Toffoli-Gate. The action of the gate is defined as $\hat{TF}(|c_0\rangle{}|c_1\rangle{}|t\rangle{})= |c_0\rangle{}|c_1\rangle{}|t\oplus(c_0\cdot{}_1)\rangle{}$, hence it is the equivalent of the AND gate. It is defined is QISKIT:

In [2]:
qc = QuantumCircuit(3)
qc.toffoli(0,1,2)
qc.draw()

Out[2]:

The NAND gate can be implemented quite easily by simply negating the result

In [3]:
def NAND_gate(as_gate=True):
qc = QuantumCircuit(3)
qc.toffoli(0,1,2)
qc.x(2)
if (as_gate):
U_s = qc.to_gate()
U_s.name = "NAND"
return U_s
else:
return qc

qc = NAND_gate(as_gate=False)
qc.draw()

Out[3]:

We can use this function to create a truth-table and see that this is indeed equivalent to the gate:

In [4]:
def gate_test_onevalue(inp1, inp2, gate):
qc = QuantumCircuit(3)
if (inp1):
qc.x(0)
if (inp2):
qc.x(1)
qc.append(gate,[0,1,2])

qc.measure_all()
qc_t = transpile(qc, sim)
results = sim.run(qc_t, shots=1).result().get_counts()
for key, value in results.items():
truth = int(key[0])
break
return truth

def gate_test(gate):
r = [[0,0],[0,0]]
for idx1, inp1 in enumerate([False, True]):
for idx2, inp2 in enumerate([False, True]):
r[idx1][idx2] = gate_test_onevalue(inp1, inp2, gate)
return r

import pandas
def print_truth_table(gate):
t = gate_test(gate)
print(pandas.DataFrame(t, [0, 1], [0, 1]))

Which we apply into the NAND-gate:

In [5]:
print('NAND-gate')
print_truth_table(NAND_gate(False))

NAND-gate
0  1
0  1  1
1  1  0

We can equivalently define and Test shortcuts for ANDs and ORs, which will come in handy, later on. To create the OR and we use the fact that $A\ \mathrm{or}\ B = \mathrm{not}(\mathrm{not}(A\ \mathrm{or}\ B)) = \mathrm{not}(\mathrm{not}(A)\ \mathrm{and}\ \mathrm{not}(B))$. The XOR-gate is constructed from two CNOTs.

In [6]:
def OR_gate(as_gate=True):
qc = QuantumCircuit(3)
qc.x(0)
qc.x(1)
qc.toffoli(0,1,2)
qc.x(2)
qc.x(0)
qc.x(1)
if (as_gate):
U_s = qc.to_gate()
U_s.name = "OR"
return U_s
else:
return qc

def AND_gate(as_gate=True):
qc = QuantumCircuit(3)
qc.toffoli(0,1,2)
if (as_gate):
U_s = qc.to_gate()
U_s.name = "AND"
return U_s
else:
return qc

def XOR_gate(as_gate=True):
qc = QuantumCircuit(3)
qc.cx(0,2)
qc.cx(1,2)
if (as_gate):
U_s = qc.to_gate()
U_s.name = "XOR"
return U_s
else:
return qc

print('OR Gate')
print_truth_table(OR_gate())
print('')
print('AND Gate')
print_truth_table(AND_gate())
print('')
print('XOR Gate')
print_truth_table(XOR_gate())

OR Gate
0  1
0  0  1
1  1  1

AND Gate
0  1
0  0  0
1  0  1

XOR Gate
0  1
0  0  1
1  1  0

As NAND implements a complete basis set for classic computers, we therefore conclude that we can use to cast any classical algorithm in a quantum form. What does this mean? This means that the algorithm behaves exactly like the classical one, if we run it with CBS as an input (where the CBS are supposed to be read like binary numbers for the classical input). However, we can also run the algorithm with an entangled superposition state and retain a true quantum result. As a example we take an entirely fictitious algorithm that is fed with a four bit number. We run it twice, once with the input number “12” and once with the input “6”. Suppose the algorithm us VERY hard to compute, then we would, after a long wait compile the following table:

 Input Output 1100 (12) 0110 (6) 1110 (14) 0011 (3)
We can now turn the algorithm into a quantum version by replacing all its NANDs with their quantum equivalents and we would be guaranteed to get:

 Input Output $|1100\rangle\ (12)$ $|0110\rangle\ (6)$ $|1110\rangle\ (14)$ $|0011\rangle\ (3)$
This is certainly not an improvement. However, because the quantum algorithm is necessarily linear (it is a unitary matrix!) this means that if we input a superposition of CBS-states we obtain a result, which is superimposed of both classical runs:

 Input $\alpha|1100\rangle+\beta|0110\rangle$ $\alpha|1110\rangle+\beta|0011\rangle$
Of course, we can generalize this to all possible superpositions, if we wanted to. We are now in a position, where we can run a classical algorithm with all possible classical inputs at once! This is, however, not really useful, because upon a simple measurement in the CBS we would still collapse onto ONE particular solution of the algorithm and we would not even know which one. So, we can only get a real advantage out of this, if what we are really looking for are specific properties of groups of solutions.

### Task 1: Addition as an Example¶

We shall implement a circuit for the addition of two n-bit numbers $a$ and $b$ in a quantum circuit. Bitwise addion is carried out in the same way as you would add number son paper, i.e. add digits from the least to the most significant and using carry-bits. The circuit is depicted in the following chart:

The circuit must be applied from the $0^{th}$ bit to the $n-1^{st}$ bit, starting without a carry input quibt and using the $c_{out}$ as $c_{in}$ for the next Qubit. The last $c_{out}$ is retained. The result thus has $n+1$ Qubits, namely $(s_0,...,s_{n+1}, c_{out})$.

Implement a 4 bit Quantum-Adder and demonstrate that $13+6=19$.

We start with creating the half-adder:

In [7]:
def half_adder(as_gate=True):
a_qubit = QuantumRegister(1, name='a')
b_qubit = QuantumRegister(1, name='b')
s_qubit = QuantumRegister(1, name='s')
c_qubit = QuantumRegister(1, name='c')
qc = QuantumCircuit(a_qubit, b_qubit, s_qubit, c_qubit)

qc.append(AND_gate(), [a_qubit,b_qubit,c_qubit])
qc.append(XOR_gate(), [a_qubit,b_qubit,s_qubit])

if (as_gate):
U_s = qc.to_gate()
U_s.name = "HalfAdd"
return U_s
else:
return qc

half_adder(as_gate=False).draw()

Out[7]:

We then create the full Adder from the Half Adder. This requires intermediate QuBits to store intermediate results (altogether three), corresponding to any of the lines not connected to input or output in the image above. We call these "auxiliary" qubits.

We want to be able to reuse then, so we have to clean up (uncompute) them after usage. This is done after the or-gate. Uncomputing aux1, and aux2 is simple. We can just repeat the first line; where aux1 and aux2 are the output. Any bit-flip carried out on them will be undone by a second flip. If no flip was carried out a second no-flip will not do anthing either. However, can't do this as a first step in uncomputation because we also need to uncompute aux3 for which we need the intermediary result from aux2. We can use the same approach here (uncomputation through recomputation) but can't just invoke the half-adder again, because that would uncompute s_qubit as well. Thus we just enact the part of the half-adder again. This is a bit unelegant but I don't have time for a smoother solution.

In [8]:
def full_adder(as_gate=True):
a_qubit = QuantumRegister(1, name='a')
b_qubit = QuantumRegister(1, name='b')
cin_qubit = QuantumRegister(1, name='cin')
aux1_qubit = QuantumRegister(1, name='aux1')
aux2_qubit = QuantumRegister(1, name='aux2')
aux3_qubit = QuantumRegister(1, name='aux3')
s_qubit = QuantumRegister(1, name='s')
c_qubit = QuantumRegister(1, name='c')
qc = QuantumCircuit(a_qubit, b_qubit, cin_qubit, aux1_qubit, aux2_qubit, aux3_qubit, s_qubit, c_qubit)

#Compute Sum
qc.append(half_adder(), [a_qubit, b_qubit, aux1_qubit, aux2_qubit])
qc.append(half_adder(), [aux1_qubit, cin_qubit, s_qubit, aux3_qubit])
qc.append(OR_gate(), [aux2_qubit, aux3_qubit, c_qubit])
#Uncompute aux1-3
qc.append(AND_gate(), [aux1_qubit, cin_qubit, aux3_qubit])
qc.append(half_adder(), [a_qubit, b_qubit, aux1_qubit, aux2_qubit])

if (as_gate):
U_s = qc.to_gate()
U_s.name = "FullAdd"
return U_s
else:
return qc

full_adder(as_gate=False).draw()

Out[8]:

We then compose the addition circuit by stacking the full adder

In [9]:
def nbit_addition(nbits, as_gate=True):
a_qubits = QuantumRegister(nbits, name='a')
b_qubits = QuantumRegister(nbits, name='b')
c_qubits = QuantumRegister(nbits+1, name='c')
aux_qubits = QuantumRegister(3, name='aux')
s_qubits = QuantumRegister(nbits, name='s')
qc = QuantumCircuit(a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits)

for k in range(nbits):
qc.append(full_adder(), [a_qubits[k], b_qubits[k], c_qubits[k], aux_qubits[0], aux_qubits[1], aux_qubits[2], s_qubits[k], c_qubits[k+1]])

if (as_gate):
U_s = qc.to_gate()
U_s.name = "Addition"
return U_s
else:
return qc

nbit_addition(4,as_gate=False).draw()

Out[9]:

Let's now calculate 13 (1101) + 6 (0110) = 19 (1 0011)

In [10]:
nbits = 4;
a_qubits = QuantumRegister(nbits, name='a')
b_qubits = QuantumRegister(nbits, name='b')
c_qubits = QuantumRegister(nbits+1, name='c')
aux_qubits = QuantumRegister(3, name='aux')
s_qubits = QuantumRegister(nbits, name='s')

s_bits = ClassicalRegister(nbits, name='s_bits')
c_bit = ClassicalRegister(1, name='c_bit')

qc = QuantumCircuit(a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits, s_bits, c_bit)

#initiate the 13 (reverse order!)
qc.x(a_qubits[3])
qc.x(a_qubits[2])
qc.x(a_qubits[0])

#initiate the 6 (reverse order!)
qc.x(b_qubits[2])
qc.x(b_qubits[1])

#this seems like a rather unelegant way to compile the list of qubits but it's the inly way I found that would work
qlist = []
for qubit in a_qubits:
qlist.append(qubit)
for qubit in b_qubits:
qlist.append(qubit)
for qubit in c_qubits:
qlist.append(qubit)
for qubit in aux_qubits:
qlist.append(qubit)
for qubit in s_qubits:
qlist.append(qubit)
qc.append(nbit_addition(4), qlist)
#this seems like the more eleqgant solution but does not work
#qc.append(nbit_addition(4), [a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits])

qc.measure(s_qubits, s_bits)
qc.measure(c_qubits[nbits], c_bit)

qc.draw()

Out[10]:

Let's try this out

In [11]:
qc_t = transpile(qc, sim)
result = sim.run(qc_t, shots=1).result()
cts = result.get_counts().int_outcomes()
print(cts)
plot_histogram(cts)

{19: 1}

Out[11]:

This gives 19, as expected. Feel free to play around with it.

### Task 2: Uncomputation¶

The algorithm as such will probably need ancilla Qubits to store intermediate results. The carry lowest $n-1$ carry bits are such an example. For usage of the algorithm as an Oracle (see below) we MUST MAKE SURE that all ancillas are returned to their origina state, because otherwise the entire mathematics of the algorithms does not work anymore (it gets mixed up in entanglement, if you so wish). This process is called uncomputation.

Implement a 4 bit Quantum-Adder and demonstrate that $13+6=19$ which is fully uncomputed, e.g. it does not change the input qubits and also does not change the ancillas. Only changing of result QuBits is permissible.

We have already cleaned up the ancilla bits of the Full-Adder. We only need to clean up the lower n carry bits (the upper one is a part of the result). We thus redefine the nbit_addition function. We use the test approach of uncomputation by recomputation. To do so, we need to split off the Carry-Calculation-Part of the Full Adder, becuase we only need to uncompute this part. Also keep in mind that we have to do the uncomputation backwards, because we need the n-1-th carry but to calc the nth.

In [12]:
def full_adder_c_only(as_gate=True):
a_qubit = QuantumRegister(1, name='a')
b_qubit = QuantumRegister(1, name='b')
cin_qubit = QuantumRegister(1, name='cin')
aux1_qubit = QuantumRegister(1, name='aux1')
aux2_qubit = QuantumRegister(1, name='aux2')
aux3_qubit = QuantumRegister(1, name='aux3')
c_qubit = QuantumRegister(1, name='c')
qc = QuantumCircuit(a_qubit, b_qubit, cin_qubit, aux1_qubit, aux2_qubit, aux3_qubit, c_qubit)

#Compute Sum
qc.append(half_adder(), [a_qubit, b_qubit, aux1_qubit, aux2_qubit])
qc.append(AND_gate(), [aux1_qubit, cin_qubit, aux3_qubit])
qc.append(OR_gate(), [aux2_qubit, aux3_qubit, c_qubit])
#Uncompute aux1-3
qc.append(AND_gate(), [aux1_qubit, cin_qubit, aux3_qubit])
qc.append(half_adder(), [a_qubit, b_qubit, aux1_qubit, aux2_qubit])

if (as_gate):
U_s = qc.to_gate()
U_s.name = "FullAdd C-Only"
return U_s
else:
return qc

def nbit_addition_clean(nbits, as_gate=True):
a_qubits = QuantumRegister(nbits, name='a')
b_qubits = QuantumRegister(nbits, name='b')
c_qubits = QuantumRegister(nbits+1, name='c')
aux_qubits = QuantumRegister(3, name='aux')
s_qubits = QuantumRegister(nbits, name='s')
qc = QuantumCircuit(a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits)

for k in range(nbits):
qc.append(full_adder(), [a_qubits[k], b_qubits[k], c_qubits[k], aux_qubits[0], aux_qubits[1], aux_qubits[2], s_qubits[k], c_qubits[k+1]])
for k in range(nbits-2,-1,-1):
qc.append(full_adder_c_only(), [a_qubits[k], b_qubits[k], c_qubits[k], aux_qubits[0], aux_qubits[1], aux_qubits[2], c_qubits[k+1]])

if (as_gate):
U_s = qc.to_gate()
U_s.name = "Addition Clean"
return U_s
else:
return qc

nbit_addition_clean(4,as_gate=False).draw()

Out[12]:

Let's see: we try this out but now we measure all the qubits, because we want to see that the aux's are all zero.

In [13]:
nbits = 4;
a_qubits = QuantumRegister(nbits, name='a')
b_qubits = QuantumRegister(nbits, name='b')
c_qubits = QuantumRegister(nbits+1, name='c')
aux_qubits = QuantumRegister(3, name='aux')
s_qubits = QuantumRegister(nbits, name='s')

qc = QuantumCircuit(a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits)

#initiate the 13 (reverse order!)
qc.x(a_qubits[3])
qc.x(a_qubits[2])
qc.x(a_qubits[0])

#initiate the 6 (reverse order!)
qc.x(b_qubits[2])
qc.x(b_qubits[1])

#this seems like a rather unelegant way to compile the list of qubits but it's the inly way I found that would work
qlist = []
for qubit in a_qubits:
qlist.append(qubit)
for qubit in b_qubits:
qlist.append(qubit)
for qubit in c_qubits:
qlist.append(qubit)
for qubit in aux_qubits:
qlist.append(qubit)
for qubit in s_qubits:
qlist.append(qubit)
qc.append(nbit_addition_clean(4), qlist)
#this seems like the more eleqgant solution but does not work
#qc.append(nbit_addition(4), [a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits])

qc.measure_all()

qc.draw()

Out[13]:

Let's go.

In [14]:
qc_t = transpile(qc, sim)
result = sim.run(qc_t, shots=1).result()
cts = result.get_counts()
print(cts)
plot_histogram(cts)

{'00110001000001101101': 1}

Out[14]:

This has worked. All results are fine, all low carry bit and aux bits are uncomputed. Congratulations, you can now compute a+b on a Quantum Computer.

## Quantum Oracles¶

For many computationally hard to solve problems, the best solution is systematically test possible solution candidates until a proper solution is found. This approach is said to use and “oracle” function: a function $O(x)$, which returns $O(x)=0$ for all $x$, which are not solutions to the problem and $O(x)=1$ for proper solutions to the problem. The name “oracle” is altogether fitting because it contains two central ideas to this solution approach

• the answer is always correct but in the most cases of very minimal use, and
• one it usually assumes that asking the oracle is connected to some cost.

The difference of the 21st century and the 2nd century BC is that this cost is due in computational resources and not in sacrificial goats.

Using our understanding of Classical Problems on a Quantum Computer we can, of course, create a quantum version of the oracle $\hat{O}$, i.e., $\hat{O}|x\rangle|o\rangle=|x\rangle|o\oplus{}O(x)\rangle$, where $|x\rangle$ is the register of input Qubits and $|o\rangle$ is the single output qubit, i.e. the Orcacle's answer.

It is helpful to initialize the output Qubit into a superposition state $|q\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ because this implies that

$$\hat{O}|x\rangle\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)=(-1)^{o(x)}|x\rangle\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$$

.

Which is a rather funny result, because it tells us that the result qubit $|o\rangle$ does not change its state irrespective of the input being a solution. The quantum oracle rather marks solutions to search problems by shifting their phase by $\pi$ with respect to all other solutions. You can also think in eigenstates: all possible CBS inputs are eigenstates to the Oracle operator (if $|o\rangle$ is chosen appropriately) with the eigentvalue being +1 or -1 depending on the correctness of the result. Because the application of the oracle does not affect the oracle QuBit at all, it shall be omitted from the fruther discussion.

## The Grover Algorithm¶

The Grover Aogorithm uses the markdown-property imposed by the Oracle operator to amplify the quantum aplitude of correct solutions. It does so by the application of the Grover-Operator $\hat{G}=(2|\overline{\psi}\rangle\langle\overline{\psi}|-\hat{I})$, where $|\overline{\psi}\rangle=\sum_x|x\rangle$ is the balaned superposition of all possible CBS-states (the average).

The implementation of the Grover-Algorithm is discussed in detail in the QISKIT book and we give it here for reference.

In [15]:
def grover_operator(nqubits, as_gate=True):
qc = QuantumCircuit(nqubits)
# Apply transformation |s> -> |00..0> (H-gates)
for qubit in range(nqubits):
qc.h(qubit)
# Apply transformation |00..0> -> |11..1> (X-gates)
for qubit in range(nqubits):
qc.x(qubit)
# Do multi-controlled-Z gate
qc.h(nqubits-1)
qc.mct(list(range(nqubits-1)), nqubits-1)  # multi-controlled-toffoli
qc.h(nqubits-1)
# Apply transformation |11..1> -> |00..0>
for qubit in range(nqubits):
qc.x(qubit)
# Apply transformation |00..0> -> |s>
for qubit in range(nqubits):
qc.h(qubit)
# We will return the diffuser as a gate
if (as_gate):
U_s = qc.to_gate()
U_s.name = "G"
return U_s
else:
return qc

This is what the circuit looks like:

In [16]:
grover_operator(4, as_gate=False).draw()

Out[16]:

Use the grover_operator function in such as way:

In [17]:
qc = QuantumCircuit(4)
qc.append(grover_operator(4), [0,1,2,3])
qc.draw()

Out[17]:

## The Grover Algorithm¶

The entire algrithm works in the following way:

Initialization:

1. Initiate the input $|x\rangle$ in a balanced superposition using $\hat{H}$-gates on all QuBits
2. Initiate the Oracle $|o\rangle$ into the state $o\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$.

Iteration:

1. Apply the Oracle Operator $\hat{O}$.
2. Apply the grover-Operator $\hat{g}$.
3. Repeat Steps 1+2 for $\frac{\pi}{4}\sqrt{\frac{N}{M}}$ times, where $N=2^n$ is the size of the search space and $M$ is the number of correct answers.*

$*$There is an efficient way of determining $M$ if it is unknown, called Quantum Counting.

Why does the algorithm work? To answer that question it is useful to imagine the entire search space spanned by all as a high-dimensional vector space. This space is spanned by two linearily independent subspaces, the $M$-dimensional subspace of “correct” answers $|x'\rangle$ and the $N-M$ dimensional subspace or incorrect answers $|x''\rangle$. Within both of these subspaces we define normalized superposition states:

$$|\alpha\rangle = \frac{1}{\sqrt{N-M}}\sum_{x''}|x''\rangle$$$$|\beta\rangle = \frac{1}{\sqrt{M}}\sum_{x'}|x'\rangle$$

The initial state of the input register produced by an equal superposition of all CBS is then simply:

$$|\psi\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle+\sqrt{\frac{M}{N}}|\beta\rangle=\cos{\frac{\theta_0}{2}}|\alpha\rangle+\sin{\frac{\theta_0}{2}}|\beta\rangle$$

where $\theta_0\ll1$ because there are many more wrong solutions than there are correct solutions. We find that the angle $\theta$ is a measure of the “correctness”, e.g. $\theta=0$ is a balanced superposition of all wrong results, whereas $\theta=\pi$ is a superposition of all correct answers. The Grover-Algorithm starts with $\theta=\theta_0$ and increases the angle for every iteration. It is also noteworthy that $|\psi(\theta_0)\rangle=|\overline{x}\rangle$, i.e. the starting point of the algorithm is the average.

The first step in the iteratation is the application of the Oracle and we had seen that the oracle flips the sign of the correct answers hence: $$\hat{O}|\psi(\theta)\rangle=\cos{\frac{\theta}{2}}|\alpha\rangle-\sin{\frac{\theta}{2}}|\beta\rangle=|\psi(-\theta)\rangle$$

If visualized in the $|\alpha\rangle-|\beta\rangle$-plane this amount to a reflecton at the $|\alpha\rangle$-axis.

The application of the Grover operator $\hat{G}=(2|\psi(\theta_0)\rangle\langle\psi(\theta_0)|-\hat{I})$ changes the value to:

$$\hat{G}|\psi(-\theta)\rangle=\cos{\frac{2\theta_0+\theta}{2}}|\alpha\rangle+\sin{\frac{2\theta_0+\theta}{2}}|\beta\rangle=|\psi(2\theta_0+\theta)\rangle$$

This is because the Grover operator also does a reflection but this time about the initial state.

Since we have started in the point $\theta_0$ we find that after $k$ iterations we are in the state:

$$(\hat{G}\hat{O})^k|\psi(\theta_0)\rangle=|\psi(\frac{2k+1}{2}\theta_0)\rangle$$

The geometric interpretation is indeed quite simple. The application of $\hat{G}$ has the state $|\psi\left(\theta\right)\rangle$ by $2\theta_0$ counterclockwise from the $|\alpha\rangle$ towards the $|\beta\rangle$ direction and has thus increased the relative quantum amplitude and therefore the likelihood of observing a correct answer.

It is now a mere question of when to terminate, such that we do not “overrotate” and again decrease the likelihood of the system being in any of the CBS, which comprise $|\beta\rangle$. Quantitatively we must terminate the algorithm, when $\frac{2k+1}{2}\theta_0=\frac{\pi}{2}$ this means that: $k=\frac{\pi}{2\theta}-\frac{1}{2}$.

Let’s assume for simplicity that $M\ll N$, e.g. that a correct answer is a fairly rare event. Note that this approximation is an exclusively technical approximation. We can approximate $\theta\approx 2\sqrt{M/N}$ and thus we get:

$$K=\frac{\pi}{4}\left(\frac{N}{M}\right)^{1/2}-\frac{1}{2}\approx\frac{\pi}{4}\left(\frac{N}{M}\right)^{1/2}$$

### Task 3: Grover Solution finding¶

Use the grover algorithm and your 4-bit Adding-Circuit to find a solution to the problem $a+b=17$.

We start by calculating the number of iteration we need to find a solution. We do so by cheating, as we, of course, know the solutions beforehand. There are $M=14$ solutions, namely $2+15$, $3+14$, ... , $15+2$. The total search space is $N=2^{8}=256$. We hance find that $K=\frac{\pi}{4}\left(\frac{N}{M}\right)^{1/2}=3.2$, so we need roughly $K\approx3$ iterations of the circuit. That was easy.

Next we need to design the oracle. Let's first assume that we have the Addition carried out such that we have the (quantum superposition) of results stored in register $(s_0,...,s_{n+1}, c_{out})$. We must compare bitwise with 17=10001, e.g. the result is ONLY 17 if all the number are equal. To do so we employ an $n+1$ input Toffoli-Gate, which is a natural AND (e.g. it operates if all input are 1) together with $NOT$-gates at those bts, which are supposed to be $0$. Don't forget to uncompute those!

In [18]:
def comparator_17(as_gate=True):
qc = QuantumCircuit(6)
##prepare for comparison with 10001 by flipping the middle three bits
qc.x(1)
qc.x(2)
qc.x(3)
##compare and store result in qubit 6
qc.mct(list(range(5)), 5)  # multi-controlled-toffoli
##unflip
qc.x(1)
qc.x(2)
qc.x(3)

if (as_gate):
U_s = qc.to_gate()
U_s.name = "Compare with 17"
return U_s
else:
return qc

This is what the circuit looks like

In [19]:
comparator_17(as_gate=False).draw()

Out[19]:

Use it in such a way

In [20]:
qc = QuantumCircuit(6)
qc.append(comparator_17(), [0,1,2,3,4,5])
qc.draw()

Out[20]:

The we need to initialize everything properly. Keep in mind that we have to initialize both the input qubits and the oracle qubits and we have to create empty ancilliaries.

In [21]:
qc = QuantumCircuit(3)
qc.toffoli(0,1,2)
qc.draw()

Out[21]:
In [23]:
#create all Qubits, this time with names
a_qubits = QuantumRegister(4, name='a')
b_qubits = QuantumRegister(4, name='b')
c_qubit = QuantumRegister(5, name='c')
aux_qubits = QuantumRegister(3, name='aux')
s_qubits = QuantumRegister(4, name='s')
o_qubit = QuantumRegister(1, name='o')
a_bits = ClassicalRegister(4, name='a_bits')
b_bits = ClassicalRegister(4, name='b_bits')

qc = QuantumCircuit(a_qubits, b_qubits, c_qubits, aux_qubits, s_qubits, o_qubit, a_bits, b_bits)

#Initialize into to balanced superposition
qc.h(a_qubits)
qc.h(b_qubits)

#Initialize Oracle Qubit onto Linear Down Polarization (could also use H->RZ->RZ)
qc.initialize([1, -1]/np.sqrt(2), o_qubit)

qlist = []
for qubit in a_qubits:
qlist.append(qubit)
for qubit in b_qubits:
qlist.append(qubit)
for qubit in c_qubits:
qlist.append(qubit)
for qubit in aux_qubits:
qlist.append(qubit)
for qubit in s_qubits:
qlist.append(qubit)

qlist2 = []
for qubit in s_qubits:
qlist2.append(qubit)
qlist2.append(c_qubit[4])
qlist2.append(o_qubit)

qlist3 = []
for qubit in a_qubits:
qlist3.append(qubit)
for qubit in b_qubits:
qlist3.append(qubit)

#first grover iteration
qc.barrier()
qc.append(nbit_addition_clean(4), qlist)
qc.append(comparator_17(),qlist2)
qc.append(nbit_addition_clean(4), qlist)
qc.append(grover_operator(8), qlist3)

#second grover iteration
qc.barrier()
qc.append(nbit_addition_clean(4), qlist)
qc.append(comparator_17(),qlist2)
qc.append(nbit_addition_clean(4), qlist)
qc.append(grover_operator(8), qlist3)

#third grover iteration
qc.barrier()
qc.append(nbit_addition_clean(4), qlist)
qc.append(comparator_17(),qlist2)
qc.append(nbit_addition_clean(4), qlist)
qc.append(grover_operator(8), qlist3)

#that's it, we are ready to measure a and b
qc.barrier()
qc.measure(a_qubits, a_bits)
qc.measure(b_qubits, b_bits)

qc.draw(fold=-1)

Out[23]:

Now we run the code 100 times to see the results distribution. Keep the fingers crossed.

In [26]:
qc_t = transpile(qc, sim)
result = sim.run(qc_t, shots=100).result()
cts = result.get_counts()
plot_histogram(cts)

Out[26]:

The results are all combinations of a and b that produce 17. You can verify by taking the first block of 4 bits and add them with the seocnd block of 4 qubits. Example from the first 0010 (2) + 1111 (15) = 17.

The same is true for all results (at least to should be true for most, because we enver end up perfetly at $|\beta\rangle$. But, and this is important: with just three steps we (rbute force) find a solution in a serach space with 256 possible items. . This is amazing.


text:
1
AIEEE 2004
+4
-1
The equation of the straight line passing through the point $$(4, 3)$$ and making intercepts on the co-ordinate axes whose sum is $$-1$$ is
A
$${x \over 2} - {y \over 3} = 1$$ and $${x \over -2} +{y \over 1} = 1$$
B
$${x \over 2} - {y \over 3} = -1$$ and $${x \over -2} +{y \over 1} = -1$$
C
$${x \over 2} + {y \over 3} = 1$$ and $${x \over 2} +{y \over 1} = 1$$
D
$${x \over 2} + {y \over 3} = -1$$ and $${x \over -2} +{y \over 1} = -1$$
2
AIEEE 2004
+4
-1
Let $$A\left( {2, - 3} \right)$$ and $$B\left( {-2, 1} \right)$$ be vertices of a triangle $$ABC$$. If the centroid of this triangle moves on the line $$2x + 3y = 1$$, then the locus of the vertex $$C$$ is the line
A
$$3x - 2y = 3$$
B
$$2x - 3y = 7$$
C
$$3x + 2y = 5$$
D
$$2x + 3y = 9$$
3
AIEEE 2004
+4
-1
If the sum of the slopes of the lines given by $${x^2} - 2cxy - 7{y^2} = 0$$ is four times their product $$c$$ has the value
A
$$-2$$
B
$$-1$$
C
$$2$$
D
$$1$$
4
AIEEE 2004
+4
-1
If one of the lines given by $$6{x^2} - xy + 4c{y^2} = 0$$ is $$3x + 4y = 0,$$ then $$c$$ equals
A
$$-3$$
B
$$-1$$
C
$$3$$
D
$$1$$
JEE Main Subjects
Physics
Mechanics
Electricity
Optics
Modern Physics
Chemistry
Physical Chemistry
Inorganic Chemistry
Organic Chemistry
Mathematics
Algebra
Trigonometry
Coordinate Geometry
Calculus
EXAM MAP
Joint Entrance Examination

format: plain


text:
# A 11 year old female has epilepsy.she has problems with wetting the bed and does so every night.is her epilepsy the cause

###### Question:

A 11 year old female has epilepsy. she has problems with wetting the bed and does so every night.
is her epilepsy the cause for her wetting?

### Calculate how many dietary folate equivalents a pregnant woman is getting from 200 mcg folate from supplement, 80 mcg folate from fortified

Calculate how many dietary folate equivalents a pregnant woman is getting from 200 mcg folate from supplement, 80 mcg folate from fortified cereal and 100 mcg folate from other foods (5 points). What is the daily recommended values for folate intake for pregnant women (1 point)? How does the intake ...

### Answers for from three men in a boat ( to say of the dog)

Answers for from three men in a boat ( to say of the dog)...

### The discount yield on a T-bill differs from the T-bill's bond equivalent yield (BEY) because I. the

The discount yield on a T-bill differs from the T-bill's bond equivalent yield (BEY) because I. the discount yield is the return per dollar of face value and the BEY is a return per dollar originally invested. II. a 360-day year is used on the discount yield and the BEY uses 365 days. III. the disco...

### Is the following sequence arithmetic or geometric? If it is arithmetic what is d and if it isgeometric what is r? also, what is

Is the following sequence arithmetic or geometric? If it is arithmetic what is d and if it is geometric what is r? also, what is the 12th term 3, 12, 21, 30...

### Jose must choose a number between 61 and 107 that is a multiple of 3, 6, and 9. Write all the numbers that he could choose.

Jose must choose a number between 61 and 107 that is a multiple of 3, 6, and 9. Write all the numbers that he could choose....
One caterer charges a basic fee of $\$ 100$plus$\$15$ per person. A second caterer charges a basic fee of $\$200$plus$\$12$ per person. What is the least number of people that could go to a party so that the second caterer is cheaper to hire?...

### There is an oil refinery located on a river. a fish farm is located in the bay, and is adversely affected

There is an oil refinery located on a river. a fish farm is located in the bay, and is adversely affected by the oil refiner’s water pollution. more oil produces more pollution, and more pollution increases the fish farmer’s costs. the price for refining a barrel of crude oil is po = 200, and th...

### For what reasons do poets use parallelism? Check all that apply.

For what reasons do poets use parallelism? Check all that apply....

### When should information be used as a quote rather than paraphrased?

When should information be used as a quote rather than paraphrased?...

### Determining the best payoff for each alternative and choosing the alternative with the 'best of the best' is the approach

Determining the best payoff for each alternative and choosing the alternative with the "best of the best" is the approach called:...

### Atire has a radius of 13 inches. how far does the tire travel every time it turns exactly once? use 3.14 for pi and round

Atire has a radius of 13 inches. how far does the tire travel every time it turns exactly once? use 3.14 for pi and round your final answer to one decimal place....

### The sauce burned before hans remembered to stir it

The sauce burned before hans remembered to stir it...

### What is the pH of a solution that has a concentration of 1 X 10-3 hydrogen ions?

What is the pH of a solution that has a concentration of 1 X 10-3 hydrogen ions?...

### Write a balanced nuclear equation for the alpha decay of potassium-224

Write a balanced nuclear equation for the alpha decay of potassium-224...

### Portfolio Activity: Writing a RésuméClick to review the online content. Then answer the question(s)

Portfolio Activity: Writing a Résumé Click to review the online content. Then answer the question(s) below, using complete sentences. Scroll down to view additional questions. Online Content: Site 1 Online Content: Site 2 You can use this area to create your resume....

### Abasic disc clutch is to be designed to transmit a torque of 100 lbf-in. the outer ring diameter is

Abasic disc clutch is to be designed to transmit a torque of 100 lbf-in. the outer ring diameter is to be 4 inches. the values for the molded friction material are to be pmax = 200 psi and f = 0.25. find appropriate values for the ring inside radius (ri) and the clamping force (f)....

### Heres the rest of my points. im leaving life. bye peeps

Heres the rest of my points. im leaving life. bye peeps...

### Part a which statement identifies the central idea of the text students that reported having meaningful

Part a which statement identifies the central idea of the text students that reported having meaningful...


text:
## Classical Limit

It is possible to analyze the circumstances that lead to classical-like trajectories in Bohmian mechanics.

One of the nice features of this analysis is that it very much shows the strength of Bohmian mechanics: waves can be waves and particles can be particles. We do not need a spread out wave to become a wave packet traveling classically; the trajectory itself is picking out the effective wave packet.

#### Setting up the classical limit

We have trajectories in Bohmian mechanics. The simplest question is, under what conditions are these trajectories approximately classical?

That is perhaps a little too simple. One imagines that a single particle, such as an electron, will not move classically. But that perhaps a grouping of such particles, say a stone, will move classically.

Thus, the first step is to change coordinates to a center of mass coordinate, $X$, and internal relative coordinates of all of the other particles, $Y$.

This allows a splitting of the Hamiltonian and the effective potential acting on $X$ is where one part of the conditions will arise. This is similar to Ehrenfest’s theorem of standard quantum mechanics.

With this setup, we can then investigate when the path $X(t)$ will be classical.

It is quite acceptable to have an initial (very short) period of time in which there is quantum behavior that relaxes into classical behavior.

#### the emergence of classical behavior

There are several steps to the classical limit, conceptually. The first is to establish the behavior for a suitable class of wave functions. The wave functions are, in particular, those of the form $\psi(X) \phi(Y)$ with $\psi$ a wave packet of wave length $\lambda$. Then our condition is that $V(X)$, the effective (classical) external potential, should vary slowly relative to the wave length $\lambda$. In particular, what one seems to need is $$\lambda \ll \sqrt{\frac{|V^{\,\,\prime}|}{|V^{\,\,\prime \prime \prime}|}} = L(V)$$ This is derived from the Ehrenfest $$m\langle \ddot{X} \rangle = \langle -\nabla V(X(t)) \rangle$$ and wanting to make the assumption that $$- \langle \nabla V(X(t)) \rangle \approx – \nabla V(\langle X(t)\rangle)$$

So the classical limit is somewhat giving us a condition for good initial wave functions. This might first seem a little useless since wave functions do not evolve into wave packets. Or do they in some sense?

So the next steps are to argue that a broader class of wave functions will relax to locally look like appropriate wave packets. So one does that. What kind of condition might be placed on the wave function? Well, one could use the mean kinetic energy, $E_{\mathrm{kin}} (\psi) = \langle \psi, -\frac{\hbar^2}{2m} \nabla_x^2 \psi \rangle$  to generate a suitable wave length: $$\lambda (\psi) = \frac{h}{\sqrt{2m E_{\mathrm{kin}} (\psi)}}$$

The claim is that under the condition $$\lambda(\psi) \ll L(V)$$ we have first the wave evolution spreading the wave function out under the direction of the kinetic term,  quickly leading to a locally plane wave function. And then, this local plane wave has local classical motion. And the particle rides the wave, thus looking classical.

#### On Classical Crossing

One little problem is that classical trajectories, being second order, can cross each other in configuration space. This does not happen in Bohmian mechanics. And such situations ought to arise. Thus classical motion should not work.

But then there is decoherence. So at first, the wave is crazy. Then it relaxes. Then it starts to come back together, but by that time, it is entangled with the environment or even with its own internal degrees of freedom. So the waves that are drawn back to each other classically miss each other as these waves are on configuration space and the other coordinates of the configuration have separated them.

Which wave is relevant? The one in which the actual configuration is located. It is this which gives the wave plus particle combination such power to make everything work out just right.

#### References

Seven Steps Toward a Classical World by Valia Allori, Detlef Dürr, Shelly Goldstein, Nino Zanghí, and references therein.


text:
## Is this contains an open set?

On the number line R, does [-1,$$\infty$$) contain an open set?

because it includes -1, don't think it is an open set.

 PhysOrg.com science news on PhysOrg.com >> Hong Kong launches first electric taxis>> Morocco to harness the wind in energy hunt>> Galaxy's Ring of Fire

 Quote by zli034 On the number line R, does [-1,$$\infty$$) contain an open set? because it includes -1, don't think it is an open set.
It's a half open interval that you've shown. If you define a set {$$[-1,\infty)$$} then it contains at least one half open subset.

 Blog Entries: 1 Recognitions: Homework Help Is the question: Is $$[-1, \infty)$$ an open set? Or is the question: Does $$[-1, \infty)$$ contain an open set?

## Is this contains an open set?

 Quote by Office_Shredder Is the question: Is $$[-1, \infty)$$ an open set? Or is the question: Does $$[-1, \infty)$$ contain an open set?
What's the difference?

 It is not an open set. But it contains the open set (4, 7) for example.

 Quote by g_edgar It is not an open set. But it contains the open set (4, 7) for example.
I guess I'm not understanding the OP's question. Any non zero interval on the reals "contains" every possible combination: [a,b],(a,b),(a,b],[a,b). Any such interval has a bijective mapping to the entire set of reals, so of course the interval [-1,$$\infty)$$ "contains" open sets.

EDIT: Perhaps I'm mistaken, but in terms of open and closed sets or subsets, I'm considering the actual membership of a given set to be dependent on the specification (choice) of that set. Therefore I could specify that every subset of C:C subset of R be closed.


text:
# A question about parametrized differentiable curves.

I am reading Manfredo Carmo's book on differential geometry and I am slightly confused by something. It says that the definition of a parametrized differentiable curve is a map $\alpha: I \rightarrow \mathbb{R}^3$ for an interval $I$ of $\mathbb{R}.$ However, it lists a map $\alpha: \mathbb{R} \rightarrow \mathbb{R}^2$ as an example. My guess is that this is equivalent to a map $\alpha: \mathbb{R} \rightarrow \mathbb{R}^3$ except we send the $z$ coordinate to 0 at all points. Is this the correct way of looking at this?

• A "differentiable curve" is really a map $I \to \Bbb{R}^n$ for any $n$. – Nick Jan 12 '18 at 4:29

If you chose to embed $\iota:\mathbf{R}^2\to\mathbf{R}^3$ as $(x,y)\mapsto (x,y,0)$ then this indeed works out naturally. A parameterized curve $\alpha:I\to \mathbf{R}^2$ given by $\alpha(t)=(x(t),y(t))$ can be identified with the curve $\tilde{\alpha}=\iota\circ \alpha.$ More concretely, we have that $\tilde{\alpha}(t)=(x(t),y(t),0).$
On the other hand, we really needn't worry about the dimensionality. The definition holds for any choice of $n$. We can define a differentiable curve $\gamma:I\to \mathbf{R}^n$ for any $n\in \mathbf{N}_{\ge 1}$ by requiring that the component functions $\gamma_i(t)$ for $1\le i\le n$ be smooth as functions $\gamma_i:I\to\mathbf{R}$. Note that here I'm thinking of $\gamma$ as $$\gamma(t)=(\gamma_1(t),\ldots, \gamma_n(t)).$$


text:
# Error in Polynomial Factoring

From Ramanujan's Notebooks IV:

Let $\alpha,\beta$ and $\gamma$ be the roots of$$x^3-ax^2+bx-1=0\tag1$$Now, choose cube roots such that $(\alpha\beta\gamma)^{1/3}=1$ and then let$$z^3-\theta z^2+\varphi z-1=0\tag2$$Denote the cubic polynomial with roots $\alpha^{1/3},\beta^{1/3},\gamma^{1/3}$. Cubing both sides of the equality$$z^3-1=\theta z^2-\varphi z\tag3$$We find that$$(z^3-1)^3-\theta^3z^6+\varphi^3z^3+3\theta\varphi z^3(z^3-1)=0\tag4$$Since $\alpha^{1/3},\beta^{1/3},\gamma^{1/3}$ are roots of $(2)$, they are also the root of $(4)$. As a cubic polynomial in $z^3$, $(4)$ thus has the roots $\alpha,\beta,\gamma$. Comparing $(1)$ with $(4)$, we deduce$$a=\theta^3+3-3\theta\varphi\tag5$$$$b=\varphi^3+3-3\theta\varphi\tag6$$ If we define $t$ by$$\theta^3=a+6+3t\tag7$$Then, by $(2)$ and $(7)$, $$\alpha^{1/3}+\beta^{1/3}+\gamma^{1/3}=\theta=(a+6+3t)^{1/3}$$And similarly, $$(\alpha\beta)^{1/3}+(\beta\gamma)^{1/3}+(\gamma\alpha)^{1/3}=\varphi=(b+6+3t)^{1/3}$$

While the proof is fairly elementary, there is one problem that I'm not sure how Bruce got there. From $z^3-1=\theta z^2-\varphi z$, to the next step, how'd they get the $3\theta\varphi z^3(z^3-1)$. When you expand $\theta z^2-\varphi z$, you get$$(\theta z^2-\varphi z)^3=\theta^3z^6-3\theta^2\varphi z^5+3\theta\varphi^2z^4-\varphi^3z^3$$So where did that term come from?

• The equation on the fourth line of your post is not a consequence of the one on the second line. Is that what you are asking about? – Jyrki Lahtonen May 11 '17 at 20:34
• @JyrkiLahtonen Yes, I added a bit more information. Hopefully that should be sufficient! – Crescendo May 11 '17 at 23:16

The equation (4) is correct. After both sides of equation (3) are cubed and the terms on the right get moved to the left there is only zero on the right. Now the cube of the right side of (4) is expanded by binomial theorem to four terms. Two of them are combined and factored with one factor being the right side of (3) which is immediately replaced with the left side of (3). A simple example will make this clear. $$a = b-c,$$ $$a^3 = b^3 - 3b^2c +3bc^2 -c^3,$$ $$a^3 -b^3 +c^3 = -3bc(b - c),$$ $$a^3 - b^3 + c^3 = -3abc.$$ The author just combined several steps. Notice that if we change the sign of $b$ we get the pretty result that if $a+b+c=0$ then $a^3+b^3+c^3=3abc$, which is a fact that Ramanujan was very familiar with.

• Is there a fourth power form similar to $a^3+b^3+c^3=3abc$? – Crescendo May 13 '17 at 18:28
• Thanks for that question. Indeed there is. You want to look at power sums. This is, $s(n) := a^n+b^n+c^n$ given that $s(1) = a+b+c = 0$. Now, $s(2) = 2(a^2+ab+b^2), s(4)=s(2)^2/2, s(5)=s(3)s(2)5/6$ and so on. – Somos May 13 '17 at 19:44
• I meant that $a^4+b^4+c^4+d^4$ for fourth powers, $a^5+b^5+c^5+d^5+e^5$ for fifth powers, and so on... Is there such formula for that? Sorry for not being too specific... – Crescendo May 14 '17 at 19:47
• Thanks for that further question. Has a similar answer and you can come up with your own variation. Let $s(n):=a^n+b^n+c^n+d^n$ given that $s(1)=s(2)=0$. Now $s(5)=0, s(6)=s(3)^2/3, s(7)=s(3)s(4)7/12, s(8)=s(4)^2/4,s(9)=s(3)^3/9$ and so on. – Somos May 14 '17 at 21:11

The last term on the left multiplies out to $3\theta\varphi(z^3-1)=3\theta\varphi z^3-3\theta\varphi$ which are intended to be the two middle terms from cubing the original right side. It should be $-3\theta\varphi z^3(\theta z^2-\varphi z)$

• That's the problem I'm wondering. The author used $3\theta\varphi(z^3-1)$. Is it an error? And if so, what would be the correct procedure? – Crescendo May 11 '17 at 23:16
• It is just expanding the cube of $\theta z^2-\varphi z$. The $\theta^3z^6$ and$\varphi^3 z^3$ got moved to the other side. The two middle terms of the cube are as I show. – Ross Millikan May 11 '17 at 23:20
• Perhaps I'm not quite understanding you. The author intended the $3\theta\varphi(z^3-1)$. Even though whenever I expand it, it isn't the same as the original function – Crescendo May 11 '17 at 23:26
• I was just doing $(a-b)^3=a^3-b^3+3ab(a-b)$. Maybe there is some other relation that justifies the substitution – Ross Millikan May 12 '17 at 0:40
• So the book is wrong... – Crescendo May 12 '17 at 1:13


text:
1

# Evaluate the integral. $$\int \sinh ^{-1} x d x$$...

## Question

###### Evaluate the integral. $$\int \sinh ^{-1} x d x$$

Evaluate the integral. $$\int \sinh ^{-1} x d x$$

#### Similar Solved Questions

##### VoiayH the capacitgnce 8 Csi 4 3 vzlus cf 3 p0 0190 * 28 Iu
Voiay H the capacitgnce 8 Csi 4 3 vzlus cf 3 p 0 0190 * 28 Iu...
##### Let be the tollowing matrix:must use as the parameter instead of A , Enter its characteristic equation below: Note you equation wilh the equals sign: and you must enter your answer as 0 = For example 16,16,24. Enter the elgenvalues of Ihe matrix, including any repetilion_ 72 orthonormal basis for each eigenvalue eigenspace (c) Find the eigenvectors_ and then use Gram-Schmidt to tind an list of row vectors, below: eigenvectors Enter this matrix; Build an orthogonal matrix whose columns are these
Let be the tollowing matrix: must use as the parameter instead of A , Enter its characteristic equation below: Note you equation wilh the equals sign: and you must enter your answer as 0 = For example 16,16,24. Enter the elgenvalues of Ihe matrix, including any repetilion_ 72 orthonormal basis for e...
##### The ccompanying tabl contains cata on sample of full-time MBA programs offered by private universities. The variables collected for this sample are average starting salary upon graduation (S} tne percertage of applicants the full-time program who were ccepted_ the average GMAT test score of students entering the program, program per-year tuition (S), and percent of students with job offers at time of graduation_ Click on the icon to view the data on the MBA programsLet X- be the program per-year
The ccompanying tabl contains cata on sample of full-time MBA programs offered by private universities. The variables collected for this sample are average starting salary upon graduation (S} tne percertage of applicants the full-time program who were ccepted_ the average GMAT test score of students...
##### (30) 3 3 products Jeay NaOMe and mechanisms for the below reactions_ Jg" 2heat NaOMe
(30) 3 3 products Jeay NaOMe and mechanisms for the below reactions_ Jg" 2 heat NaOMe...
##### Point) Let X1,Xn be an independent trials process with common expected value and common variance 17-What is the exact value of the expected value of the average AnWhat is the variance of the average An Your formula should haveAccording to the Chebyshev inequality,P(IAn0.2)(your formula should have n)Using your bound irom the Chebyshev inequality, how many trials are needed s0 thatP(An0.2) 0.11? see the note below here)If you get an answer liken > 123.8,round it Up to the next whole number:You
point) Let X1, Xn be an independent trials process with common expected value and common variance 17- What is the exact value of the expected value of the average An What is the variance of the average An Your formula should have According to the Chebyshev inequality, P(IAn 0.2) (your formula should...
##### 25. Line UP 24ouitut the dilution amount for each tube Color ? (blue, pale blue, Solution Dilution of Original YTube Water Dye Dye clear) 1/10 OR 1X10-1 800 100 ul Loading Dye bu (1x stock) 100 pl Tube 1 Tp Sooh /1ooop 0 LcElu 9504 S0 ul Tube 2 504 | /Mnul MAu ss0pi sou Tube 3 coul obo4 L Tuac
25. Line UP 24ouitut the dilution amount for each tube Color ? (blue, pale blue, Solution Dilution of Original YTube Water Dye Dye clear) 1/10 OR 1X10-1 800 100 ul Loading Dye bu (1x stock) 100 pl Tube 1 Tp Sooh /1ooop 0 LcElu 9504 S0 ul Tube 2 504 | /Mnul MAu ss0pi sou Tube 3 coul obo4 L Tuac...
##### 3) (Lagrange Multipliers) (12 pts) Use the method of Lagrange multipliers to find the critical points o the funetion f (E,v) = rev subjeet to the constraint V? =2
3) (Lagrange Multipliers) (12 pts) Use the method of Lagrange multipliers to find the critical points o the funetion f (E,v) = rev subjeet to the constraint V? =2...
##### Block A of mass 8.0 kg and block B of unknown mass MB are attached to 3 rope that passes over a massless and frictionless pulley: A 50 N horizontal force pushes block A against a rough vertical wall. The coefficients of static and kinetic friction between the wall and block A are Ul; 0.40 and plk: 0.30. Initially block B is held at rest_ What are the smallest and largest masses of the block B that would would keep the blocks from moving when block B is released? As usual, take g = 10 m/s?(A) Sma
Block A of mass 8.0 kg and block B of unknown mass MB are attached to 3 rope that passes over a massless and frictionless pulley: A 50 N horizontal force pushes block A against a rough vertical wall. The coefficients of static and kinetic friction between the wall and block A are Ul; 0.40 and plk: 0...
##### 4 Find the equation of containing the(pan the vector passing through the points (1,2,-1) ad (-1,3,0) and
4 Find the equation of containing the(pan the vector passing through the points (1,2,-1) ad (-1,3,0) and...
##### Evaluate the trigonometric function using its period as an aid.57 cosi
Evaluate the trigonometric function using its period as an aid. 57 cosi...
##### 06nnnxS poinubretarpol [eMotratlt othe(Ottt Kat I67undintroom ["Mn #ratureRempealuLna( mroIne (coling conztntLeriennnnndclan ccunplelta
06nnnx S poinu bretarpol [eMotratlt othe(Ottt Kat I67 undintroom ["Mn #rature Rempealu Lna( mro Ine (coling conztnt Leriennnnndclan ccunplelta...
##### 12. [-/1 Points]DETAILSWEBASSIGNCALCET? 1.2.0066.Evaluate the IlmieIlm[-/1 Points]DETAILSWEBASSIGNCALCET2 1.2.0061.Evaluate the Iimit:[-/1 Points]DETAILSWEBASSIGNCALCET2 1.2.008B.Evaluate the Ilmit belov Involving absolute value
12. [-/1 Points] DETAILS WEBASSIGNCALCET? 1.2.0066. Evaluate the Ilmie Ilm [-/1 Points] DETAILS WEBASSIGNCALCET2 1.2.0061. Evaluate the Iimit: [-/1 Points] DETAILS WEBASSIGNCALCET2 1.2.008B. Evaluate the Ilmit belov Involving absolute value...
##### 23. [~/1 Points]DETAILSLARCALCI1 1.3.510.XP.MY NOTESASK YOUR TEACHERPRACTICE AUse the position function s(t) = -16t2 600, which gives the height (in feet) of an object that has fallen seconds IS given bv the followingseconds trom height of 600 feet. The velocitylimIfa construction worker drops wrench from height of 600 feet; how Tast WIl the wrench be falling aiter seconds? ftsNeed Help?Bcodl
23. [~/1 Points] DETAILS LARCALCI1 1.3.510.XP. MY NOTES ASK YOUR TEACHER PRACTICE A Use the position function s(t) = -16t2 600, which gives the height (in feet) of an object that has fallen seconds IS given bv the following seconds trom height of 600 feet. The velocity lim Ifa construction worker dr...
##### Two long straight current carrying wires are parallel to one another ad are in the plane of the page as shown: The wires are 30 cm apart and the current in the wire o the left is L =10 A and the current in the wire on the right is R = _ 20 A, with the current in the wire on the left going up the page and the current in the wire on the right going down the page: wat is the magnetic field due to the wires at a point in the plane of the page 15 cm to the left of the wire on the lef?
Two long straight current carrying wires are parallel to one another ad are in the plane of the page as shown: The wires are 30 cm apart and the current in the wire o the left is L =10 A and the current in the wire on the right is R = _ 20 A, with the current in the wire on the left going up the pag...
##### Build a model 0f an alkane from ethane by joining one more carbon alom t0 form a three-carbon chain: 2) What is the name of this hydrocarbon? 3) Could a branched chain containing only three carbon atoms be formed?ca"H 'HPerspective drawingThree-dimensional modelLH
Build a model 0f an alkane from ethane by joining one more carbon alom t0 form a three-carbon chain: 2) What is the name of this hydrocarbon? 3) Could a branched chain containing only three carbon atoms be formed? ca"H 'H Perspective drawing Three-dimensional model LH...
##### 63 Evaluate Points] C(6 the 3) 8 expression_ DETAILS 3)AUFEXC4 12.2.024
6 3 Evaluate Points] C(6 the 3) 8 expression_ DETAILS 3) AUFEXC4 12.2.024...
##### Solve each equation.$$2 x+3=7$$
Solve each equation. $$2 x+3=7$$...


text:
LP decoding of expander codes: a simpler proof

# LP decoding of expander codes: a simpler proof

Michael Viderman
Computer Science Department
Technion — Israel Institute of Technology
Haifa 32000, Israel
viderman@cs.technion.ac.il
Research supported by an ERC-2007-StG grant number 202405.
###### Abstract

A code is a -expander code if it has a Tanner graph, where every variable node has degree , and every subset of variable nodes such that has at least neighbors.

Feldman et al. (IEEE IT, 2007) proved that LP decoding corrects errors of -expander code, where .

In this paper, we provide a simpler proof of their result and show that this result holds for every expansion parameter .

## 1 Introduction

The central algorithmic problem in coding theory is the explicit construction of error-correcting codes with best possible parameters together with fast encoding and decoding algorithms. Recently, this area has benefited enormously from insights and viewpoints originating in complexity theory, and numerous interconnections between codes and complexity theory have been discovered, which are surveyed for example in [9, 12]. The former survey [9] focuses on a notion called list-decoding and the second survey [12] focuses mainly on sub-linear algorithms for local testing and local decoding. Basically, there are two different kinds of noise models: adversarial and probabilistic. In this paper we consider an adversarial noise model where we only assume a bound on the number of errors and not how they are distributed. We refer a reader to the seminal paper of Richardson and Urbanke [7] for details concerning probabilistic noise model.

Surprisingly, all known constructions of asymptotically good error-correcting codes which can be decoded in linear time when a constant fraction of symbols is adversarially corrupted are based on expander codes. In particular, when the parity check graph of the low density parity check (LDPC) code has good expansion properties the associated code is called an expander code (see Definition 2). Expander codes and their decoding algorithms are often (implicitly) involved as basic building blocks in the constructions of asymptotically good codes which are linear-time decodable.

More formally, a linear code is a -expander code if it has a Tanner graph [11] , where every variable node has degree and every subset of variable nodes such that has at least neighbors.

The celebrated result of Sipser and Spielman [8] showed that regular expander codes with expansion parameter are decodable in linear time from errors. They achieved this by defining an extremely simple decoding algorithm, called Flip Algorithm. Feldman et al. [3] showed that the linear programming (LP) decoding (suggested in [4]) corrects errors in polynomial time if the underlying code is a -expander with expansion parameter . It is worth to notice that the running time of the LP decoder was strongly improved later (see e.g. [2, 10, 14]), although linear running time was not achieved. Then it was shown that similar result can be obtained using a different decoding algorithm [13], which in particular runs in linear time. Moreover, [13, Proposition D.1] points out that some regular expander codes with expansion parameter have minimum Hamming distance 2 and thus cannot correct even a single error. This leaves open the intriguing question: whether all regular expander codes with expansion parameter more than are polynomial time decodable from the constant fraction of errors.

While the decoding algorithm provided in [13] reaches better (proven) result than LP decoding in [3] with regards to regular expander codes, the LP decoder still looks much more powerful. Hence we might hope that the future of studying of LP decoding capabilities (see [1, 15, 16, 6, 5]) will resolve the above question.

The proof of the main result of Feldman et al. [3] was indirect and took the LP dual witness twice by using the min-cut max-flow theorem. We show a straightforward proof for the result of [3] which in particular holds for every expansion parameter . We think that our simplified proof sheds more light on the intuition lying behind the LP decoding of expander codes.

## 2 Preliminaries

Let be the binary field and be the set . In this work, we consider only linear codes. Let be a linear code over a field . For , let and . We define the distance between two words to be . The minimum distance of a code is defined by . The dual code is defined by . For we say that if for all we have .

Now we define expanders and expander codes. We start from the definition of expanders and then proceed to the definition of expander codes.

{definition}

[Expander Codes] Let be a linear code and let be its Tanner graph [11], where represents the variable nodes and represents the parity check nodes. Note that for every we have if and only if . For and it holds that if and only if . For and , let

• be the set of neighbors of ,

• be the set of neighbors of the node .

Let be constants. Then, is called a -expander if every vertex has degree and for all subsets such that we have .

We say that a code is a -expander code if it has a parity check graph that is a -expander.

## 3 Main Result

Feldman et al. [3] proved the following theorem.

{theorem}

[[3]] If is a -expander code, where and is an integer then is decodable from at most errors (in polynomial time) by LP decoding.

Their proof took the LP dual witness twice and in particular, they applied min-cut max-flow theorem to find such a witness. Feldman et al. [3] mentioned that it would be interesting to see a more direct proof of this result.

We reprove their result in the more straightforward manner and obtain a small improvement to the required expansion parameter, i.e., we assume only that .

{theorem}

[Main Theorem] If is a -expander code, where and is an integer then is decodable from at most errors (in polynomial time) by LP decoding.

In Section 4 we recall an implicit result (Theorem 4) that was shown in [3]. We shall use Theorem 4 in the proof of Theorem 3, which appears in Section 5.

## 4 Implicit result of Feldman et al. [3]

Let be a code and be its parity check graph. Assume that is an input word (a corrupted codeword) and is a set of error coordinates, i.e., if all bits in were flipped then would be the codeword of . We say that if and if .

{definition}

[Feasible weights] Let be the parity check graph of the code . A setting of edge weights is called feasible with respect to if

1. For all and distinct we have .

2. For all we have .

The following theorem was implicit in [3] and was argued in [3, Proposition 2] and by the discussions in [3, Sections 2 and 3].

{theorem}

[Implicit in [3]] If for all , there exists a feasible settings of weights then LP decoding for the code corrects errors. Moreover, if is an LDPC code then LP decoding runs in polynomial time.

The nice point here is that one can use Theorem 4 without any background on the LP decoding technique. We also note that this Theorem is related to the LDPC codes in general, not necessarily to the expander codes.

## 5 Proof of Theorem 3

We start the proof by defining the concept of matching (slightly different and simpler than in [3]).

{definition}

[-Matching] Let be a subset and let be an integer. With some abuse of notations we say that is a matching if for every we have at most one such that . Given a subset we say that is a -matching with respect to if

1. is a matching.

2. For every we have at least nodes such that .

For the rest of the proof, let be the set of error locations in the input word, and

 ^U=\seti∈[n]∖U | |N(i)∩N(U)|≥(2ϵ−1)c.

We let . The following proposition is similar to the corresponding proposition in [3], where an appropriate modification was made to fit our definition of matching (Definition 5).

{proposition}

Let and assume . If there exists an -matching with respect to then there is a feasible edge weight assignment (as in Definition 4).

###### Proof.

We assign weights as follows.

• For such that there is an and , set , and for all other set

• For all other , for all set .

Clearly, this weighting satisfies the first condition of a feasible weight assignment. For condition 2 we distinguish three cases. We recall that is an integer.

1. For we have . Also, at least edges that are incident to are in (and each has weight ). All other incident edges have weight or . So, the total weight of the incident edges to is at most . This is less than as long as .

2. If then . At least of ’s incident edges are in , but (trivially) not incident to . These edges have weight 0. The other incident edges have weight either 0 or . So, the total weight is at most which is smaller than as long as .

3. When then . We know that has less than neighbors in , i.e., at most neighbors in . All other edges have weight 0. I.e., the total weight is at most which is smaller than as long as .

Summarizing our conditions on , we have . There is such an if , i.e., . ∎

It is not hard to see that a sufficiently strong upper bound on implies an upper bound on .

{proposition}

Assume that . Then .

###### Proof.

Recall that .

We prove that . Assume the contrary and let such that (note that ).

We argue that which implies that with contradiction. Due to the fact that is a -expander code we have

 ϵc(|U|+|U′′|)≤|N(U∪U′′)|=|N(U)|+|N(U′′)∖N(U)|≤|U|⋅c+|U′′|⋅(c−(2ϵ−1)c).

Then we have and . Contradiction. ∎

We are ready to prove Theorem 3.

###### Proof of Theorem 3.

Let be a set of error locations. By assumption, and so, by Proposition 5 we have . By Corollary 5.1 (stated below) there exists an -matching with respect to . By Proposition 5 there exists a feasible edge weight assignment. Theorem 4 implies that the LP decoder succeeds and runs in polynomial time. ∎

### 5.1 Hall’s Theorem

Let us recall that is the bipartite graph with vertex sets and , and the edge set . We also recall Definition 5. We let to be a subset of .

{theorem}

[Hall’s Marriage Theorem] Assume that for every we have . Then there exists a -matching with respect to .

{corollary}

[Polygamous form of Hall’s Theorem] Let be an integer. Assume that for all we have . Then there exists -matching with respect to .

###### Proof.

Replace each with nodes connected to all nodes in . The corollary follows from the Hall’s theorem (Theorem 5.1). ∎

### Acknowledgements

We thank the anonymous referees for valuable comments on an earlier version of this paper.

## References

• [1] Sanjeev Arora, Constantinos Daskalakis, and David Steurer. Message passing algorithms and improved LP decoding. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 3–12. ACM, 2009.
• [2] David Burshtein. Iterative approximate linear programming decoding of LDPC codes with linear complexity. IEEE Transactions on Information Theory, 55(11):4835–4859, 2009.
• [3] Jon Feldman, Tal Malkin, Rocco A. Servedio, Clifford Stein, and Martin J. Wainwright. LP decoding corrects a constant fraction of errors. IEEE Transactions on Information Theory, 53(1):82–89, 2007.
• [4] Jon Feldman, Martin J. Wainwright, and David R. Karger. Using linear programming to decode binary linear codes. IEEE Transactions on Information Theory, 51(3):954–972, 2005.
• [5] Nissim Halabi and Guy Even. LP decoding of regular LDPC codes in memoryless channels. IEEE Transactions on Information Theory, 57(2):887–897, 2011.
• [6] Ralf Koetter and Pascal O. Vontobel. On the block error probability of LP decoding of LDPC codes, February 25 2006.
• [7] Thomas J. Richardson and Rüdiger L. Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2):599–618, 2001.
• [8] Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710–1722, 1996. Preliminary version appeared in FOCS 1994.
• [9] Madhu Sudan. List decoding: algorithms and applications. SIGACT News, 31(1):16–27, 2000.
• [10] Mohammad H. Taghavi, Amin Shokrollahi, and Paul H. Siegel. Efficient implementation of linear programming decoding. IEEE Transactions on Information Theory, 57(9):5960–5982, 2011.
• [11] Robert Michael Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533–547, 1981.
• [12] Luca Trevisan. Some applications of coding theory in computational complexity. In ECCC: Electronic Colloquium on Computational Complexity, technical reports, 2004.
• [13] Michael Viderman. Linear time decoding of regular expander codes. In Innovations in Theoretical Computer Science 2012 (ITCS 2012), Cambridge, MA, USA, January 8-10, 2012, pages 168–182. ACM, 2012.
• [14] Pascal O. Vontobel. Interior-point algorithms for linear-programming decoding. In Proceedings of the Information Theory and its Applications Workshop, UC San Diego, La Jolla, CA, USA, 2008.
• [15] Pascal O. Vontobel and Ralf Koetter. Bounds on the threshold of linear programming decoding, February 25 2006.
• [16] Pascal O. Vontobel and Ralf Koetter. Towards low-complexity linear-programming decoding, February 25 2006.
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:
# EEG Current Source Density and the Surface Laplacian

In some of our recent work , we use Surface Laplacians to estimate Current Source Density (CSD) from EEG data.

This transforms the data from a measure of electric potentials at the scalp to an estimate of underlying current sources and sinks: the Current Source Density (CSD). The Surface Laplacian can also be thought of as a spatial high-pass filter applied to the data, which attenuates low-spatial-frequency signals that are broadly distributed across the scalp, but preserves high-spatial-frequency signals that are more localised.

However, despite these great resources, I wasn't happy with my intuitions about how this works. In this post, I work through a toy example that helped me make sense of just why and how this method works.

Disclaimer: I've written this post mostly to help me understand something myself. I'm not the expert here, and it may all be horribly wrong. No warranties.

import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
import seaborn as sns
sns.set(rc={'figure.figsize':(8, 6)},
font_scale=1.5)
sns.set_style('whitegrid')

## The Surface Laplacian

To begin, let's pretend the world is two-dimensional, because it makes things simple.

• A Laplacian is basically a spatial second-order derivative.

• A derivative is a number that indicates how quickly something changes.

• A spatial derivative indicates how much something changes from place to place. If we measure elevation about sea level at two points 10 m apart and find the first is at +5 m while the second is at +15, the spatial derivative is the slope between the these two places. More formally, $\frac{\delta Elevation}{\delta Location}$ (change in elevation per change in location) = $\frac{10\ m}{10\ m} = 1$ meters per meter.

• A second derivative indicates how quickly the first derivate changes. Imagine a third point another 10 m further along that is 30 m above sea level. Remember, we're pretending everything is two-dimensional, so all these points are along a line. The slope between points 1 and 2 is $\frac{10\ m}{10\ m} = 1$. The slope between points 2 and 3 is $\frac{15\ m}{10\ m} = 1.5$. The difference in slopes is $0.5$.

Here's all of the above in plot form.

delta_loc = 10
locs = np.array([0, 10, 20])
heights = np.array([5, 15, 30])
diff_height = np.diff(heights)
diff_diff_height = np.diff(diff_height)

diff_locs = locs[:-1] + .5*delta_loc   # Keep the x-axis properly aligned
diff_diff_locs = locs[:-2] + 1*delta_loc

plt.plot(locs, heights, '-o', label='Elevation (m)')
plt.plot(diff_locs, diff_height, '-o', label=u'Slope (δ Elevation)')
plt.plot(diff_diff_locs, diff_diff_height, '-o', label=u'δ Slope')
plt.hlines(0, *plt.xlim(), linestyle='dashed')
plt.xlabel('Location (m)')
plt.legend()
plt.show()

## EEG Laplacians

So why does calculating the second spatial derivative of the EEG signal help us? To see, I simulate some one-dimensional data (pretend we only have electrodes on the midline) illustrating a common issue in EEG: our data contains a small, narrow negative component and a large, broad positive one.

electrode_spacing = .1
space = np.arange(0, 10, electrode_spacing)
comp1 = 2 * stats.norm.pdf(space, loc=4, scale=1)
comp2 = -.25 * stats.norm.pdf(space, loc=5, scale=.5)

def do_label():
plt.legend(loc='upper right')
plt.xlabel('Location')
plt.ylabel('')

fig_ground_truth = plt.figure()
for comp, label in zip([comp1, comp2], ['Positive', 'Negative']):
plt.plot(space, comp, label=label)
do_label()

Of course, in our recordings both of these components are superimposed, and the little one is obscured by the big one. Poor little component.

eeg_signal = comp1 + comp2
plt.plot(space, eeg_signal, label='EEG Signal')
do_label()

Where did our negative component go? It's still there, as a wiggle on the right hand side of the positive component, but good luck detecting this in noisy data. Yes, I did tweak these parameters to make the effect particularly dramatic.

Next, we take the first spatial derivative of the EEG signal: how much it changes between electrodes. This doesn't tell us much by itself.

first_derivative = np.diff(eeg_signal)
space_d1 = space[:-1] + .5 * electrode_spacing # Keep locations lined up with differenced data
plt.plot(space_d1, first_derivative, label='First spatial derivative')
do_label()

Next, we take the second spatial derivative: the derivative of the derivative.

second_derivative = np.diff(first_derivative)
space_d2 = space[:-2] + .5 * electrode_spacing
plt.plot(space_d2, second_derivative, label='Second spatial derivative')
do_label()

…and multiply it by $-1$.

plt.plot(space_d2, -1*second_derivative, label='-1 × Second spatial derivative')
do_label()

There it is! Our positive component is narrower, but still has it's peak at $x=4$. Our negative component can now be seen at $x=5$

For comparison, here are the original components again.

fig_ground_truth

By calculating the Laplacian, we've squeezed the components into a narrower spatial range, which make it possible to see the otherwise hidden negative component. It looks like we've also introduced some other artifacts, like the negative dip at around $x=2$. However, this makes sense from an electrophysiological point of view: if there is a positive current source at $x=4$, there must be corresponding negative sinks around it. (I might be confusing sinks and sources here, but no matter).

## 2D Laplacians

OK, this works with one-dimensional data, but EEG electrodes are located in three-dimensional space around the head. Let's at least see how it works in the two-dimensional case. We'll pretend the scalp is a flat square of 20 cm on each side.

X = Y = np.arange(-10, 10.01, .1)
XY = np.array([(x, y) for x in X for y in Y])

def show(X):
'''Plot an image from a 2D array'''
mx = np.abs(X).max()
im = plt.imshow(X, cmap='seismic', vmin=-mx, vmax=mx)
plt.colorbar(im)

locs = [(0, -4), (0, 2)]  # Center of each component
peaks = [-1, 6]           # Peak amplitudes
scales = [2, 8]           # Standard deviations
V = np.zeros(XY.shape[0]) # Voltages

for loc, peak, scale in zip(locs, peaks, scales):
cov = np.eye(2) * scale
thisV = stats.multivariate_normal.pdf(XY, mean=loc, cov=cov)
gain = peak / thisV.max()
V += thisV * gain
wV = V.reshape(len(X), len(X)).T # Voltage as a 2D grid
show(wV)

Again, where did that little guy go?

As before, we can look at the first derivatives, but again they don't tell us much.

def combine(dx, dy):
'''Combine two one-dimensional partial derivates to form a Laplacian
Drops the last value in each dimension so the shapes match.
Is this the right thing to do?
Wikipedia (https://en.wikipedia.org/wiki/Laplace_operator#Definition)
says "the Laplacian of f is the sum of all the unmixed second partial
derivatives in the Cartesian coordinates xi." I think this means yes.
'''
n = dx.shape[0]
assert(dy.shape[1]==n)
return dx[:n, :n] + dy[:n, :n]

dv_dx = np.diff(wV, axis=0)[:-1, :] # Drop the last value on the appropriate axis to keep things symmetrical
dv_dy = np.diff(wV, axis=1)[:, :-1]

The negative second derivatives - the Laplacian - on the other hand…

ddv_ddx = np.diff(dv_dx, axis=0)[:-1, :]
ddv_ddy = np.diff(dv_dy, axis=1)[:, :-1]
laplacian = -combine(ddv_ddx, ddv_ddy)
show(laplacian)

There it is!

This is the same effect as we saw in 1D space done in 2D. As mentioned above, real EEG electrodes are located in 3D space, and they aren't evenly spaced, which is why you can't calculate the Laplacian by looking at the difference between adjacent electrodes. Instead, you need to use something complicated called spherical spline interpolation, but I'm not going into that here.

I now get why calculating the second spatial derivative of an EEG signal is sensible thing to do. Hopefully you do too!


text:
# Wire Resistance

R = \rho*L/A
Wire resistance calculator from resistivity and wire dimensions.
Enter 'x' in the field to be calculated.

This tool is a calculator of the resistance of an electric wire. It uses the relation between the wire resistance and the wire dimensions and material (resistivity). The formula is as follows,

R = \rho*L/A

R: resistance in ohm
\rho: resistivity in ohm-meter
L: length in meter
A: cross-sectional area of the wire in meter square


text:
# Factorial

## Factorial

For any positive integer n, a number that is the product of all the positive integers less than or equal to n.

• In set theory, the factorial n is defined as being the number of permutations of a set of n elements.
• We say that “n!” is a function of the set of whole numbers in itself, defined like this: ∀ $$n\in \mathbb{N}\space\vert\ n! = 1 \times 2 \times 3 \times \ldots \times n$$.
• By convention, 0! = 1, because there is only one permutation of a set that contains 0 elements.

### Symbol

• The expression “5 factorial” is noted as “5!”.
• The symbol is “!” which can be associated with the exclamation point.

### Examples

• 5! = 5 × 4 × 3 × 2 × 1 =  120
• 4! = 4 × 3 × 2 × 1 =  24

### Historical Note

The French mathematician Christian Kramp (1760-1826) introduced factorial notation in his book Éléments d’Arithmétique Universelle, published in 1808.


text:
# AMR refinement criteria¶

Several parameters controlling refinement can be set in the setrun function. See Specifying AMRClaw run-time parameters in setrun.py for further description of these. Many of the parameters discussed below are attributes of rundata.amrdata in setrun.py.

Every regrid_interval time steps on each level, the error is estimated in all cells on grids at this level. Cells where some refinement criteria are satisfied are flagged for refinement. Default options for flagging are described below. Additional cells surrounding the flagged cells are also flagged to insure that moving features of the solution (e.g. shock waves) do not escape from the region of refinement before the next regridding time. The number of buffer cells flagged is specified by regrid_buffer_width and the number of steps between regridding on each level is specified by regrid_interval. Typically these are equal (assuming the Courant number is close to 1) and taken to be some small integer such as 2 or 3.

In addition to flagging individual cells based on the behavior of the solution, it is also possible to specify that certain regions of the domain should always be refined to a certain level (and/or never refined above some level). This is described further in Specifying AMR regions. These regions are used in conjunction with the methods described below to determine whether or not a given cell should be flagged for refinement.

The cells that have been flagged are then clustered into rectangular regions to form grids at the next finer level. The clustering is done in light of the tradeoffs between a few large grids (which usually means refinement of many additional cells that were not flagged) or many small grids (which typically results in fewer fine grid cells but more grids and hence more overhead and less efficient looping over shorter rows of cells). The parameter clustering_cutoff in amrNez.data is used to control this tradeoff. At least this fraction of the fine grid cells should result from coarse cells that were flagged as needing refinement. The value clustering_cutoff = 0.7 is usually reasonable.

## Flagging criteria¶

Two possible approaches to flagging individual cells for refinement (based on the behavior of the solution) are built into AMRClaw. (A different default approach is used in GeoClaw, see Flagging criteria in GeoClaw).

Note: Starting in v5.6.0, a new approach is also available, see Guiding AMR with adjoint flagging.

One approach to flagging cells for refinement (the default used in most examples) is to set flag2refine == True and specify a tolerance flag2refine_tol. This indicates that the library subroutine $CLAW/amrclaw/src/Nd/flag2refine.f90 should be used to flag cells for refinement. This routine computes the maximum max-norm of the undivided difference of $$q_{i,j}$$ based its four neighbors in two space dimensions (or 6 neighbors in 3d). If this is greater than the specified tolerance, then the cell is flagged for refinement (subject to limitations imposed by “regions”). The undivided difference (not divided by the mesh width) is used, e.g. $$|q(m,i+1,j) - q(m,i-1,j)|$$ for each component $$m$$. Note that the user can change the criterion used for flagging cells by modifying this routine – best done by copying the library routine to your application directory and modifying the Makefile to point to the modified version. ### Richardson extrapolation¶ The second approach to flagging individual cells is based on using Richardson extrapolation to estimate the error in each cell. This is used if flag_richardson == True. In this case a cell is flagged if the error estimate exceeds the value flag_richardson_tol. Richardson estimation requires taking two time steps on the current grid and comparing the result with what’s obtained by taking one step on a coarsened grid. One time step on the fine grid is re-used, so only one additional time step on the fine grid and one on a coarsened grid are required. It is somewhat more expensive than the flag2refine approach, but may be more useful for cases where the solution is smooth and undivided differences do not identify the regions of greatest error. Note: Both approaches can be used together: if flag2refine == True and flag_richardson == True then a cell will be flagged if either of the corresponding specified tolerances is exceeded. ## Specifying AMR regions¶ In addition to specifying a tolerance or other criteria for flagging individual cells as described above, it is possible to specify regions of the domain so that all points in the region, over some time interval also specified, will be refined to at least some level minlevel and at most some level maxlevel. These are specified through the parameter rundata.regiondata.regions in setrun.py. This is a list of lists, each of which specifies a region. A new region can be added via: rundata.regiondata.regions.append([minlevel,maxlevel,t1,t2,x1,x2,y1,y2])  This indicates that over the time period from t1 to t2, cells in the rectangle x1 <= x <= x2 and y1 <= y <= y2 should be refined to at least minlevel and at most maxlevel. To determine whether a grid cell lies in one of the regions specified, the center of the grid cell is used. If a mapped grid is being used, the limits for the regions should be in terms of the computational grid coordinates, not the physical coordinates. If a cell center lies in more than one specified region, then the cell will definitely be flagged for refinement at level L (meaning it should be covered by a Level L+1 grid) if L+1 <= minlevel for any of the regions, regardless of whether the general flagging criteria hold or not. This means the smallest of the various minlevel parameters for any region covering this point will take effect. Conversely it will not be flagged for refinement if L+1 > maxlevel for all regions that cover this point. This means the largest of the various maxlevel parameters for any region covering this point will take effect. (However, note that since flagged cells are buffered as described above by flagging some adjacent cells, a cell may still end up flagged for refinement even if the above tests say it should not be.) For example, suppose that amr_levels_max = 6 has been specified along with these two regions: rundata.regiondata.regions.append([2, 5, 10.0, 30.0, 0.0, 0.5, 0.0, 0.5]) rundata.regiondata.regions.append([3, 4, 20.0, 40.0, 0.2, 1.0, 0.2, 1.0])  The first region specifies that from time 10 to 30 there should be at least 2 levels and at most 5 levels of refinement for points in the spatial domain 0 < x < 0.5 and 0 < y < 0.5. The second region specifies that from time 20 to 40 there should be at least 3 level and at most 4 levels of refinement for points in the spatial domain 0.2 < x < 1.0 and 0.2 < y < 1.0. Note that these regions overlap in both space and time, and in regions of overlap the maximum of the minlevel and also the maximum of the maxlevel parameters applies. So in the above example, from time 20 to 30 there will be at least 3 levels and at most 5 levels in the region of overlap, 0.2 < x < 0.5 and 0.2 < y < 0.5. Within these regions, how many levels are chosen at each point will be determined by the error flagging criteria, i.e. by the default or user-supplied routine flag2refine, or as determined by Richardson extrapolation, as described above. Points that are not covered by either region are not constrained by the regions at all. With amr_levels_max = 6 then they might be refined to any level from 1 to 6 depending on the error flagging criteria. ## Implementation¶ It is perhaps easiest to understand how this works by summarizing the implementation. Note the order in which different flagging criteria are checked was modified in Version 5.5.0 in order to avoid the more expensive options for grid cells that are either forbidden from being refined or forced to be refined based on regions they lie in. The regridding algorithm from level L to L+1 loops over all grid patches (in parallel when OpenMP is used with more than one thread). The cells on each patch are initially marked with amrflags(i,j) = UNSET, a special value (set in amr_module.f90). In flagging based on regions: • If the current level is less than the maximum of all minlevel values for regions that contain the cell, then it is marked with amrflags(i,j) = DOFLAG. • If the current level is greater than or equal to the maximum of all maxlevel values for regions that contain the cell, then it is marked with amrflags(i,j) = DONTFLAG. If there are any cells in the patch that are still marked as UNSET after checking all the regions, then if the setrun parameter flag2refine is True, then the routine flag2refine is called. The user may wish to create their own version of this routine. The default library version was modified with the addition of the adjoint option in Version 5.6.0 (see Guiding AMR with adjoint flagging), and does one of two things: • If adjoint_flagging then it checks the inner product of the forward solution with all adjoints over the specified time period and if the magnitude is greater than tolsp the cell is marked DOFLAG. • Otherwise, the undivided difference of all components of q in each coordinate direction is computed, e.g. abs(q(:,i+1,j) - q(:,i-1,j)) and abs(q(:,i,j+1) - q(:,i,j-1)) in 2d, and if the maximum of these is greater than tolsp the cell is marked DOFLAG. If there are still any cells in the patch that are still marked as UNSET, then if the setrun parameter flag_richardson is True, then the routine errest is called. This does flagging based on estimates of the one-step error produced by Richardson extrapolation using the solution on the current grid and on a coarsened grid. If adjoint_flagging then these estimates are applied to the inner product of the error estimate with the adjoint solutions over the relevant time period. In either case, the setrun parameter flag_richardson_tol is used as the tolerance. ## Flagging criteria in GeoClaw¶ In GeoClaw, a special flag2refine subroutine is defined. A standard approach for modeling tsunamis propagating across the ocean is to refine anywhere that the surface elevation of the ocean $$\eta = h+B$$ is greater in absolute value than some specified wave_tolerance, e.g. 0.1 meter as set, for example, in the setrun.py file of$CLAW/geoclaw/examples/tsunami/chile2010. This wave_tolerance parameter can be set for any GeoClaw application.

Often this ends up refining the entire ocean when in fact only some waves are of interest. In this case one can use regions as described in Specifying AMR regions to limit refinement to certain space-time regions.

Alternatively, starting in Version 5.6.0 one can use adjoint flagging (see Guiding AMR with adjoint flagging) to better select the waves that will reach a particular location over a specified time range, including those that might reflect off distant shores.

Generally one must also use regions to allow (or force) much higher levels of refinement over small regions along the coast if one is doing detailed inundation modeling of a particular community.


text:
By Murray Bourne, 17 Aug 2006

This was not made very obvious when I installed IE7:

OS Updates--Do not reinstall any version of Microsoft Windows in any way after you install Internet Explorer 7. Do not upgrade in place or upgrade to a new edition. The workaround is to remove Internet Explorer 7 Beta, install operating system updates, and then reinstall Internet Explorer.

(Found at IE7's Release Notes.)

Hmm - of course, several updates have automatically installed themselves since then. So should I expect a blue screen of death sometime soon...?

1. Vinod says:

I've got a copy of Ubuntu Linux with your name on it!

2. Murray says:

Thanks, Vinod. Bring on open source... ^_^

### Comment Preview

HTML: You can use simple tags like <b>, <a href="...">, etc.

To enter math, you can can either:

1. Use simple calculator-like input in the following format (surround your math in backticks, or qq on tablet or phone):
a^2 = sqrt(b^2 + c^2)
(See more on ASCIIMath syntax); or
2. Use simple LaTeX in the following format. Surround your math with $$ and $$.
$$\int g dx = \sqrt{\frac{a}{b}}$$
(This is standard simple LaTeX.)

NOTE: You can't mix both types of math entry in your comment.


text:
## 王照陆博客

If an egg is broken by outside force, life ends. But if broken by inside force, life begins!!

# Thinking in States

## Thinking in States

Niclas Nilsson
PEOPLE IN THE REAL WORLD HAVE A WEIRD RELATIONSHIP WITH STATE.
This morning, I stopped by the local store to prepare for another day of con- verting caffeine to code. Since my favorite way of doing that is by drinking lattes, and I couldn’t find any milk, I asked the clerk.
“Sorry, we’re super-duper, mega–out of milk.”
To a programmer, that’s an odd statement. You’re either out of milk, or you’re not. There is no scale when it comes to being out of milk. Perhaps she was try- ing to tell me that they’d be out of milk for a week, but the outcome was the same—espresso day for me.
In most real-world situations, people’s relaxed attitude toward state is not an issue. Unfortunately, however, many programmers are quite vague about state, too—and that is a problem.
Consider a simple webshop that only accepts credit cards and does not invoice customers, with an Order class containing this method:
public boolean isComplete() {
return isPaid() && hasShipped();
}
Reasonable, right? Well, even if the expression is nicely extracted into a method instead of copy ’n’ pasted everywhere, the expression shouldn’t exist at all. The fact that it does highlights a problem. Why? Because an order can’t be shipped before it’s paid. Thereby, hasShipped can’t be true unless isPaid is true, which makes part of the expression redundant. You may still want isComplete for clarity in the code, but then it should look like this:

    public boolean isComplete() {
return hasShipped();
}

￼￼168
97 Things Every Programmer Should Know

￼￼￼￼￼￼￼￼￼￼￼￼￼￼￼In my work, I see both missing checks and redundant checks all the time. This example is tiny, but when you add cancellation and repayment, it’ll become more complex, and the need for good state handling increases. In this case, an order can only be in one of three distinct states:
• In progress: Can add or remove items. Can’t ship.
• Paid: Can’t add or remove items. Can be shipped.
• Shipped: Done. No more changes accepted.
These states are important, and you need to check that you’re in the expected state before doing operations, and that you only move to a legal state from where you are. In short, you have to protect your objects carefully, in the right places.
But how do you begin thinking in states? Extracting expressions to meaningful methods is a very good start, but it is just a start. The foundation is to under- stand state machines. I know you may have bad memories from CS class, but leave them behind. State machines are not particularly hard. Visualize them to make them simple to understand and easy to talk about. Test-drive your code to unravel valid and invalid states and transitions and to keep them correct. Study the State pattern. When you feel comfortable, read up on Design by Contract. It helps you ensure a valid state by validating incoming data and the object itself on entry and exit of each public method.
If your state is incorrect, there’s a bug, and you risk trashing data if you don’t abort. If you find the state checks to be noise, learn how to use a tool, code generation, weaving, or aspects to hide them. Regardless of which approach you pick, thinking in states will make your code simpler and more robust.

#### QML之states

2010-12-09 02:49:00

#### 802. Find Eventual Safe States

2018-03-18 11:57:25

#### Thinking In Java 第四版(英文版)

2015年11月25日 71B 下载

#### C#项目中的一些问题

2014-04-21 10:09:33

#### 云计算之路-阿里云上：对“黑色n秒”问题的最终猜想——CPU C-states引起的

2014-05-24 09:01:47

#### Thinking in Java (Java 编程思想)

2017-04-30 15:16:02

#### CPU的C-States /Cpu的各种状态

2016-09-14 11:00:45

#### qml的states属性

2016-01-28 16:51:52

#### Thinking in Java 4th Edition 原版全套

2009年04月05日 5.76MB 下载

#### Thinking in C++ 中文版

2009年02月27日 13.82MB 下载


text:
UTD20s13

#### Start

2020-07-11 09:00 AKDT

## UTD20s13

#### End

2020-07-11 12:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -77 days 23:31:09

3:00:00

0:00:00

# Problem CTrimming Convex Polygons

You are the proud owner of a beautiful convex polygon! But university is expensive, so you decide to sell your polygon to support your studies. The market value, in dollars, for a polygon is exactly twice its area. But there is an illegal black market for individual vertices.

In this problem, you are given a convex polygon with vertices $P$. Each vertex $p_ i \in P$ has a value $v_ i$. You can form a new polygon using a subset of points $Q \subseteq P$. You can then legally sell the polygon formed by vertices $Q$ and also sell the points $P-Q$ on the black market. The amount of money you would earn this way is $2 \cdot {\rm area}(Q) + \sum _{p_ i \in P-Q} v_ i$ where ${\rm area}(Q)$ is the area of the unique convex polygon having vertices $Q$.

You are guaranteed no three vertices of $P$ are collinear, and you also have ${\rm area}(Q) = 0$ for each set $Q$ with at most two points. Note that it is valid for the polygon from $Q$ to be degenerate (i.e. have an area of $0$).

## Input

The first line of input consists of a single integer $3 \leq n \leq 200$ indicating the number of points on your convex polygon.

Then $n$ lines follow. The $i$’th such line contains three integers $x_ i, y_ i, v_ i$ describing the coordinates $(x_ i, y_ i)$ and value $v_ i$ of the $i$’ vertex on the polygon. You are guaranteed $|x_ i|, |y_ i| \leq 10^6$ and $0\leq v_ i\leq 10^9$.

The points are given in counterclockwise order around $P$. You are guaranteed no three points are collinear, and the polygon $P$ is convex.

## Output

A single line with a single integer indicating the maximum amount of money that can be obtained by selling a subset of $P$ on the black market and legally selling the polygon defined by the remaining points.

Sample Input 1 Sample Output 1
4
0 0 1
4 0 3
6 6 100
0 5 4

120

Sample Input 2 Sample Output 2
3
0 0 5
1 0 6
0 1 7

18


text:
# Mass and Dimensions

• January 17th 2013, 09:57 PM
dempsey1905
Mass and Dimensions
Hello All...

This is my first posting so I am not sure if this is the right section.

I am having a hard time figuring out how to do this problem:

Question: Determine the mass of a tombstone made of the same material as the granite rock and having the dimensions of 260 cm by 90 by 40 cm. What is the mass of the tombstone?

..

I have not been given the mass of the granite rock yet, but once I do how would I set up this problem?
• January 18th 2013, 02:14 AM
earboth
Re: Mass and Dimensions
Quote:

Originally Posted by dempsey1905
Hello All...

This is my first posting so I am not sure if this is the right section.

I am having a hard time figuring out how to do this problem:

Question: Determine the mass of a tombstone made of the same material as the granite rock and having the dimensions of 260 cm by 90 by 40 cm. What is the mass of the tombstone?

..

I have not been given the mass of the granite rock yet, but once I do how would I set up this problem?

1. Use the definition of density of a material:

$density = \frac{mass}{volume}$ ....... Then $mass = density \cdot volume$

2. Have a look here: Granite - Wikipedia, the free encyclopedia

In this text about the various forms of granite you'll find: "The average density of granite is between 2.65 and 2.75 g/cm3, ...."

If I were you I would take $d_{granite} = 2.7\ \tfrac{g}{cm^3}$

3. Since you now know the mass of 1 cm³ of granite you only have to determine the volume of the tombstone. Go ahead!
• January 18th 2013, 06:35 AM
dempsey1905
Re: Mass and Dimensions
Thank you!


text:
# Maximum but still limited magnitude region is not plotted with ContourPlot [closed]

The function is well defined in the whole region. But it just skips plotting the center region. I've tried PlotPoints, Mesh, Contours - it didn't help.

After making more contours. White hole is still there.

After zooming in the region suddenly reveals data.

How can I make it to plot central part in detail when zoomed out? Thank you in advance.

UPD: Yes, thanks, that's PlotRange :)

-

## closed as off-topic by Ajasja, Artes, Mr.Wizard♦Jan 21 at 1:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question arises due to a simple mistake such as a trivial syntax error, incorrect capitalization, spelling mistake, or other typographical error and is unlikely to help any future visitors, or else it is easily found in the documentation." – Ajasja, Artes, Mr.Wizard
If this question can be reworded to fit the rules in the help center, please edit the question.

PlotRange -> All? –  ybeltukov Jan 20 at 2:06

Just add PlotRange -> All
ContourPlot[Exp[-x^2 - y^2], {x, -3, 3}, {y, -3, 3}]

ContourPlot[Exp[-x^2 - y^2], {x, -3, 3}, {y, -3, 3}, PlotRange -> All]