text:
Consider a rooted tree $$T=(V,E)$$ with leaf set $$\mathcal L\subseteq V$$ and positive vertex weights $$w : V\setminus \mathcal L\to \mathbb R_+$$ that are non-increasing along root-leaf paths. We recall the ultrametric $$d_w$$ defined on $$\mathcal L$$ by

$$d_w(\ell,\ell') \mathrel{\vcenter{:}}= w(\mathrm{lca}(\ell,\ell')).$$

Say that $$(\mathcal L,d_w)$$ is a $$\tau$$-HST metric for some $$\tau \geq 1$$ if $$\mathcal L$$ is the leaf set of some weighted tree $$T=(V,E)$$, and $$d_w$$ is the ultrametric corresponding to a weight $$w$$ on $$T$$ with the property that $$w(y) \leq w(x)/\tau$$ whenever $$y$$ is a child of $$x$$. (So for a finite metric space, the notions of $$1$$-HST metric and ultrametic are equivalent.) Say that $$(\mathcal L,d)$$ is a strict $$\tau$$-HST metric if we require the stronger property that $$w(y)=w(x)/\tau$$ whenever $$x,y \in V$$ are internal nodes and $$y$$ is a child of $$x$$.

Two metrics $$d$$ and $$d'$$ on a set $$X$$ are $$K$$-equivalent if there is a constant $$c > 0$$ such that $d(x,y) \leq c\, d'(x,y) \leq K d(x,y)\qquad \forall x,y \in X\,.$ We leave the following statements as an exercise: For every $$\tau > 1$$, every $$1$$-HST is $$\tau$$-equivalent to some strict $$\tau$$-HST.

There is a constant $$C \geq 1$$ such that if $$(\mathcal L,d_w)$$ is a $$C (\log n)^2$$-HST metric, where $$n=|\mathcal L|$$, then the competitive ratio for MTS on $$(\mathcal L,d_w)$$ is $$\Omega\left(\log n\right)$$.

While the preceding theorem applies only to $\tau$-HSTs with $\tau$ sufficiently large, the next lemma shows how we can improve the separation parameter by passing to a subset of leaves.

If $$(\mathcal L,d)$$ is a strict $$2$$-HST, then for every $$k \in \mathbb N$$, there is a subset $$\mathcal L' \subseteq \mathcal L$$ with

$$|\mathcal{L}'| \geq |\mathcal{L}|^{1/k},$$

and such that $$(\mathcal L', d)$$ is a $$2^k$$-HST metric.

Combining this with Theorem 1 yields:

If $$(\mathcal L,d)$$ is a $$1$$-HST metric with $$n=|\mathcal L|$$, then the competitive ratio for MTS on $$(\mathcal L,d)$$ is at least $$\Omega\left(\frac{\log n}{\log \log n}\right)$$.

Recall that the Metric Ramsey theorem from the preceding lecture implies that every $$n$$-point metric space contains a subset of size $$\sqrt{n}$$ that is $$O(1)$$-equivalent to a $$1$$-HST. This yields:

For every $$n$$-point metric space, the competitive ratio for MTS is at least $$\Omega(\log n/\log \log n)$$.

We will not prove Theorem 1, but we will prove a lower bound for two special cases that together capture the essential elements of the full argument. The general case is discussed at the end.

## The complete d-ary tree

The first case we’ll consider is when $$T$$ is a $$d$$-ary tree of height $$h$$, so that $$|\mathcal L|=d^h$$. Define $$w(x)=\tau^{-\mathrm{dist}_T(x,r)}$$, where $$r$$ is the root of $$T$$ and $$\mathrm{dist}_T$$ denotes the combinatorial distance on $$T$$. Then $$(\mathcal L,d_w)$$ is a $$\tau$$-HST.

Our goal is to establish a lower bound of $$\Omega(h \log d)$$ on the competitive ratio for MTS when $$\tau$$ is sufficiently large. Note that when $$\tau = \Theta(1)$$ and $$d=2$$, it is an open problem to exhibit an $$\Omega(h)$$ lower bound, and proving such a bound is likely the most difficult obstacle in obtaining an $$\Omega(\log n)$$ lower bound for every $$n$$-point ultrametric.

Our costs functions will be of the form $$\{\epsilon\cdot c_\ell : \ell \in \mathcal L\}$$, where $$\epsilon> 0$$ is a number, and $c_\ell(\ell') = \begin{cases} 0 & \ell=\ell' \\ 1 & \ell \neq \ell'\,. \end{cases}$ More succinctly: $$c_\ell \mathrel{\vcenter{:}}= \mathbf{1}-\mathbf{1}_\ell$$.

Let $$\alpha_h$$ be the competitive ratio for height $$h$$. We will prove inductively that $$\alpha_h \geq \Omega(h \log d)$$.

Consider first the case $$h=1$$. We define the height-$$1$$ cost sequence. The root $$r$$ has $$d$$ leaves beneath it. We do the following $$d \log d$$ times: Choose a random leaf $$\ell$$ and play the cost function $$c_\ell$$. It is straightforward that if $$\mathrm{alg}_1$$ denotes the cost of an online algorithm, then: $\mathbb{E}[\mathrm{alg}_1] \geq \log d\,.$ (Note that if a cost comes at $$\ell$$, then the algorithm must either move and pay movement cost $$1$$, or stay in place and pay service cost $$1$$.)

Consider the following offline algorithm: Move to the leaf that will be chosen the smallest number of times, and stay there. The movement cost if $$1$$, and a standard coupon collecting argument shows that the service cost is $$O(1)$$, hence: $\mathbb{E}[\mathrm{opt}_1] \leq O(1)\,.$ We conclude that the competitive ratio satisfies $\alpha_1 \geq c \log d$ for some $$c > 0$$.

Consider now the case of $$h \geq 2$$. We define the height-$$h$$ cost sequence. The root has beneath it $$d$$ subtrees $$T_1, T_2, \ldots, T_d$$ of height $$h-1$$. For some number $$\mu_h$$ to be chosen shortly, we do the following $$\mu_h d$$ times: Choose $$i \in \{1,2,\ldots,d\}$$ uniformly at random and play in $$T_i$$ the height-$$(h-1)$$ cost sequence scaled by $$1/\tau$$.

Consider first what an online algorithm can do. If the algorithm’s state lies in $$T_i$$ when a height-$$(h-1)$$ cost sequence is imposed on $$T_i$$, it can either leave $$T_i$$ at some point during the sequence, or it can remain in $$T_i$$. Hence the algorithm pays at least $\min\left(1,\tau^{-1} \mathbb{E}[\mathrm{alg}_{h-1}]\right)$. It follows that:

$\mathbb{E}[\mathrm{alg}_h] \geq \mu_h \min\left(1,\tau^{-1} \mathbb{E}[\mathrm{alg}_{h-1}]\right) \geq \mu_h \min\left(1,\tau^{-1} \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]\right)\,.$

Thus if

$$\label{eq:tauchoice} \tau \geq \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]$$

it holds that $$\label{eq:alg} \mathbb{E}[\mathrm{alg}_h] \geq \mu_h \tau^{-1} \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]\,.$$ We will choose $$\tau$$ so that \eqref{eq:tauchoice} holds.

Let us now analyze an offline algorithm. Let $$\rho_i$$ denote the number of times that $$T_i$$ is chosen. The offline algorithm first moves to some $$T_i$$ with $$\rho_i$$ minimal, and then plays optimally against level-$$(h-1)$$ cost sequences arriving in $$T_i$$.

If $$\mu_h \geq \Omega(\log d)$$, then the normal approximation to a binomial distribution shows that there is a constant $$0 < c' < 1$$ such that $\mathbb{E}\left[\min(\rho_1,\ldots,\rho_d)\right] \leq \mu_h - c'\sqrt{\mu_h \log d}\,.$ Hence incorporating the movement cost yields: $\mathbb{E}[\mathrm{opt}_h] \leq 1 + \left(\mu_h - c'\sqrt{\mu_h \log d}\right) \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}]\,.$

We now choose $$\mu_h$$ so that $c' \sqrt{\mu_h \log d} \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}] = 2\,,$ i.e., $\mu_h \mathrel{\vcenter{:}}= \frac{4}{\log d} \left(\frac\tau{c' \mathbb{E}[\mathrm{opt}_{h-1}]}\right)^2$ Note from \eqref{eq:tauchoice}, we have $$\label{eq:muh} \mu_h \geq \frac{4}{(c')^2\log d} \alpha_{h-1}^2.$$ Since $$\alpha_{h-1} \geq \alpha_1 \geq \Omega(\log d)$$ it follows that $$\mu_h \geq \log d$$ for $$c'$$ chosen small enough. (In particular, the normal approximation applies.)

Our choice of $$\mu_h$$ ensures that \begin{align} \mathbb{E}[\mathrm{opt}_h] &\leq \left(\mu_h-\frac{c'}{2} \sqrt{\mu_h \log d}\right) \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}] \label{eq:opt}\end{align} Combining this with \eqref{eq:alg} yields

$$\alpha_h \geq \frac{\mathbb{E}[\mathrm{alg}_h]}{\mathbb{E}[\mathrm{opt}_h]} \geq \frac{\alpha_{h-1}}{1-\frac{c'}{2} \sqrt{\frac{\log d}{\mu_h}}} \geq \alpha_{h-1} \left(1+\frac{c'}{2} \sqrt{\frac{\log d}{\mu_h}}\right),$$

where the latter inequality holds because $$c' < 1$$ and $$\mu_h \geq \log d$$. Using \eqref{eq:muh}, this gives $\alpha_h \geq \alpha_{h-1} + \frac{c'}{2} \log d\,,$ completing the argument.

Note that in \eqref{eq:tauchoice}, we required $$\tau \geq \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]$$. So let us use \eqref{eq:opt} to compute: $\mathbb{E}[\mathrm{opt}_h] \leq \mu_h \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}] \leq \frac{O(1)}{\log d} \frac\tau{\mathbb{E}[\mathrm{opt}_{h-1}]}$ Since $\mathbb{E}[\mathrm{opt}_h] \cdot \mathbb{E}[\mathrm{opt}_{h-1}] \leq O(\tau/\log d)\,,$ and $$\mathbb{E}[\mathrm{opt}_h] \geq \mathbb{E}[\mathrm{opt}_{h-1}] \geq 1$$ for all $$h$$, it follows that $$\mathbb{E}[\mathrm{opt}_h] \leq O(\sqrt{\tau/\log d})$$, meaning that $$\tau \geq \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]$$ will be satisfied for $$\tau \geq C(\alpha_{h-1}/\log d)^2 \asymp h^2$$. Since $$h \asymp \frac{\log n}{\log d}$$, this yields completes the proof of in the special case of a $$d$$-regular HST.

## The “superincreasing” metric

We will now consider a highly unbalanced family of HSTs. These were analyzed in a paper of Karloff, Rabani, and Ravid.

Let us define the trees $$\{T_n\}$$ as follows: The root $$r_{n}$$ of $$T_n$$ has two children. The left child is a copy of $$T_{n-1}$$ of rooted at $$r_{n-1}$$, and the right child is a single leaf. We denote $$w_n(r_n)=1$$, and $$w_n(r_{n-1}) = 1/\tau_n$$, where $$\tau_n > \tau_{n-1} > \cdots > 0$$ is a sequence of positive weights we will choose soon, and such that $$\tau_n \leq O(\log n)$$.

The basic structure of our argument will be similar to the $$d$$-regular case. We do the following $$2 \mu_n$$ times: Choose $$i \in \{L,R\}$$ uniformly at random. If $$i=L$$, we play a height-$$(n-1)$$ cost sequence on the left subtree (scaled by $$1/\tau_n$$). Otherwise, we play $$c_\ell$$, where $$\ell$$ is the leaf constituting the right subtree.

Consider an online algorithm. If the algorithm sits in the left subtree when $$i=L$$, then either the algorithm moves out of the subtree (movement cost $$1$$), or it incurs the cost of a height-$$(n-1)$$ inductive sequence scaled by $$1/\tau_n$$. If it sits in the right subtree, then it pays cost $$1$$ (either by moving or staying and incurring the service cost). If we choose $$\tau_n \mathrel{\vcenter{:}}=\alpha_{n-1} \mathbb{E}[\mathrm{opt}_{n-1}]$$, then such an algorithm always pays at least $$\tau_n^{-1} \alpha_{n-1} \mathbb{E}[\mathrm{opt}_{n-1}]$$ in any of these cases. Therefore:

$$\label{eq:algn} \mathbb{E}[\mathrm{alg}_n] \geq \mu_n \tau_n^{-1} \alpha_{n-1} \mathbb{E}[\mathrm{opt}_{n-1}].$$

We now bound the cost of the optimal offline algorithm. Let $$\rho_L$$ be the number of times $$i=L$$ and let $$\rho_R \mathrel{\vcenter{:}}= 2\mu_n - \rho_L$$. The algorithm will always sit by default in the left subtree. If $$\rho_R=0$$, it will move to the right subtree, suffer zero service cost there, and then move back to the left subtree (paying total cost $$2$$). If $$\rho_R > 0$$, the algorithm will remain in the left subtree and play an optimal strategy for $$T_{n-1}$$.

This yields: \begin{aligned} \mathbb{E}[\mathrm{opt}_n] &\leq \left(1-{\mathbb{P}}[\rho_R=0]\right) \mathbb{E}\left[\rho_L \tau_n^{-1} \mathrm{opt}_{n-1} \mid \rho_R > 0\right] + 2 {\mathbb{P}}[\rho_R=0] \\ &\leq (1-4^{-\mu_n}) \mu_n \tau_n^{-1} \mathbb{E}[\mathrm{opt}_{n-1}] + 2 \cdot 4^{-\mu_n}.\end{aligned} Now choose: $\mu_n \mathrel{\vcenter{:}}=\frac{4 \tau_n}{\mathbb{E}[\mathrm{opt}_{n-1}]} = 4 \alpha_{n-1}\,.$ This yields: $\mathbb{E}[\mathrm{opt}_n] \leq \left(1-\tfrac12 4^{-4 \alpha_n}\right) \mu_n \tau_n^{-1} \mathbb{E}[\mathrm{opt}_{n-1}].$

Combined with \eqref{eq:algn}, we have $\alpha_n \geq \frac{\mathbb{E}[\mathrm{alg}_n]}{\mathbb{E}[\mathrm{opt}_n]} \geq \alpha_{n-1} + \tfrac12 4^{-4\alpha_{n-1}}.$ This implies that $$\alpha_n \geq \beta \log n$$ for some positive $$\beta < 1$$. (To see this observe, that if $$f(x)=\beta \log x$$, then $$f'(x) = \beta/x < \frac12 4^{-4 \beta \log x}$$ for $$\beta$$ chosen small enough.)

Note furthermore that $\mathbb{E}[\mathrm{opt}_n] \leq 4\,,$ and therefore $$\tau_n \leq O(\log n)$$.

## The general case

We have demonstrated lower bounds in two cases: When the underlying tree $$T$$ is regular, and when it is unbalanced and binary. The general case can be proved by combining these two strategies along any $$\Omega((\log n)^2)$$-HST. The next lemma contains the basic idea. We leave it to the reader as a basic exercise. (Hint: Use the concavity of $$x \mapsto \sqrt{x}$$.)

Suppose that $$n=n_1+n_2+\cdots+n_m$$ where $$n_1 \geq n_2 \geq \cdots \geq n_m \geq 1$$. Then either $$\sqrt{n_1}+\sqrt{n_2} \geq \sqrt{n}$$, or there is some $$\ell \geq 3$$ such that $$\ell \cdot \sqrt{n_\ell} \geq \sqrt{n}$$.

Suppose now that $$T$$ is a rooted tree with subtrees $$T_1, T_2, \ldots, T_m$$ beneath the root, and such that $$T_i$$ has $$n_i$$ leaves with $$n_1 \geq n_2 \geq \cdots \geq n_m \geq 1$$. The lemma says we can either consider only the first two subtrees (the binary, possibly “unbalanced” case), or we can take the first $$\ell$$ subtrees for some $$\ell \geq 3$$, prune them so they all have exactly $$n_\ell$$ leaves, and then prove a lower bound. Analyzing these two cases correspond roughly to the two lower bound arguments above.


text:
# If the sum of first p term of an A.P. is ap2 + bp,

Question:

If the sum of first $\rho$ term of an A.P. is $a p^{2}+b p$, find its common difference.

Solution:

Here, we are given,

$S_{p}=a p^{2}+b p$

Let us take the first term as a’ and the common difference as d.

Now, as we know,

$a_{p}=S_{p}-S_{p-1}$

So, we get,

$a_{p}=\left(a p^{2}+b p\right)-\left[a(p-1)^{2}+b(p-1)\right]$

$=a p^{2}+b p-\left[a\left(p^{2}+1-2 p\right)+b p-b\right]$ $\left[\right.$ Using $\left.(a-b)^{2}=a^{2}+b^{2}-a b\right]$

$=a p^{2}+b p-\left(a p^{2}+a-2 a p+b p-b\right)$

$=a p^{2}+b p-a p^{2}-a+2 a p-b p+b$

$=2 a p-a+b$$\ldots(1) Also, a_{p}=a^{\prime}+(p-1) d =a^{\prime}+p d-d =p d+\left(a^{\prime}-d\right)$$\ldots(2)$

On comparing the terms containing in (1) and (2), we get,

$d p=2 a p$

$d=2 a$

Therefore, the common difference is $d=2 a$

format: plain


text:
A. TL
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Valera wanted to prepare a Codesecrof round. He's already got one problem and he wants to set a time limit (TL) on it.

Valera has written n correct solutions. For each correct solution, he knows its running time (in seconds). Valera has also wrote m wrong solutions and for each wrong solution he knows its running time (in seconds).

Let's suppose that Valera will set v seconds TL in the problem. Then we can say that a solution passes the system testing if its running time is at most v seconds. We can also say that a solution passes the system testing with some "extra" time if for its running time, a seconds, an inequality 2a ≤ v holds.

As a result, Valera decided to set v seconds TL, that the following conditions are met:

1. v is a positive integer;
2. all correct solutions pass the system testing;
3. at least one correct solution passes the system testing with some "extra" time;
4. all wrong solutions do not pass the system testing;
5. value v is minimum among all TLs, for which points 1, 2, 3, 4 hold.

Help Valera and find the most suitable TL or else state that such TL doesn't exist.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 100). The second line contains n space-separated positive integers a 1, a 2, ..., a n (1 ≤ a i ≤ 100) — the running time of each of the n correct solutions in seconds. The third line contains m space-separated positive integers b 1, b 2, ..., b m (1 ≤ b i ≤ 100) — the running time of each of m wrong solutions in seconds.

Output

If there is a valid TL value, print it. Otherwise, print -1.

Examples
Input
3 64 5 28 9 6 10 7 11
Output
5
Input
3 13 4 56
Output
-1


text:
# All Questions

62 views

### Real-time Tick Filtering

Is anybody aware of any papers regarding tick/quote filtering algorithms. I'm aware of the Olsen stuff, but I'd prefer something with fewer free parameters.
64 views

### Binary Option valuation problem in R using RQuantLib; also result validation aspect

When I am trying to value Binary Option using RQuantLib I am not getting all the greeks for exctype "american" wheras "european" exctype is fine. What is the problem here ? ...
49 views

### Is it OK to consider the expected return is zero for stocks when calculating VaR over a short horizon?

I want to implement the approach described in the following recipe for calculating VaR: Is there a step-by-step guide for calculating portfolio VaR using monte carlo simulations I was told that I can ...
41 views

### Macaulay Duration: Duration for 2 bonds

Using Macaulay Duration, determine the duration of Bond B if Bond A and B (market value of 600 000 dollars and 400 000 dollars respectively) have a duration of 6.7 years and the duration of A is ...
44 views

146 views

### Has automated trading produced profits at IEX?

Is there evidence that automated trading is profitable on the latency-enforced portion of the exchange? On the one hand, if automated trading was profitable when these limits existed naturally, it ...
67 views

### Why vega increases further out in time

Why do back months options have a higher vega than front month options? If possible , kindly explain on an intuitive level without a lot of math.
75 views

### Computing the minimum variance portfolio

Given two risky assets and their corresponding covariance matrix, how do I compute the global minimum variance portfolio, its standard deviation and its expected return?
192 views

### at c(x)% “where x is a numerical figure”, what does that c mean?

When i read financial news, sometimes, there is cX% (where X is a number). Below are few examples: 1. "improving to c4% on a proforma basis" 2. "market share is now c6% of the ..." What does that c ...
257 views

### Bootstrapping zero-rates from AUD swap rates

I have a pay fixed / receive floating interest-rate-swap on the AUD BBSY that I'd like to price for the purposes of accounting. I understand the general process to be as follows (assuming ...
241 views

I am trying to gather historical data for experimental reasons (intellectual curiosity) and am having trouble understanding how that data is calculated. First some data gathering on AAPL from Feb. ...
107 views

### Online algorithm for selecting smoothing parameter?

In Online Algorithms in High-frequency Trading the authors demonstrate online, exponentially-weighted algorithms for mean, variance, and linear regression. The authors estimate their smoothing ...
143 views

### What are the parameters of the function PORTVAR in Matlab?

According to the Matlab help, Portvar will give the "Variance for portfolio of assets" by entering the returns of the Assets and the corresponding weight. However, it does not explain the parameters ...
34 views

### Transaction Costs Measure ATOP: What does it mean and exactly measure?

I went through some presentations about LowVol strategies for some indices. In the presentations were tables with average returns, vola, Sharp ratio and ATOP. I have no clue what this ATOP is supposed ...
158 views

### Investment: Bond vs Equity

I was talking to a friend recently and he asked me the following question. If I have a device which perfectly (with 100% accuracy) predicts that both a bond (e.g. AAA rated government bond) and the ...
91 views

### How do I track implied volatility of specific delta?

I'm a newbie with respects to volatility trading and options. I recently purchased a book on the topic called "Trading Implied Volatility -An introduction" by Simon Gleadall. It's been one of the most ...
91 views

### Variance calculation

How could I calculate variance when I have a snapshot of a portfolio that shows the following for each stock: Purchase Price, Close Price, Change in value, Change in percentage, Shares owned, ...
102 views

### Backtesting software with custom data input

I was considering to develop a custom backtesting platform for myself. However, I see that it would require some significant time and effort, and the result might not be as initially expected. So I ...
60 views

### Calculating “Market Index Dividend Yield” of the ASX

In attempts to establish an investment portfolio with a long term horizon, the method of relative dividend yield has caught my attention. I require the Market Index Dividend Yield to proceed. The ...


text:
# Will my idea for simple-minded renormalization work?

+ 1 like - 3 dislike
203 views
This is a simpleminded approach to dealing with
divergences.

We are trying to calculate some Feynman diagrams and there are
a finite number of divergent integrals. Presumably the high energy
behavior of the theory is not being handled properly.

We generally believe in the theory so we believe that if it properly
handled the high energy behavior the integrals would turn out finite.
Since we can't calculate the integrals we simply treat them as
additional parameters to be determined by observation.
So e.g. instead of $\{e,m\}$, we have $\{e,m,I_1,I_2,I_3\}$.
We then proceed to calculate. Things are very simple. We don't have to
worry about overlapping divergences. There are no infinities at all.
We don't have to prove that the integrals can be absorbed by the
original parameters. If they can be it will appear in the calculations.
If they can't  it's not fatal.

Will this work?

Closed as per community consensus as the post is not appropriate for the Q&A section of PO
recategorized Jun 7, 2015

Hi ockeghem,

this looks rather like an abstract of some paper, the question if what you are doing will work can not be answered without looking at your specific calculations. I therefore vote to close it here. The @downvoters may probably also want to follow the link to my closevote above and upvote it there ...

But you can request the correspoding paper to be imported into our reviews section, to obtain a review and further discussion. This will most probably also answer the question if your approach works.

In the context of a proper renormalization group analysis, I think your terms $I_1$, $I_2$, $I_3$ could in principle correspond to some operators (or terms in the action, Lagrangian) that are only important at certain high energy scales (corresponding to new physics or effects kicking in).

But it is really difficult to tell without knowing in some more detail what exactly you are doing...

Do I get it right, that you declare the results of the integrals as constants to be determined experimentally? That doesn't explain why the integral diverges, and that's why you need renormalisation.

Everyone misunderstood my question! I wasn't explicit enough.

1. I am presenting a simple general approach to dealing with

divergences in field theory. This is not an abstract! I have no

particular problem in mind and am not looking for help solving it!

2. Consider QED. Everyone believes that it is mostly valid and

very successful, but has problems at high energies that are not

understood and cause divergences. Renormalization does not

explain these divergences but only evades them.

3. The usual (textbook) way of dealing with these divergences is

complicated  and involves counterterms and dealing with

overlapping divergences. There are mysterious invisible infinities.

4. Instead I propose to simply consider the divergent integrals as

additional  parameters --- like masses or coupling constants.

The justification for this is that if we did understand the high

energy behavior we could do the integrals and they would come

out finite.

No further thought is required --- we don't have to prove anything more.

We simply calculate. If the new parameters $I_i$  can be absorbed

into the old ones $e,m$  it will show up when the diagrams are

calculated. Otherwise there are additional parameters that have to be fitted

to observed data.

5. Is this renormalization? I don't think so. It's logically simpler.

If it gives the same results then the answer to my question is 'yes'

-- it works!

6. The point of all this is not necessarily practical calculation but

to show that a theory with a finite number of divergent integrals is

calculable without any appeal to special renormalization techniques.

I hope this clarifies things. I'm having trouble with the editor. Why

is this doublespaced?

@ockeghem It's clear enough. It's just nonsensical.

@dimension10 Please allow him the chance to explain himself.

@ockeghem Try to place you thoughts in the context of scalar field theory. Preferably clearly detailing the steps. I can definitely say I don't understand your motives.

@Prathyush as already said, the post seems to be the abstract of a paper. So he should submit this paper to our Reviews section, where we can review and discuss it.

In case there are not yet any calculations done to support the conclusions and claims made in the above "question", neither the Q&A nor the Reviews section of PO would be an appropriate place for it.

Simply rewriting this Q&A question does not help, the missing information that must be added to judge if the above approach works is substantial and worth a whole paper. It should therefore definitively go into the reviews section.

+ 0 like - 2 dislike

Will this work?

You want us to do this research for you and give you the answer?

We generally believe in the theory so we believe that if it properly
handled the high energy behavior the integrals would turn out finite.

How can you "generally believe in theory" if the high energy behavior is certainly handled in a wrong way and you know it?

Yes, "properly handled the high energy behavior" may help, I call it "reformulation", but for that you have to understands why you currently handle it in a wrong way. Replacing divergent integrals with cut-off integrals and considering the cut-off theory as a "fitting function" is the actual renormalization approach, so you propose nothing new. And this is fatal! You did not get the right physics!

answered Jun 7, 2015 by (112 points)
edited Jun 7, 2015
###### (Oops, the original revision of my above comment, saying that there was something right with the answer, was posted despite the fact that I edited it once I understood what exactly the OP was trying to say. The final revision was:)

Erm, no - this is not renormalisation at all. The OP is basically saying that we should consider the results of divergent integrals as something to be experimentally verified. However, this does not actually explain anything, on the contrary - renormalisation does explain everything.

Tangential discussion moved to chat.


text:
### Using Elimination Theory to construct Rigid Matrices

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar & Jayalal Sarma M. N.
The rigidity of a matrix $A$ for target rank $r$ is the minimum number of entries of $A$ that must be changed to ensure that the rank of the altered matrix is at most $r$. Since its introduction by Valiant \cite{Val77}, rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all $\nbyn$ matrices over an infinite field have a rigidity of $(n-r)^2$. It is...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our Documentation.


text:
P: 367
 Quote by pamparana Hello, I was going through the same problem. From what I can see on the net, one of the relations a linear function has to express is: f(u + v) = f(u) + f(v) Now if f(x) = ax + b is linear then f(u + v) = a(u+v) + 2b So f(u + v) is not equal to f(u ) + f(v). So why is f(x) = ax + b linear as it fails this criteria? Sorry for this stupid question...... Thanks, Luc
It is not a stupid question. The definition above is exactly the definition of a linear function, i.e. a function f that satisfies f( cx + y ) = c f ( x ) + f ( y ) ( note that you can pull the scalar out, so that functions of the form cx are linear )
the map f ( x ) = ax + b is taught to us in grade school as a linear function on the basis that it draws a line. Actually though, it is called an "affine function" ( it acts essentially like a linear map though, the map will satisfy all the properties if you simply translate everything by b ).
In the context of differential equations, both cases are known as "linear equations"


text:
Article | Open

# Hamiltonian simulation with optimal sample complexity

• npj Quantum Information 3, Article number: 13 (2017)
• doi:10.1038/s41534-017-0013-7
Revised:
Accepted:
Published online:

## Abstract

We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631–633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.

## Introduction

Much work has been done on the time and query complexity of Hamiltonian simulation when given a classical description or black box description of the Hamiltonian. Lloyd provided the first formal results on simulation, considering Hamiltonians that consist of sums of non-commuting terms.1 Other lines of research have focused on simulating sparse Hamiltonians, with a long sequence of work recently culminating in an optimal algorithm2 (see ref. 3 for a more complete history of work in this field).

In this work, we approach the problem of Hamiltonian simulation from a slightly different perspective. Rather than given a classical description or black-box access to a Hamiltonian H, we consider the problem of simulating H when given many copies of a quantum state ρ that encodes the Hamiltonian to be simulated. In particular, we assume that

$ρ= H + c 1 Tr ( H + c 1 )$
(1)

for some constant $c∈R$ such that $H+c1$ is positive semidefinite and nonzero. In that case, ρ itself is positive semidefinite and Tr ρ = 1, so ρ is a valid density matrix. Note that the Hamiltonian dynamics of H and ρ are equivalent up to an overall phase and time scaling. Moreover, since the Hamiltonian H in Eq. (1) can be arbitrary, any unitary can in fact be expressed as eiρt for an appropriately chosen state ρ and time t.

This modified version of the original Hamiltonian simulation problem is what we call sample-based Hamiltonian simulation: given one copy of an unknown state σ and n copies of an unknown state ρ, implement the following map:

$σ⊗ ρ ⊗⋯ ⊗ ρ n ↦ e - i ρ t σ e i ρ t$
(2)

where t is the desired evolution time. We also allow for some error in the final state—we denote by δ the trace distance4 between the state that is output by the protocol and the ideal state eiρtσeiρt. This problem was first considered in ref. 5, where the authors give a simple protocol, which we call the LMR protocol (LMR comes from the author’s initials: Lloyd, Mohseni, and Rebentrost), for approximately implementing the unitary eiρt using many copies of ρ. Their protocol is based on a partial swap operation that can also be considered as a finite-dimensional analog of a beam-splitter.6 An interesting feature of the LMR protocol is that it is agnostic with regard to ρ. In the spirit of 7, 8 this suggests interpreting ρ as a “quantum software state”.

The main motivation for sample-based Hamiltonian simulation in ref. 5 is to perform principal component analysis of ρ. They do this by performing phase estimation on the unitary e. (We note in Supplementary Information Section C that a slightly more careful analysis gives a polynomial improvement in sample complexity over the complexity given in ref. 5 for performing phase estimation, which is a subroutine for principal component analysis). The LMR protocol has applications to many problems in machine learning, e.g., refs 5, 9,10,11.

In this paper, we ask the following question: given t and δ, what is the minimum n (number of copies of ρ) necessary to implement the unitary eiρt on an unknown state σ to trace distance at most δ? We call this the sample complexity of Hamiltonian simulation.

While the LMR protocol acts with each copy of ρ sequentially, perhaps one could achieve better performance by acting with a global operation?12 For example, recent near-optimal tomographic protocols have relied on performing global operations (like the Schur transform) on many copies of the unknown state.13, 14 Along those lines, perhaps one could do better than LMR by applying tomographic protocols to get an estimate $ρ ^$ of ρ from the n copies of ρ, and then evolve according to $e - i ρ ^ t$.

On the contrary, however, we show that LMR performs asymptotically better than any tomographic strategy (‘LMR protocol vs. state tomography’), and performs sample-based Hamiltonian simulation with asymptotic optimality in both t and δ simultaneously (‘LMR protocol is optimal’). We additionally show LMR is optimal in δ when restricting to pure states, and provide a sample-optimal algorithm for a variant of Grover’s search. In ‘Generalized LMR for simulation of Hermitian polynomials’, we discuss the sample complexity of more complex Hamiltonians that depend on multiple states. For example, we show how to simulate the Hamiltonians given by any Hermitian polynomial (i.e. any element of the Jordan–Lie algebra15) generated by states ρ1,…, ρ K to which we are given sample access. As applications of this result, we show how to simulate the commutator i[ρ1, ρ2] and anticommutator {ρ1, ρ2} of two states ρ1 and ρ2, and how to simulate any real linear combination of states ρ1,…, ρ K when given access to many copies of those states. We prove the optimality of the commutator, anticommutator, and linear combinations protocols. In ‘Applications of commutator simulation’, we give applications of commutator simulation to orthogonality testing and quantum state addition. In ‘Universality of LMR’, we show how to use sample-based Hamiltonian simulation to implement a universal model of quantum computation using only partial swaps and a stream of input qubits initialized in |0〉 and |+〉.

In ‘Discussion’, we discuss the results and suggest open problems. Finally, in ‘Methods’ we give proofs for two of the main results in the paper: the lower bound on the LMR protocol, and the protocol for simulating Hamiltonians given by Hermitian polynomials of the input states.

### Notation

We use $H$ to denote a finite-dimensional Hilbert space, and $D ( H )$ to represent the set of positive semi-definite operators with trace 1 on $H$ (i.e. the set of valid quantum states).

The trace distance between $ρ,σ∈D ( H )$ is given by $1 2 ∥ ρ - σ ∥ 1$, where $∥ A ∥ 1 :=Tr ( A A † ) .$ The trace distance between ρ and σ gives the maximum difference in probability of any measurement on the two states.4 For two quantum channels $E 1$ and $E 2$ that act on $D ( H )$, their trace norm distance is defined as

$1 2 ∥ E 1 - E 2 ∥ tr := 1 2 max ρ ∈ D ( H ) ∥ E 1 ( ρ ) - E 2 ( ρ ) ∥ 1$
(3)

The diamond norm distance is defined as

$1 2 ∥ E 1 - E 2 ∥ ◇ := 1 2 max k , ρ ∈ D ( H ⊗ H k ) ∥ ( E 1 ⊗ I ) ( ρ ) - ( E 2 ⊗ I ) ( ρ ) ∥ 1$
(4)

where $I$ is the identity channel on a k-dimensional space $H k$. Note $∥ E 1 - E 2 ∥ ◇ ≥∥ E 1 - E 2 ∥ tr$.

We use $1 A$ to mean the identity matrix acting on subsystem A, but if clear from context, we will drop the subscript. We use |+〉:=(|0〉+|1〉)/(2)1/2 and denote single-qubit Pauli operators as X, Y, and Z.

## Results

### LMR protocol vs. state tomography

Lloyd, Mohseni, and Rebentrost5 gave a simple method for approximating the transformation in Eq. (2). The number of copies of ρ required by their procedure is not only independent of σ and ρ, but is independent of the dimension and rank of ρ. We state their result in a slightly more general form, where σ has two registers and eiρt is applied only to one of them.

### Theorem 1

(ref. 5). Let$ρ∈D ( H A )$and$σ∈D ( H A ⊗ H B )$be two unknown quantum states and$t∈R$(can be either positive or negative). Then there exists a quantum algorithm that transforms$σ AB ⊗ ρ A 1 ⊗⋯⊗ ρ A n$into$σ ̃ AB$such that

$1 2 ∥ ( e - i ρ A t ⊗ 1 B ) σ AB ( e i ρ A t ⊗ 1 B ) - σ ̃ AB ∥ 1 ≤δ,$
(5)

as long as the number of copies of ρ is n = O(t2/δ). In other words, this quantum algorithm implements the unitary eiρtup to error δ in the diamond norm, using O(t2/δ) copies of ρ.

We will give a sketch of the proof because many of our more general simulation techniques build on their ideas; for the full proof see Supplementary Information Section A. For simplicity we assume ρ and σ have the same dimension. Using a Taylor series expansion, the target state is

$e - i ρ t σ e i ρ t =σ-i [ ρ , σ ] t- 1 2! [ ρ , [ ρ , σ ] ] t 2 +⋯.$
(6)

We note that for very small evolution times Δ, we have the following direct calculation:

$Tr 2 [ e - i S Δ ( σ ⊗ ρ ) e i S Δ ] =σ-i [ ρ , σ ] Δ+O ( Δ 2 )$
(7)
$= e - i ρ Δ σ e i ρ Δ +O ( Δ 2 ) ,$
(8)

where by Tr i we mean taking the partial trace of the ith subsystem, and S is the swap operator between the two registers. If we take Δ = δ/t and repeat this procedure O(t2/δ) times, we end up implementing the operator eiρt up to error O2 · t2/δ) = O(δ).

Thus the LMR protocol uses O(t2/δ) copies of ρ to implement the unitary eiρt up to error δ in trace norm. (While not noted explicitly in ref. 5, the LMR protocol can be implemented efficiently, i.e. using $O ( log D ⋅ t 2 ∕ δ )$ single-qubit and Fredkin (controlled-swap) gates, where $D= dim ( H A )$, by applying the linear combination of unitaries algorithm (see, e.g., ref. 3 or ref. 16, Theorem 2.4). For more information, see Supplementary Information Section A). To obtain the result for the diamond norm, simply replace σ by σAB and perform the partial swap operation eiSΔ only between the A registers of σAB and ρA, and then discard the last register that was originally holding ρA.

Additionally, the LMR protocol can be modified to implement the controlled-eiρt operation, which will be important if one wants to implement phase estimation on eiρt. A method for implementing controlled-eiρt is stated without proof in ref. 5; we prove this method works and provide an additional approach in the Supplementary Information Section A.1.

An alternative method to LMR for sample-based Hamiltonian simulation would be to perform tomography on the copies of ρ to get an estimate $ρ ^$ of ρ, and then implement $e - i ρ ^ t$. In Supplementary Information Section B, we show that the number of samples needed if using this strategy is

$n=Ω C d r ( t - δ ) 2 δ 2 log ( d t ∕ r δ ) + t 2 δ 2 ,$
(9)

where d is the dimension of ρ, r is the rank of ρ, and t and δ are as in Theorem 1.

Comparing with Theorem 1, since LMR does not have any dependence on d or r, we immediately see that for large d or r, LMR does significantly better. Furthermore, even fixing d and r, we see that LMR provides a square-root improvement in sample complexity over tomography in terms of δ.

### LMR protocol is optimal

To prove the LMR protocol is in fact asymptotically optimal, we first give a lower bound on the sample complexity of distinguishing two specific states. Next, we assume we have a protocol that simulates eiρt to trace norm (which is a weaker assumption than using diamond norm) δ using f(t, δ) samples of ρ for some function f. Then we show that using such a protocol one can distinguish these two states. However, if f = o(t2/δ), we would violate our lower bound on state discrimination.

### Theorem 2

Let f(t, δ) be the number of copies of ρ required to implement the unitary eiρtup to error δ in trace norm. Then as long as δ ≤ 1/6 and δ/t ≤ 1/(6π), it holds that f(t,δ) = Θ(t2/δ).

The proof of Theorem 2 can be found in ‘Discussion’. The proof uses mixed states, so it could be possible that simulating $exp ( - i ∣ ψ ⟩ ⟨ ψ ∣ t )$ for a pure state |ψ〉 could be done more efficiently. This relates to a practically relevant question, namely, the fact that the LMR protocol and certain pure states as resources create a universal model for quantum computation (see ‘Universality of LMR’). However, we can show that LMR is also optimal for pure states in the δ error parameter. We cannot expect to prove a meaningful lower bound on the t dependence in pure state LMR. The reason is that, given any state ρ and promised that $exp ( - i ρ t )$ is periodic with period T (i.e. $exp ( - i ρ t 1 ) = exp ( - i ρ t 2 )$ for any t2 = t1 + kT for integer k and real number T ), we can always simulate the Hamiltonian ρ for an equivalent time t[0,T ) instead. Therefore asymptotic scaling in terms of large t is meaningless. For pure states, we immediately know the period, namely 2π.

To prove that the LMR protocol is optimal for pure states, we employ variants of Grover’s search. While Grover’s search17 is a well-known quantum mechanical task, it is not often stated in its form as a decision problem, and very rarely18 as a metrological decision problem, where the inputs are unitaries and the output depends on a property that those unitaries either possess or do not possess. This guise is useful for our purposes, however, because the LMR protocol allows us to turn metrology problems on states into metrology problems on quantum operations.

In the metrological view, Grover’s search, or perhaps more precisely amplitude amplification,19 is the following problem of parameter estimation. Let $T$ be a subspace of $C 2 q$. We call $T$ the target subspace. Let $U T$ be a unitary acting on q + 1 qubits such that

$U T ϕ 0 = ϕ 1 , if ϕ ∈ T , ϕ 0 , if ϕ ⊥ T .$
(10)

In this problem, and in the following variations, we will assume access to $U T$ and $U T †$ are free. For a q-qubit unitary V, define

$λ:= ( 1 ⊗ 1 ) U T ( ( V 0 ⊗ q ) ⊗ 0 ) 2 .$
(11)

Then in Grover’s search, the task is to decide whether λ ≥ w (for w > 0) or λ = 0, while using V and V as few times as possible. In other words, if we call |s〉: = V|0〉q the start state, we would like to determine whether the start state has substantial probability mass in the target subspace or none, promised one is the case. If we solve this problem using Grover’s search and count the number of uses of V and V required to succeed with probability 1 − ε, we get the standard complexity $Θ ( log ( 1∕ ε ) ∕ w )$.20, 21

One simple modification of metrological Grover’s search is to replace the circuit description of V with copies of the start state |s〉 instead. The problem is now to determine whether $λ:= ( 1 ⊗ 1 ) U T s ⊗ 0 2$ is at least w > 0 or equal to zero, promised one is the case, given copies of |s〉 and unlimited access to $U T$ and $U T †$. We call this sample-based Grover’s search.

A second variant of metrological Grover’s search is to replace both V and $U T$ with quantum states. In this form, the problem becomes: given copies of q-qubit states |s〉 and |t〉, determine whether $λ= ∣ ⟨ s ∣ ∣ t ⟩ ∣ 2$ is at least w > 0 or equal to zero, promised one is the case. We call this variant orthogonality testing. We address optimal orthogonality testing in ‘Applications of commutator simulation’.

In Supplementary Information Section D.2, we first prove that for sample-based Grover’s search, we lose the square-root advantage of the regular Grover’s search:

### Lemma 3

Sample-based Grover’s search with success probability 1 − ε uses$Θ ( log ( 1∕ ε ) ∕ w )$ copies of |s〉.

Using this result, we prove:

### Theorem 4

The number of copies of an unknown pure state ρ required for any algorithm to simulate eiρt to trace norm δ is Ω(1/δ).

The main idea of the proof, which can be found in Supplementary Information Section D.2, is that the reflections V and V needed for Grover’s algorithm can be implemented by sample-based Hamiltonian simulation using many copies of the state |s〉. This gives us a way to reduce sample-based Grover’s search to sample-based Hamiltonian simulation. Then we apply the lower bound of Lemma 3.

### Generalized LMR for simulation of Hermitian polynomials

We show sample-based Hamiltonian simulation of Eq. (2) can be further generalized. Instead of evolution of σ by a single state ρ, the target Hamiltonian H could be encoded by some combination of multiple states ρ1,ρ2,…,ρ K . For example, we might want to implement the map

$σ⊗ ⊗ j =1 K ρ j ⊗ n j ↦ e - i f ( ρ 1 , ρ 2 , … , ρ K ) t σ e i f ( ρ 1 , ρ 2 , … , ρ K ) t ,$
(12)

where H = f(ρ1,ρ2,…,ρ K ) is some Hermitian polynomial function of the input states. In fact, we prove it is possible to simulate arbitrary Hermitian multinomial functions:

### Theorem 5

Let$ρ 1 ,…, ρ K ∈D ( H A )$and$σ AB ∈D ( H A ⊗ H B )$be unknown quantum states, and let

$H= ∑ r ∈ R c r H r , H r = 1 2 ( e i ϕ r ρ r 1 ρ r 2 ⋯ ρ r ∣ r ∣ + e - i ϕ r ρ r ∣ r ∣ ρ r ∣ r ∣ - 1 ⋯ ρ r 1 )$
(13)

be a Hermitian polynomial in ρ1,…,ρ K , where R is a finite set of strings over the alphabet {1,2,…,K}. Using n samples from the states {ρ1,…,ρ K }, a quantum algorithm can transform σABinto$σ ̃ AB$such that

$1 2 ∥ ( e - i H t ⊗ 1 B ) σ AB ( e i H t ⊗ 1 B ) - σ ̃ AB ∥ 1 ≤O ( δ ) ,$
(14)

if n = O(Lc2t2/δ) where c: = ∑ rR |c r | and$L:= max r ∈ R ∣r∣$is the multinomial degree of H. Moreover, on average, the number of copies of ρ j consumed is n j  = O(κ j c2t2/δ) where κ j  = ∑ rR v j (r)|c r |/c, and v j (r) = |{s:r s  = j}|.

As corollaries of Theorem 5, we have the following simulation results for linear combinations of states (Corollary 6) and for the commutator and anticommutator of two states (Corollary 7):

### Corollary 6

Let$ρ 1 ,…, ρ K ∈D ( H A )$and$σ AB ∈D ( H A ⊗ H B )$be unknown quantum states, and let$c 1 ,…, c K ∈R$. Using n samples from the states {ρ1,…,ρ K }, a quantum algorithm can transform σABinto$σ ̃ AB$such that

$1 2 ∥ ( e - i H t ⊗ 1 B ) σ AB ( e i H t ⊗ 1 B ) - σ ̃ AB ∥ 1 ≤O ( δ ) ,H= ∑ j =1 K c j ρ j ,$
(15)

if n = O(c2t2/δ) where$c:= ∑ j =1 K ∣ c j ∣$. Moreover, on average, the number of copies of ρ j consumed is n j  = O(|c j |ct2/δ).

### Corollary 7

Let$ρ 1 , ρ 2 ∈D ( H A )$and$σ AB ∈D ( H A ⊗ H B )$be unknown quantum states, and ϕ[0, 2π). Using n samples each of ρ1and ρ2, a quantum algorithm can transform σABinto$σ ̃ AB$such that

$1 2 ∥ ( e - i H t ⊗ 1 B ) σ AB ( e i H t ⊗ 1 B ) - σ ̃ AB ∥ ◇ ≤ O ( δ ) , H = 1 2 ( e i ϕ ρ 1 ρ 2 + e - i ϕ ρ 2 ρ 1 ) ,$
(16)

if$n=O ( t 2 ∕ δ )$

Note from Eq. (16) that

$H= 1 2 cos ( ϕ ) { ρ 1 , ρ 2 } + 1 2 sin ( ϕ ) i [ ρ 1 , ρ 2 ] ,$
(17)

so by choosing ϕ = 0, we recover the anticommutator Hamiltonian {ρ1,ρ2}/2, and choosing ϕ = π/2 we recover the commutator Hamiltonian i[ρ1,ρ2]/2.

Furthermore, Corollary 6 and Corollary 7 are both optimal:

### Theorem 8

Let {c1,…,c K } be a set of K real numbers. Then there exist ρ1,…,ρ K such that to simulate$H= ∑ j =1 K c j ρ j$for time t and to error δ in trace norm requires Ω(c2t2/δ) copies of states in {ρ1,…,ρ K }, where c: = ∑ j |c j |, as long as δ and δ/(ct) are smaller than some constants.

### Theorem 9

To simulate H = i[ρ1, ρ2] for time t and to trace norm error δ requires Ω(t2/δ) copies each of the states ρ1and ρ2, as long as δ and δ/t are smaller than some constants.

While Theorem 9 only applies to commutators, it is easy to see that the simulation from Corollary 7 of the anticommutator {ρ1, ρ2} has optimal scaling in t and δ, because in the qubit case, we can always choose $ρ 2 =1∕2$ so that {ρ1, ρ2} = ρ1 and we can apply the lower bound from Theorem 2. The proofs for results in this section can be found in Supplementary Information Section D.3.

### Applications of commutator simulation

We now describe how one can use commutator simulation to perform tasks such as orthogonality testing and coherent addition of two pure states.

We first give a protocol for coherent state addition: given many copies of unknown pure states |ψ1〉 and |ψ2〉, the task is to obtain a state of the form

$a ψ 1 +b ψ 2$
(18)

for some $a,b∈R$. Note that the target state is sensitive to the global phases of the two input states—in particular, the relative phase between |ψ1〉 and |ψ2〉—which have no physical meaning. To make the task well-defined, we instead demand the target state to be of the form

$a ψ 1 +b ψ 2 ψ 1 ψ 2 ψ 1 ψ 2$
(19)

for some $a,b∈R$, which is unique (up to a global phase) even when the global phases of the two input states have not been specified. Note that we can always recover Eq. (18) from Eq. (19) by fixing the global phases of the two input states appropriately (i.e. such that 〈ψ2|ψ1〉 > 0).

### Theorem 10

Let |ψ1and |ψ2be unknown pure states of the same dimension. Promised that the angle between the two states is$Δ:= arccos∣ ⟨ ψ 1 ∣ ψ 2 ⟩ ∣$and Δ{0,π/2}, it is possible to create the state

$ψ ( χ ) := 1 sin Δ ( sin ( Δ - χ ) ψ 1 + e i φ sin χ ψ 2 )$
(20)

to trace distance δ using$O ( χ 2 δ sin 2 2 Δ )$copies of |ψ1and |ψ2, where e: = 〈ψ2|ψ1〉/|〈ψ2|ψ1〉| is an unimportant phase factor that can be ignored by appropriately adjusting the global phases of the two states.

A similar protocol has been independently discovered in ref. 22, Theorem 2, and recently implemented experimentally.23 While our protocol involves only the two input states |ψ1〉 and |ψ2〉, the protocol of ref. 22 requires an additional reference state |χ〉. Another difference between the two results is that we consume several copies of the input states to obtain an approximation of the target state, while23 consume only a single copy but rely on a probabilistic postselection.

The proof of Theorem 10 (which can be found in Supplementary Information Section F) is based on commutator simulation and effectively implements a rotation in the two-dimensional subspace spanned by |ψ1〉 and |ψ2〉. Indeed, note from Eq. (20) that |ψ(0)〉 = |ψ1〉 and |ψ(Δ)〉 = e|ψ2〉, while intermediate values of χ produce states that interpolate between these two. (If one does not care about the relative phase $e i φ$, one can always exchange the two states and replace $χ$ by $Δ-χ$, which would improve the complexity by a constant factor when $χ>Δ∕2$). As a consequence, the target state in Eq. (19) has real coefficients a and b. One can also achieve complex coefficients using a more sophisticated Hamiltonian that includes terms proportional to |ψ1〉〈ψ1| and |ψ2〉〈ψ2|, but we do not consider this case here for the sake of simplicity.

Our protocol requires a very large number of samples when the states |ψ1〉 and |ψ2〉 have either very small or very large overlap (i.e. in cases when $sin 2 2Δ$ is very small). This is because we use commutator simulation to effectively implement a rotation in the two-dimensional subspace spanned by |ψ1〉 and |ψ2〉, and in the special cases when |ψ1|ψ2〉 or |ψ1〉 = e|ψ2〉 the commutator vanishes and hence our protocol fails (in the second case the task is trivial though).

Interestingly, by choosing χ = Δ/2 in Eq. (20) it is possible to coherently add two states, i.e. create a state proportional to |ψ1〉 + |ψ2〉 (we are ignoring the relative phase between the two states). However, to determine Δ one needs to estimate the inner product between the two states, which can be done by running phase estimation on the commutator.

We note that the commutator of orthogonal states is zero, while the commutator of non-orthogonal states is non-zero (as long as the states are not identical). Using this fact, and by performing phase estimation on the unitary generated by the commutator of two pure states, we can create a test for orthogonality (for proof, see Supplementary Information Section F).

### Theorem 11

Let |ψ1and |ψ2be unknown pure states of the same dimension. Promised that either |〈ψ1|ψ2〉| = 0 or |〈ψ1|ψ2〉| ≥ w, deciding which with probability$1-ϵ$uses$Θ ( log ( 1∕ ϵ ) ∕ w )$copies of |ψ1and |ψ2.

### Universality of LMR

In many solid-state implementations of quantum computers, such as quantum dots,24 donor pairs,25 and electron spins,26 the Heisenberg exchange is the natural coupling interaction between qubits. More specifically, the Heisenberg interaction between qubits i and j is given by

$H i j := X i ⊗ X j + Y i ⊗ Y j + Z i ⊗ Z j ,$
(21)

where Xi, Yi, and Zi are the Pauli matrices acting on qubit i. Up to an overall scaling, this is the same as the swap interaction S used in the LMR protocol, see Eq. (7). In the solid state systems mentioned above, the Heisenberg interaction typically can be turned on and off for pairs of qubits for any desired length of time, and the operations induced by these interactions are usually fast and reliable.

While it is beneficial to create computing models that take advantage of the Heisenberg exchange interaction, this interaction is not universal for spin-1/2 systems.27 Several schemes have overcome this limitation by using encoded logical qubits and decoherence-free subsystems.28, 29

In this section, we use the LMR protocol to design a universal model for quantum computation that does not use encoded qubits, but which requires only the Heisenberg interaction, as well as the ability to prepare the states |0〉 and |+〉 on a single qubit. Our scheme thus requires n + 1 physical qubits to perform computations on n qubits, in contrast to encoded schemes, of which the simplest require 2 or 3 times the number of physical qubits.28, 29 Furthermore, there has been much research in the field of quantum dots on how to quickly and reliably prepare a fixed qubit state, e.g., in refs 30,31,32,33. These schemes could be applied to produce the single-qubit states |0〉 and |+〉 needed for our protocol.

We consider a connectivity graph of the qubits as in Fig. 1 (different connectivity graphs lead to different scalings depending on which costs you would like to optimize). We assume exchange interactions can be applied between connected qubits in the form of unitaries $exp ( - i t H i j )$ for arbitrary t. The qubit q* is where the states |0〉 and |+〉 are prepared.

Recall that arbitrary single-qubit gates combined with any entangling two-qubit gate is sufficient for universal quantum computation.34 Since we do not have encoded qubits, the exchange interaction itself immediately gives us an entangling gate. Now for universal quantum computation we need to show how to perform arbitrary single-qubit gates.

Let $X ϕ := exp [ - i θ X ]$ and let $Z θ := exp [ - i θ Z ]$ for Pauli’s X and Z. Then any single-qubit rotation can be written as X ϕ Z θ X ξ for some angles ϕ, θ, and ξ.4 Therefore, it is sufficient to show how to perform X and Z rotations.

If qubit i needs to have a single-qubit gate performed on it, using the Heisenberg interaction, we use swap gates to move that qubit to position 0 of Fig. 1. We now show how to perform Z ϕ and X θ on the qubit in position 0. Using LMR, given n copies of the state |0〉 input at qubit q*, using only partial swap operations on qubits q0 and q*, (i.e. applying the Heisenberg interaction between qubits q0 and q*) we can apply the unitary

$exp ( - i 2 ϕ ∣ 0 ⟩ ⟨ 0 ∣ ) = Z ϕ$
(22)

(up to a global phase) to accuracy O(n−1). Likewise, using the LMR protocol, given n copies of the state |+〉, using only partial swap interactions between qubits q0 and q*, we can apply the unitary

$exp ( - i 2 θ ∣ + ⟩ ⟨ + ∣ ) = X θ$
(23)

(up to a global phase) to accuracy O(n−1).

To apply an arbitrary single-qubit rotation to accuracy ε, we need O(ε−1) resource states |0〉 and |+〉 (this construction is reminiscent of ideas in ref. 35). Suppose that over the course of an algorithm, one must apply M single-qubit gates and M′ CNOT gates. A CNOT gate requires a constant number of single-qubit gates as well as a constant number of partial swap gates.34 Then to bound the error over the course of the algorithm, we require accuracy of O((M + M′)−1) for each single-qubit gate. Therefore, we require O((M + M′)2) resource states |0〉 and |+〉 in total. Additionally, using the connectivity graph of Fig. 1, to move qubits into proximity with one another to perform any single-qubit or two-qubit gate requires O(N) swap operations operations, where N is the number of qubits. Thus the total number of operations scales as O(N(M + M′)2).

The states |0〉 and |+〉 need not be prepared perfectly for our protocol to work. For example, given depolarized versions of these states, we would need to increase the number of rounds in the LMR protocol by a constant factor. In fact, two arbitrary states (other than |0〉 and |+〉) could be used, as long as they are well characterized and not diagonal in the same basis.

Our model produces a polynomial (in particular squared) blow-up in the number of operations, which still allows for universal quantum computation. However, it would be impossible to obtain a speed-up for problems such as Grover’s search. We hope it is a useful model for systems where the Heisenberg exchange is a natural operation. It may even be useful in non-solid state systems such as cold, trapped atoms, where it was shown that partial swaps could be implemented using Rydberg interactions or through coupling to a cavity.36

## Discussion

We have shown that the LMR protocol is optimal for the problem of simulating unknown Hamiltonians encoded as quantum states. Moreover, the protocol and its generalizations also turn out to be optimal for a variety of other tasks, such as discriminating between pure states and Hamiltonian evolution under the commutators of unknown states. We hope that this study will motivate the discovery of other possible applications of this versatile protocol.

We have not shown the optimality of our protocol for simulating the evolution by the multinomials in Eq. (12). It would be interesting to investigate whether it is optimal, or whether better algorithms can be found.

Another interesting aspect is the role of ancilla qubits in our protocol. While the original LMR protocol for Hamiltonian simulation is based on partial swaps and hence does not require ancilla qubits, the use of ancillas seems to be essential in our more general simulation protocol (see Fig. 2 in ‘Methods’). We wonder whether the use of ancillas is necessary in our protocol or, for example, whether it can instead be implemented using the continuous permutations introduced in ref. 12. These continuous permutations generalize the partial swap operation and do not require ancillas.

Another possible direction is to investigate distributed versions of our protocols in the context of multiparty communication. Reference 37 considers a protocol for simulating distributed unitaries over multiple remote parties using shared entanglement and a limited amount of quantum communication, and the techniques they use are reminiscent of those of the LMR protocol. It would be interesting to investigate the connections of ref. 37 with the protocols in our work.

Finally, the LMR protocol can be seen as allowing the encoding of the operation eiρt into multiple copies of a quantum state ρ. As discussed in ‘LMR protocol vs. state tomography’, having access to O(t2/δ) copies of ρ allows a user to perform the operation eiρt, but may be insufficient for the user to determine what ρ is through tomography. It is an intriguing question whether other quantum operations could be encoded into states in this way, so that a user could perform the quantum operation but learn little else about what operation is being performed. This could be seen as a form of quantum copy-protection.38 See ref. 39 for some progress in this direction, and ref. 40 for negative results when the encoding is required to be a circuit and not a state.

## Methods

In this section, we give proofs for two of the main results in the paper: Theorem 2 (optimality of the LMR protocol), and Theorem 5 (the protocol for simulating arbitrary Hermitian polynomials of the input states). Many of the other proofs in this paper are similar, and can be found in the Supplementary Information.

### Proof of Theorem 2

The upper bound holds by the LMR protocol, Theorem 1, so we will only prove the lower bound. The fact that the trace norm lower bounds the diamond norm makes a tight lower bound in terms of the trace norm a stronger result than if we had used the diamond norm. Let

$ρ ( x ) :=x 0 0 + ( 1 - x ) 1 1 = 1 2 1+ x - 1 2 Z.$
(24)

Then, given many copies of an unknown state ρ, suppose we want to distinguish between the cases ρ1: = ρ(1/2) and $ρ 2 :=ρ ( 1 2 + ϵ )$, with $0<ϵ≤1∕2$, promised ρ is one of the two. One way of doing this is to consider the single-qubit unitary operator $U ( ρ , t ) := exp ( - i ρ t )$. Then for t ε : = π/(2ε) the operators $U ( ρ i , t ϵ )$ become orthogonal, namely,

$U ( ρ 1 , t ϵ ) ∝1,U ( ρ 2 , t ε ) ∝Z,$
(25)

where indicates that we have hidden an unimportant phase factor. Consequently, applying $U ( ρ , t )$ to |+〉 and measuring in the X-basis will distinguish ρ1 from ρ2 with certainty.

Thus, we can distinguish between ρ = ρ1 or ρ = ρ2 with probability at least 2/3 using no more than f(t ε ,1/3) copies of ρ by implementing a map that differs from $U ( ρ , t ϵ )$ by trace norm 1/3. However, Lemma D1 in the Supplementary Information tells us that C η /ε2 samples of ρ are required if ε < η ≤ 1/2. Therefore

$f ( t ε ,1∕3 ) ≥ C η ∕ ϵ 2 =C t ϵ 2 , t ϵ ≥π,$
(26)

using the definition of t ε , and where C := 4C η /π2 is some positive constant. Eq. (26) holds whenever t ε  ≥ π since ε ≤ 1/2 and so $t ε = π 2 ⋅ 1 ε ≥π$.

Now suppose instead we have arbitrary δ and t satisfying δ ≤ 1/6 and t/δ ≥ 6π, as assumed in the theorem statement. We note the following inequality for any $t∈R$ and any integer m ≥ 0:

$mf ( t , δ ) ≥f ( m t , m δ ) ,$
(27)

which holds because one way of simulating $exp ( - i ρ m t )$ up to error is to run m times a simulation of $exp ( - i ρ t )$ up to error δ. Taking $m= ⌈ 1 ∕ ( 6 δ ) ⌉$, we have

$f ( t , δ ) ≥f ( m t , m δ ) ∕m$
(28)
$≥C ( m t ) 2 ∕m=Cm t 2$
(29)
$=Ω ( t 2 ∕ δ ) ,$
(30)

where Eq. (29) holds because  ≤ 1/6 + δ ≤ 1/3 and mt ≥ t/(6δ) ≥ π, so Eq. (26) applies.

We now give a proof of Theorem 5. One key tool in the proof will be the following lemma, which lets us simulate a Hamiltonian given by the difference of two subnormalized states:

### Lemma 12

Let$ρ ′ ∈D ( C 2 ⊗ H A )$be a quantum state of the form ρ′ = |0〉〈0|ρ+ + |1〉〈1|ρ, where ρ+,ρare unknown subnormalized states with Tr ρ+ + Tr ρ = 1. Using n samples of ρ, a quantum algorithm can transform σABinto$σ ̃ AB$such that

$1 2 ∥ ( e - i H t ⊗ 1 B ) σ AB ( e i H t ⊗ 1 B ) - σ ̃ AB ∥ 1 ≤O ( δ ) ,H= ρ + - ρ - ,$
(31)

if n = O(t2/δ).

The idea is to use the first qubit of ρ′ as a control that determines whether one applies a positive or negative time evolution of partial swap between the second register of ρ′ and the target state. The rest of the proof (found in Supplementary Information Section E.2) proceeds as in the proof sketch of the standard LMR protocol.

### Proof of Theorem 5

We first consider a term H r with r = (1,2,…,k), for some k such that 2 ≤ k ≤ K. (More general r will follow easily from this special case.) Let S k be the cyclic permutation of k copies of $H A$ that acts as follows: S k |j1,j2,…,j k 〉 = |j k ,j1,…,j k−1〉. In other words,

$S k := ∑ j 1 , j 2 , … , j k = 1 dim H A j k j 1 ⊗ j 1 j 2 ⊗ j 2 j 3 ⊗⋯⊗ j k - 1 j k .$
(32)

Consider the circuit in Fig. 2. The output is of the form $ρ ′ ( r ) = 0 0 ⊗ ρ + ( r ) + 1 1 ⊗ ρ - ( r )$, where

$ρ + ( r ) : = 1 2 ( ∣ a ∣ 2 ρ 1 + ∣ b ∣ 2 ρ k + a b * ρ 1 ρ 2 ⋯ ρ k + a * b ρ k ρ k - 1 ⋯ ρ 1 ) , ρ - ( r ) : = 1 2 ( ∣ a ∣ 2 ρ 1 + ∣ b ∣ 2 ρ k - a b * ρ 1 ρ 2 ⋯ ρ k - a * b ρ k ρ k - 1 ⋯ ρ 1 ) .$
(33)

When we chose $a b * = e i ϕ r ∕2$, we find

$ρ + ( r ) - ρ - ( r ) = 1 2 e i ϕ r ρ 1 ρ 2 ⋯ ρ k + 1 2 e - i ϕ r ρ k ρ k - 1 ⋯ ρ 1 = H r .$
(34)

To deal with arbitrary r with |r| = k, simply supply the appropriate input states ρ j in Fig. 2.

Now without loss of generality, we can assume c r  ≥ 0 for all r, since the sign can be absorbed into the phase ϕ r . Therefore by sampling from rR with probability c r /c and creating ρ(r), we obtain the state

$ρ ′ = 1 c ∑ r ∈ R c r ρ ′ ( r ) = 1 c 0 0 ⊗ ∑ r ∈ R c r ρ + ( r ) + 1 1 ⊗ ∑ r ∈ R c r ρ - ( r ) .$
(35)

By Lemma 12, we can therefore simulate the Hamiltonian

$H= ∑ r ∈ R c r ( ρ + ( r ) - ρ - ( r ) ) = ∑ r ∈ R c r H r$
(36)

for the desired time and precision using O(c2t2/δ) copies of ρ′. Since each copy of ρ′ requires a sample of a state ρ(r), and each of these states requires at most $L= max r ∈ R ∣r∣$ copies of states in {ρ1,…,ρ K }, we obtain the stated total sample complexity.

To calculate the average number of uses of ρ j , we note that ρ j is used v j (r) times to create the state ρ(r), and to create the state ρ′, the state ρ(r) is chosen with probability |c j |/c. Thus ρ j is used on average κ j  = ∑ rR v j (r)|c r |/c times to create a single ρ′. Then since O(c2t2/δ) copies of ρ′ are used in the simulation, we obtain the stated complexity.

## References

1. 1.

Lloyd, S. Universal quantum simulators. Science 273, 1073–1078 (1996).

2. 2.

Low, G.H. & Chuang, I.L. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters 108, 010501 (2017).

3. 3.

Berry, D. W., Childs, A. M. & Kothari, R. Hamiltonian simulation with nearly optimal dependence on all parameters. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, 792–809 (IEEE, 2015).

4. 4.

Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge University Press, 2010). https://books.google.com/books?id=-s4DEy7o-a0C.

5. 5.

Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum principal component analysis. Nat. Phys. 10, 631–633 (2014).

6. 6.

Audenaert, K., Datta, N. & Ozols, M. Entropy power inequalities for qudits. J. Math. Phys. 57, 052202 (2016).

7. 7.

Preskill, J. Plug-in quantum software. Nature 402, 357–358 (1999).

8. 8.

Gottesman, D. & Chuang, I. L. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature 402, 390–393 (1999).

9. 9.

Wang, G. Quantum algorithms for curve fitting. arXiv preprint arXiv:1402.0660 (2014).

10. 10.

Rebentrost, P., Mohseni, M. & Lloyd, S. Quantum support vector machine for big data classification. Phys. Rev. Lett. 113, 130503 (2014).

11. 11.

Cong, I. & Duan, L. Quantum discriminant analysis for dimensionality reduction and classification. New j. Phys. 18, 073011 (2016).

12. 12.

Ozols, M. How to combine three quantum states. arXiv preprint arXiv:1508.0086. (2015)

13. 13.

Haah, J., Harrow, A. W., Ji, Z., Wu, X. & Yu, N. Sample-optimal tomography of quantum states. Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, 913–925 (ACM, 2016).

14. 14.

O’Donnell, R. & Wright, J. Efficient quantum tomography. Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, 899–912 (ACM, 2016).

15. 15.

Emch, G. G. Mathematical and Conceptual Foundations of 20th-Century Physics. North-Holland Mathematics Studies (Elsevier Science, 1984). https://books.google.com/books?id=eYQHIjkaEroCpg=PA306.

16. 16.

Kothari, R. Efficient algorithms in quantum query complexity. Ph.D. thesis, University of Waterloo (2014). http://hdl.handle.net/10012/8625.

17. 17.

Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212–219 (ACM, 1996).

18. 18.

Demkowicz-Dobrzański, R. & Markiewicz, M. Quantum computation speedup limits from quantum metrological precision bounds. Phys. Rev. A 91, 062322 (2015).

19. 19.

Brassard, G., Høyer, P., Mosca, M. & Tapp, A. Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002).

20. 20.

Boyer, M., Brassard, G., Høyer, P. & Tapp, A. Tight bounds on quantum searching. Fortschritte der Physik 46, 493–505 (1998).

21. 21.

Buhrman, H., Cleve, R., de Wolf, R. & Zalka, C. Bounds for small-error and zero-error quantum algorithms. In Foundations of Computer Science, 1999. 40th Annual Symposium on, 358–368 (IEEE, 1999).

22. 22.

Oszmaniec, M., Grudka, A., Horodecki, M. & Wójcik, A. Creating a superposition of unknown quantum states. Phys. Rev. Lett. 116, 110403 (2016).

23. 23.

Li, K. et al. Experimentally superposing two pure states with partial prior knowledge. arXiv preprint arXiv:1608.04349 (2016)

24. 24.

Loss, D. & DiVincenzo, D. P. Quantum computation with quantum dots. Phys. Rev. A 57, 120–126 (1998).

25. 25.

Kane, B. E. A silicon-based nuclear spin quantum computer. Nature 393, 133–137 (1998).

26. 26.

Vrijen, R. et al. Electron-spin-resonance transistors for quantum computing in silicon-germanium heterostructures. Phys. Rev. A 62, 012306 (2000).

27. 27.

Barenco, A. et al. Elementary gates for quantum computation. Phys. Rev. A. 52, 3457–3467 (1995).

28. 28.

DiVincenzo, D. P., Bacon, D., Kempe, J., Burkard, G. & Whaley, K. B. Universal quantum computation with the exchange interaction. Nature 408, 339–342 (2000).

29. 29.

Levy, J. Universal quantum computation with spin-1/2 pairs and Heisenberg exchange. Phys. Rev. Lett. 89, 147902 (2002).

30. 30.

Costache, M. V. & Valenzuela, S. O. Experimental spin ratchet. Science 330, 1645–1648 (2010).

31. 31.

Folk, J. A., Potok, R. M., Marcus, C. M. & Umansky, V. A gate-controlled bidirectional spin filter using quantum coherence. Science 299, 679–682 (2003).

32. 32.

Hanson, R. et al. Semiconductor few-electron quantum dot operated as a bipolar spin filter. Phys. Rev. B 70, 241304 (2004).

33. 33.

Recher, P., Sukhorukov, E. V. & Loss, D. Quantum dot as spin filter and spin memory. Phys. Rev. Lett. 85, 1962–1965 (2000).

34. 34.

Bremner, M. J. et al. Practical scheme for quantum computation with any two-qubit entangling gate. Phys. Rev. Lett. 89, 247902 (2002).

35. 35.

Marvian, I. & Mann, R. B. Building all time evolutions with rotationally invariant Hamiltonians. Phys. Rev. A 78, 022304 (2008).

36. 36.

Pichler, H., Zhu, G., Seif, A., Zoller, P. & Hafezi, M. A measurement protocol for the entanglement spectrum of cold atoms. Preprint at arXiv:1605.08624 (2016).

37. 37.

Harrow, A. W. & Leung, D. W. A communication-efficient nonlocal measurement with application to communication complexity and bipartite gate capacities. IEEE Trans. Inform. Theory 57, 5504–5508 (2011).

38. 38.

Aaronson, S. Quantum copy-protection and quantum money. In Computational Complexity (CCC), 2009 IEEE 24th Annual Conference on, 229–242 (IEEE, 2009).

39. 39.

Marvian, I. & Lloyd, S. Universal quantum emulator. arXiv preprint arXiv:1606.02734 (2016).

40. 40.

Alagic, G. & Fefferman, B. On quantum obfuscation. arXiv preprint arXiv:1602.01771 (2016).

41. 41.

Ekert, A. K. et al. Direct estimations of linear and nonlinear functionals of a quantum state. Phys. Rev. Lett. 88, 217901 (2002).

## Acknowledgements

We thank Andrew Childs for suggesting the proof idea of Theorem 4, Aram Harrow, Stephen Jordan, Seth Lloyd, Iman Marvian, Ronald de Wolf, Michael Gullans, and Henry Yuen for useful discussions, and Michał Oszmaniec for pointing out the ref. 22. Part of this work was done while M.O. was visiting the University of Maryland and MIT, so he thanks both institutions for their hospitality. S.K. and C.Y.L. are funded by the Department of Defense. G.H.L. is funded by the NSF CCR and the ARO quantum computing projects. M.O. acknowledges Leverhulme Trust Early Career Fellowship (ECF-2015-256) and European Union project QALGO (Grant Agreement No. 600700) for financial support. T.J.Y. thanks the DoD, Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. The authors are grateful to the University of Maryland Libraries’ Open Access Publishing Fund and the Massachusetts Institute of Technology Open Access Publishing Fund for partial funding for open access.

## Author information

### Affiliations

1. #### Joint Center for Quantum Information and Computer Science (QuICS), University of Maryland, College Park, MD, 20742, USA

• Shelby Kimmel
•  & Cedric Yen-Yu Lin
2. #### Department of Physics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA

• Guang Hao Low
•  & Theodore J. Yoder
3. #### Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, CB3 0WA, UK

• Maris Ozols

### Contributions

All authors contributed equally.

### Competing interests

The authors declare no competing financial interest.

### Corresponding author

Correspondence to Shelby Kimmel.


text:
# How to interpret these acf and pacf plots

Following are acf and pacf plots of a monthly data series. The second plot is acf with ci.type='ma':

The persistence of high values in acf plot probably represent a long term positive trend. The question is if this represent seasonal variation?

I tried to see different sites on this topic but I am not sure if these plots show seasonality.

ACF and PACF plot analysis

Help interpreting ACF- and PACF-plots

Help understanding the following picture of ACF

Autocorrelation and partial autocorrelation interpretation

Edit: following is the graph for lag upto 60:

Following are plots of diff(my_series):

And upto lag 60:

Edit: This data is from: Is this an appropriate method to test for seasonal effects in suicide count data? Here the contributors did not consider acf and pacf plot of original or differenced series worth mentioning (so it must not be important). Only acf/pacf plots of residuals was referred to in a couple of places.

• Can you add something about your data (eg, a basic plot)? Did you try anything like stl()? Apr 18, 2015 at 17:01
• I am trying to understand how to determine seasonality from acf and pacf plots. Is review of basic plot or stl necessary for this? Can we not determine something from these plots?
– rnso
Apr 18, 2015 at 17:09
• That would be fine. For clarity, your question isn't really about what is going on w/ your data, but is about what can be understood from these plots in isolation, is that right? Apr 18, 2015 at 17:11
• Yes. I often need to determine if seasonality is present in my data so I want to understand what information can I derive from acf and pacf plots. The plots of stl function is reasonably easy to understand but not these plots.
– rnso
Apr 18, 2015 at 17:18
• Your data does indeed have some seasonality. Please see my response to @javlacalle . Apr 20, 2015 at 15:36

looking at plots in order to try to pigeonhole the data into a guessed arima model works well when 1: There are no outliers/pulses/level shifts, local time trends and no seasonal deterministic pulses in the data AND 2) when the arima model has constant parameters over time AND 3) when the error variance from the arima model has constant variance over time. When do these three things hold .... in most textbook data sets presenting the ease of arima modelling. When do 1 or more of the 3 not hold .... in every real world data set that I have ever seen . The simple answer to your question requires access to the original facts ( the historical data ) not the secondary descriptive information in your plots. But this is just my opinion!

EDITED AFTER RECEIPT OF DATA:

I was on a Greek vacation (actually doing something other than time series analysis) and was unable to analyse the SUICIDE DATA but in conjunction with this post. It is now fitting and right that I submit an analysis to follow up/prove by example my comments about multi-stage model identification strategies and the failings of simple visual analysis of simple correlation plots as "the proof is in the pudding".

Here is the ACF of the original data The PACF of the original series . AUTOBOX http://www.autobox.com/cms/ a piece of software that I have helped developed uses heuristics to identify a starting model In this case the initially identified model was found to be . Diagnostic checking of the residuals from this model suggested some model augmentation using a level shift, pulses and a seasonal pulse Note that the Level Shift is detected at or about period 164 which is nearly identical to an earlier conclusion about period 176 from @forecaster. All roads do not lead to Rome but some can get you close ! . Testing for parameter constancy rejected parameter changes over time . Checking for deterministic changes in the error variance concluded that no deterministic changes were detected in the error variance. . The Box-Cox test for the need for a power transform was positive with the conclusion that a logarithmic transform was necessary. . The final model is here . The residuals from the final model appear to be free of any autocorrelation . The plot of the final models residuals appears to be free of any Gaussian Violations . The plot of Actual/Fit/Forecasts is here with forecasts here

• Thanks for your answer. Are these assumptions so important and always so flouted in real world data that acf and pacf plots can almost never be interpreted in isolation?
– rnso
Apr 19, 2015 at 2:06
• I hate to say never BUT the assumptions that I laid out would severely complicate the visual identification process if violated. Your data set clearly ( to my old eyes ) is an example of this. Identifying an initial model , estimating and re-identifying based upon residual diagnostics is a multi-stage process not a one and done EXCEPT in trivial cases. Apr 19, 2015 at 9:47
• To reiterate following my friend stats.stackexchange.com/users/48766/javlacalle : Checking for the presence of pulses and level shifts AND seasonal pulses AND local time trends AND error variance constancy is also necessary. Apr 19, 2015 at 10:25
• (+1) Nice analysis of the data. However, what about the original question? can seasonality be identified in the data? Maybe it can be inferred from the output that you show, but I couldn't figure it out. Apr 19, 2015 at 23:04
• seasonality is present in the AR(12) term in the ARIMA model and in the seasonal pulse starting at period 98 (2003/2) Apr 20, 2015 at 1:19

Interpretation of the ACF and PACF

The slow decay of the autocorrelation function suggests the data follow a long-memory process. The duration of shocks is relatively persistent and influence the data several observations ahead. This is probably reflected by a smooth trending pattern in the data.

The ACF and PACF of order 12 are beyond the significance confidence bands. However, this does not necessarily mean the presence of an identifiable seasonal pattern. The ACF and PACF of other seasonal orders (24, 36, 48, 60) are within the confidence bands. From the graphic, it is not possible to conclude whether the significance of the ACF and PACF of order 12 is due to seasonality or transitory fluctuations.

The persistence of the ACF mentioned before suggests that first differences may be needed to render the data stationary. However, the ACF/PACF of the differenced series look suspicious, negative correlation may have been induced by the differencing filter and may not be actually appropriate. See this post for some details.

Determine if seasonality is present

The analysis of the ACF and PACF should be complemented with other tools, for example:

• Spectrum (a view to the ACF in the frequency domain), may reveal the periodicity of cycles that explain most of the variability in the data.
• Fit the basic structural time series model and check if the variance of the seasonal component is close to zero relatively to the other parameters (in R function stats::StructTS and package stsm).
• Tests for seasonality, based on seasonal dummies, seasonal cycles or those described and implemented in X-12.
• Checking for the presence of pulses and level shifts as mentioned by IrishStat is also necessary since they can distort the conclusions from the previous methods (in R the package tsoutliers can be useful to this end).
• I have added plot upto lag 60. What would be the R command for getting "differenced series"? I will add plots for diff(my_series).
– rnso
Apr 18, 2015 at 18:16
• @mso I have added major changes to my previous answer. The command for the differenced series is the function diff that you used. Apr 18, 2015 at 19:53
• javlacalle -- there were two very similar paragraphs and @rnso attempted to help by removing one. I have removed what I think is the one you wanted to replace. Could you please check that the correct paragraph was removed? Apr 19, 2015 at 1:35
• @Glen_b thanks for the editing, I've made some changes. Apr 19, 2015 at 8:18
• @ javlacalle, @IrishStat : please see the edit in my question re original data.
– rnso
Apr 19, 2015 at 10:41