text:
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 15 3 2 14.286%

## 문제

Regina is finishing her graduation work. She asks Grigory who is LaTeX expert to help her with layout.

Making layout is easy for Grigory, but he has some problems with bibliography rendering. Due to graduation work design requirements, references in bibliography must be placed in the same order as they are placed in the text of the work. Each reference has exactly one occurrence in Regina's work.

For placing reference on some source Grigory uses \cite{<reference>} construction, where <reference> is the name of the reference. An example of a text that contains three references is shown below.

The most famous characters of Pushkin's works are Onegin \cite{onegin},
Dubrovsky \cite{dubrovsky} and Tsar Saltan \cite{saltan}.

To make the bibliography, Grigory needs to place the following construction after the text of the work:

\begin{thebibliography}{99}
\bibitem{onegin} A.S.Pushkin. Eugene Onegin. 1831.
\bibitem{dubrovsky} A.S.Pushkin. Dubrovsky. 1841.
\bibitem{saltan} A.S.Pushkin. The Tale of Tsar Saltan. 1832.
\end{thebibliography}

Here 99 is the maximal number of references and reference description is written after \bibitem{<reference>} construction.

Text is quite large and Grigory is quite lazy, so he doesn't want to check the order of references. Therefore he asks you to write a program that can analyze the text and the bibliography. If the bibliography is incorrect, your program must print the correct new one.

## 입력

Input contains the text of the work that consists of lowercase and uppercase English letters, ends of lines, spaces, <<.>>, <<,>>, <<'>> (ASCII code 39) characters and \cite{<reference>} constructions. Here <reference> is a nonempty string of lowercase English letters that has the length at most $100$. ASCII code of <<\textbackslash>> character is 92.

Each \cite{<reference>} construction starts at a new line or after a space character. The text of the work can contain empty lines.

The following line after the text is equal to \begin{thebibliography}{99}. Each of the following lines contains a description of a source in the described format. Description consists of the same characters as the text of work. Length of each description isn't greater than $100$ characters. The following line after the bibliography is \end{thebibliography}{99}.

It's guaranteed that:

• The total number of references is not greater than 99.
• There is at least one reference in the text.
• If the text contains some reference, the bibliography contains that reference too.
• The number of \cite{<reference>} constructions in the text is the same as the number of \bibitem{<reference>} constructions in the bibliography.
• The references in the text are different.
• The total number of lines in the input isn't greater than $10^5$.
• The sum of lengths of the lines in the text isn't greater than $10^5$.
• Input doesn't contain two consecutive space characters. The first and the last characters of each line aren't spaces.

## 출력

Print Correct if the bibliography from the input is correct and Incorrect otherwise.

In the second case print the correct bibliography in the required format then. The source descriptions must be the same as defined in input.

## 예제 입력 1

The most famous characters of Pushkin's works are Onegin \cite{onegin},
Dubrovsky \cite{dubrovsky} and Tsar Saltan \cite{saltan}.

\begin{thebibliography}{99}
\bibitem{saltan} A.S.Pushkin. The Tale of Tsar Saltan. 1832.
\bibitem{onegin} A.S.Pushkin. Eugene Onegin. 1831.
\bibitem{dubrovsky} A.S.Pushkin. Dubrovsky. 1841.
\end{thebibliography}

## 예제 출력 1

Incorrect
\begin{thebibliography}{99}
\bibitem{onegin} A.S.Pushkin. Eugene Onegin. 1831.
\bibitem{dubrovsky} A.S.Pushkin. Dubrovsky. 1841.
\bibitem{saltan} A.S.Pushkin. The Tale of Tsar Saltan. 1832.
\end{thebibliography}

## 예제 입력 2

The most famous characters of Pushkin's works are Onegin \cite{onegin},
Dubrovsky \cite{dubrovsky} and Tsar Saltan \cite{saltan}.
\begin{thebibliography}{99}
\bibitem{onegin} A.S.Pushkin. Eugene Onegin. 1831.
\bibitem{dubrovsky} A.S.Pushkin. Dubrovsky. 1841.
\bibitem{saltan} A.S.Pushkin. The Tale of Tsar Saltan. 1832.
\end{thebibliography}

## 예제 출력 2

Correct


text:
# Showing a 2D continuous function can be approximated by a finite sum of “simpler” continuous functions

Show that given a real-valued continuous function $f$ on $[0,1] \times [0,1]$ and an $\epsilon > 0,$ there exist real-valued continuous functions $g_1, \dots, g_n$ and $h_1 , \dots, h_n$ on $[0,1]$ such that for some finite $n\geq 1,$ $$\bigg| f(x,y) - \sum_{i=1}^n g_i(x)h_i(y) \bigg| \leq \epsilon, \;\;\;\; 0 \leq x,y \leq 1.$$

I believe the Stone-Weierstrass approximation could be useful here, as I think this is just a 2D analogue, but I am not sure what the proof would consist of. Proving the Stone-Weierstrass theorem in 1D can consist of using convolutions with an approximate identity which is done in Rudin, I've seen proofs that use Bernstein polynomials, and I remember seeing a rather concise proof that used PDE's, but none of these seem like what would be expected on a qualifier.

Perhaps this problem doesn't call for the Weierstrass approximation?
Does anyone have any suggestions?

You can indeed use Stone-Weierstrass, but if all you require of the $g_i$s and $h_i$s is that they're continuous, less than that can do.

Select some $m$, and for $0\le i\le m$, define $$k_i : [0,1]\to\mathbb R : x \mapsto \max(0,1-|i-mx|)$$

 |      /\
_|_____/  \______
0     i/m      1

Then, $$\sum_{0\le i\le m} k_i(x) = 1$$ for $x\in[0,1]$, and therefore $$\sum_{\begin{matrix}0\le i\le m\\0\le j\le m\end{matrix}} k_i(x)k_j(y) = 1$$ for $(x,y)\in[0,1]^2$, and $k_i(x)k_j(y)$ has its support bounded by $1/m$ away from $(i/m,j/m)$.

Now, since $f$ is continuous and its domain is compact, it is uniformly continuous, so there is an $m$ such that $f$ doesn't vary by more than $\varepsilon$ when $(x,y)$ varies by up to $1/m$ in each coordinate. But then $$\tilde f(x,y) = \sum_{\begin{matrix}0\le i\le m\\0\le j\le m\end{matrix}} \underbrace{f(\tfrac im,\tfrac jm)k_i(x)}_{g_{ij}(x)} \cdot \underbrace{k_j(y)}_{h_{ij}(y)}$$ approximates $f(x,y)$, because its value is always some weighted average of values of $f(x,y)$ taken no more than $1/m$ away in each coordinate.

• Impressive! Very clear I see exactly what is going on... thanks! – Merkh Jun 27 '16 at 12:40

format: plain


text:
# Adaptive experimental design for one-qubit state estimation with finite data based on a statistical update criterion

We consider 1-qubit mixed quantum state estimation by adaptively updating measurements according to previously obtained outcomes and measurement settings. Updates are determined by the average-variance-optimality (A-optimality) criterion, known in the classical theory of experimental design and applied here to quantum state estimation. In general, A-optimization is a nonlinear minimization problem; however, we find an analytic solution for 1-qubit state estimation using projective measurements, reducing computational effort. We compare numerically two adaptive and two nonadaptive schemes for finite data sets and show that the A-optimality criterion gives more precise estimates than standard quantum tomography.

## Authors

• 1 publication
• 1 publication
• 1 publication
• ### Neural network state estimation for full quantum state tomography

An efficient state estimation model, neural network estimation (NNE), em...
11/16/2018 ∙ by Qian Xu, et al. ∙ 0

• ### Quantum machine learning with adaptive linear optics

We study supervised learning algorithms in which a quantum device is use...
02/08/2021 ∙ by Ulysse Chabaud, et al. ∙ 0

• ### Machine learning assisted quantum state estimation

We build a general quantum state tomography framework that makes use of ...
03/06/2020 ∙ by Sanjaya Lohani, et al. ∙ 0

• ### Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design

Experimental design is a classical problem in statistics and has also fo...
02/23/2018 ∙ by Mohit Singh, et al. ∙ 0

• ### Machine learning pipeline for quantum state estimation with incomplete measurements

Two-qubit systems typically employ 36 projective measurements for high-f...
12/05/2020 ∙ by Onur Danaci, et al. ∙ 0

• ### Adaptive Quantum State Tomography with Neural Networks

Quantum State Tomography is the task of determining an unknown quantum s...
12/17/2018 ∙ by Yihui Quek, et al. ∙ 0

• ### Neural-Network Heuristics for Adaptive Bayesian Quantum Estimation

Quantum metrology promises unprecedented measurement precision but suffe...
03/04/2020 ∙ by Lukas J. Fiderer, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## I Introduction

For successful experimental implementation of any quantum protocol, the quantum states and operations involved must be confirmed to be sufficiently closed to their theoretical targets. One way to obtain such a confirmation is to perform another experiment and from the obtained data make an estimate of the quantum operator involved. Statistically, this is a constrained multi-parameter estimation problem – the quantum estimation problem – where we assume we are given a finite number of identical copies of a quantum state or operation, we perform measurements whose mathematical description is assumed to be known, and from the outcome statistics we make our estimate. Due to the probabilistic behavior of the measurement outcomes and the finiteness of the number of measurement trials, there always exist statistical errors in any quantum estimate. The size of the error depends on the choice of measurements and the estimation procedure. In statistics, the former is called an experimental design, while the latter is called an estimator. It is, therefore, a key aim of both classical and quantum estimation theory to find a combination of experimental design and estimator which gives us more precise estimation results using fewer measurement trials.

A standard combination in quantum information experiments is that of quantum tomography and maximum likelihood estimator. Although the term “quantum tomography” can be used in several different contexts, we use it to mean an experimental design in which an independently and identically prepared set of measurements are used throughout the entire experiment Paris and Řeháček (2004). The performance of different choices for the set of tomographic measurements have been studied, in, for example, de Burgh et al. (2008); Nunn et al. (2010). This of course raises the question of the performance of adaptive experimental designs, in which the measurements performed from trial to trial are not independent, and are chosen according to previous measurement settings and the outcomes obtained. Clearly, adaptive experimental designs are a superset of the nonadaptive ones, and as such can potentially achieve higher performance.

Adaptive designs are characterized by the way in which measurements are related from trial to trial, referred to as an update criterion. Previously proposed update criteria include those based on asymptotic statistical estimation theory (Fisher information) Nagaoka (1988, 2005); Fujiwara (2006), direct calculations of the estimates expected to be obtained in the next measurement Fischer et al. (2000); Happ and Freyberger (2008), mutually unbiased basis Happ and Freyberger (2011), as well as Bayesian estimators and Shannon entropy Fischer et al. (2000); Fischer and Freyberger (2000); Huszár and Houlsby (2011). Theoretical investigations report that some of the proposed update criteria give more precise estimates than nonadaptive quantum tomography, and an experimental implementation of the update criterion proposed in Fischer et al. (2000) in an ion trap system has been performed Hannemann et al. (2002). If denotes the number of measurement trials and is sufficiently large, it is known in 1-qubit state estimation that the expectation value of infidelity averaged over states, a measure of the estimation error, can decrease at best as in a nonadaptive experiment Bagan et al. (2004), compared to in adaptive experiments Bagan et al. (2006a). Most of the proposed update criteria, however, have high computational cost that makes real experiments infeasible. In this paper, we propose an adaptive experimental design whose average expected infidelity decreases as and whose update criterion, known as average-variance optimality (A-optimality) in classical statistics, has low computational cost for 1-qubit state estimation.

The paper is structured as follows. In Sec. II we lay out the notation and terminology that will be used throughout in this paper, by explaining basic concepts in adaptive experimental design, statistical parameter estimation, and A-optimality criteria. We also give a brief review of some of the proposed update criteria in the literature. In Sec. III we give the explicit form of the analytic solution of the A-optimal update criterion, (the derivation is given in the Appendix). This analytic solution makes it possible to reduce the computational cost for updating measurements, and using this we compare several estimation schemes numerically, showing that our proposal is more precise than standard quantum tomography. In Sec. IV, we discuss the feasibility of implementing the proposed scheme experimentally. A summary appears in Sec. V.

## Ii Preliminaries

### ii.1 Notation and terminology

We will adopt terms from the statistical literature, since they afford us the precision we need to properly discuss details of estimation schemes that can sometimes be subtle. In this subsection we will introduce a formalism for quantum estimation using that terminology, and apply it in a survey of several existing update criteria in Sec. II.5.

#### ii.1.1 Model selection

In statistical estimation theory, a statistical model is defined as a set of probability distributions, and we assume that the true probability distribution of interest is included in the set. In the quantum case, a probability distribution is determined by the state of the system and the action of the measurement on the state system. Let

be a Hilbert space with finite dimension and be the set of all density matrices acting on that Hilbert space. Suppose we know that the object we are trying to estimate lies in a subset , that is, the true density matrix is included in . For example, when we know that the true state is pure, is the set of all pure states. In this paper, we consider mixed state estimation, and we assume that in our finite measurement trials we prepare identical copies of an unknown state .

#### ii.1.2 Experimental design

A probability distribution of outcomes in quantum measurement requires not only a density matrix, but also a positive operator valued measure (POVM), , where is the set of outcomes. When the measurement is characterized by a POVM and the measured quantum state is characterized by a density matrix , the probability distribution of the outcomes is given by Born’s rule , where denotes the trace operation with respect to , (note that in the next subsection, a different trace operation represented as , is introduced).

We consider sequential measurements, as opposed to collective measurements, on copies of . We will index measurement trials using subscripts , and sequences using superscripts. Thus, for some symbol , is its value taken at the -th trial, while is the sequence . We will also try to use calligraphic fonts for supersets. Adaptivity in our sense means that the POVM performed at -th trial can depend on all the previous trials’ outcomes and POVMs.

The measurement class is the set of POVMs which are available at the -th trial. We choose the -th POVM, from , where denotes the set of measurement outcomes for the -th trial. When it is independent of the trial, as is usually the case, we omit the index, using for the measurement class and for the outcome set. Let denote the sequence of outcomes obtained up to the -th trial, where . We will denote the pair of measurement performed and outcome obtained by , and refer to it as the data for trial . The sequence of data up to trial is thus . After the -th measurement, we choose the next, -th, POVM according to the previously obtained data. Let denote the map from the data to the next measurement, that is, , . We call the measurement update criterion for the -th trial and the measurement update rule. Note that is a map from to and corresponds to the choice of the first measurement.

#### ii.1.3 Estimator

An estimator is a set of maps from the data to the model space, so that . The estimated density matrix is called the -th estimate. We will often omit the data dependency. In this paper we use a maximum likelihood estimator defined as

 ρMLn := argmaxσ∈Op(Dn|σ), (1)

where

 p(Dn|σ) := Tr[Π1,x1⊗Π2,x2⊗⋯⊗Πn,xnσ⊗n]. (2)

A quintuplet specifies an estimation scheme. A sketch of the procedure for a generic adaptive quantum estimation scheme is given in Fig. 1.

#### ii.1.4 Evaluation

In order to evaluate the precision of estimates of the true density matrix, we introduce a loss function

(sometimes called a cost function). A loss function

is a map from to such that (i) and (ii)

. For example, the trace-distance and the infidelity (one minus the fidelity) are loss functions for density matrices. The outcomes of quantum measurements are random variables, and the value of the loss function between an estimate and the true density matrix is also a random variable. Thus, in order to evaluate the precision of the estimator (not the estimate) for the true density matrix, we use the statistical expectation value of the loss function, called an

expected loss (sometimes called a risk function) Note1 . The explicit form is given by

 ¯ΔN(uN,ρest|ρ) := ∑DN∈DNp(DN|ρ)Δ(ρestN(DN),ρ). (3)

The value of the expected loss depends on the choice of the estimator as well as the true density matrix. The latter is of course unknown in an experiment, and there are at least two approaches to eliminate its dependence, namely the average and the maximal (or worst case) expected loss, given explicitly by

 ¯ΔaveN(uN,ρest) := ∫ρ∈Odμ(ρ)¯ΔN(uN,ρest|ρ), (4) ¯ΔmaxN(uN,ρest) := maxρ∈O¯ΔN(uN,ρest|ρ). (5)

where is a probability measure on . The task in this paper is to find a combination of a measurement update rule and estimator with average expected loss as small as possible.

### ii.2 A generalized Cramér-Rao inequality

The A-optimality criterion is a measurement update criterion based on the asymptotic theory of statistical parameter estimation Watanabe et al. (2005); Pukelsheim (2006). In this subsection we introduce a few basic results of the asymptotic theory. First let us parametrize the state space . Any density matrix on -dimensional Hilbert space can be parametrized by real numbers, , i.e. . In the case, we take , where , are the Pauli matrices, and

, is called the Bloch vector. The estimation of

is equivalent to the estimation of , and we let denote the estimator. Estimates of a density matrix and of a Bloch vector are related as .

For any estimator , any number of measurement trials , and any positive semidefinite matrix , the inequality

 ∑DN∈DNp(DN|s)[sestN(DN)−s]TH(s)[sestN(DN)−s] ≥tr[H(s)GN(uN,sest,s)TFN(uN,s)−1GN(uN,sest,s)] (6)

holds, where

 p(DN|s) :=p(DN|ρ(s)), (7) GN(uN,sest,s) :=∇s∑DN∈DNp(DN|s)sestTN(DN), (8) FN(uN,s) :=∑DN∈DN∇sp(DN|s)∇Tsp(DN|s)p(DN|s), (9)

and denotes the trace operation with respect to the parameter space. Eq.(6) is a known generalization of the Cramér-Rao inequality Rao (2002), and we give a simple proof in Appendix B. is a positive semidefinite matrix called the Fisher matrix of the probability distribution .

If the estimate converges to the true parameter, i.e., as with probability 1, the LHS of Eq.(6) converges to 0 and therefore the RHS should converge to 0. In this case, if we assume the exchangeability of the limit and derivative, the matrix

converges to the identity matrix

, and the quantity defined as

 KN(uN,s):=tr[H(s)FN(uN,s)−1] (10)

converges to . This can be interpreted as a lower bound of the weighted (by ) mean squared error when is sufficiently large. It is known that under certain regularity conditions, a maximum likelihood estimator achieves the equality of Eq.(6) asymptotically. For a given , it would be wise to choose a measurement update rule which makes the value of as small as possible. This is the guiding principle of the A-optimality criterion.

### ii.3 A-optimality criteria

We move on to the explanation of the procedure of A-optimality. The “A” stands for “average-variance” Pukelsheim (2006). According to the asymptotic theory of statistical parameter estimation described in the previous subsection, we wish to minimize the value of . Suppose that we perform trials and obtained the data sequence . We would like to choose the POVM minimizing in as the next, -th, measurement. When we consider minimizing this function, there are two problems. In order to avoid them, we introduce two approximations. The first problem is that the minimized function depends on the true parameter . Of course the true parameter is unknown in parameter estimation problems, and we must use an estimate in the update criterion, , instead. The mesurement update estimator is not necessarily the same as . The second problem is that unlike the independent and identically distributed (i.i.d.) measurement case, calculation of the Fisher matrix in the adaptive case requires summing over an exponential amount of data, and is computationally intensive. To avoid this problem, we approximate the sum over all possible measurements by that over only those measurements that have been performed:

 Fn+1(un+1,s) ≈~Fn+1(un+1,s|Dn):=n+1∑i=1F(Πi,s), (11)

where

 F(Πi,s) :=∑xi∈Xi∇sp(xi;Πi|s)∇Tsp(xi;Πi|s)p(xi;Πi|s), (12) Πi =ui(Di−1), i=1,⋯,n+1. (13)

The matrix is the Fisher matrix for the -th measurement probability distribution , and is the sum of the Fisher matrices from the first to the ()-th trial. Instead of minimizing , we consider the minimization of

 ~Kn+1(un+1,s|Dn):=tr[H(s)~Fn+1(un+1,s|Dn)−1]. (14)

It is known that the convergence of to is part of a sufficient condition for the convergence of a maximum likelihood estimator Hall and Heyde (1980), and this justifies the use of this second approximation. We explain the relationship between the conditional and unconditional Fisher matrices with respect to the estimator’s convergence in Appendix C. After making these two approximations, we define the A-optimality criterion as

 ΠA\scriptsize-optn+1 :=uA\scriptsize-optn+1(Dn) =argminΠn+1∈Mn+1tr[H(^sestn)~Fn+1(un+1,^sestn|Dn)−1]. (15)

Finding is a nonlinear minimization problem with high computational cost in general. In this paper, we derive the analytic solution of Eq. (15) in the 1-qubit case, reducing the computational cost significantly.

### ii.4 Estimation setting

We consider a 1-qubit mixed state estimation problem, so that . We identify the Bloch parameter space with , where we restrict the true state space to be strictly the interior in order to avoid the possible divergence of the Fisher matrix. Suppose that we can choose any rank-1 projective measurement in each trial. Let denote the POVM corresponding to the projective measurement onto the -axis , whose elements can be represented as

 Π±(a)=12(1±a⋅σ). (16)

This is the Bloch parametrization of projective measurements. We identify the set of parameters with the measurement class .

For our loss functions, we use both the squared Hilbert-Schmidt distance and the infidelity Bagan et al. (2004):

 ΔHS(s,s′): =12Tr[(ρ(s)−ρ(s′))2] (17) =14(s−s′)2, (18) ΔIF(s,s′): =1−Tr[√√ρ(s)ρ(s′)√ρ(s)]2 (19) =12(1−s⋅s′−√1−∥s∥2√1−∥s′∥2). (20)

We note that the Hilbert-Schmidt distance coincides with the trace distance in a 1-qubit system. The asymptotic behavior of the average expected fidelity is known in the 1-qubit state estimation case Bagan et al. (2004, 2006b, 2006a). The measure used for calculating this average is the Bures distribution, . If we limit our available measurements to be sequential and independent (i.e., nonadaptive), behaves at best as Bagan et al. (2004, 2006b). On the other hand, if we are allowed to use adaptive, separable, or collective measurements, can behave as Bagan et al. (2006a). In Bagan et al. (2004, 2006b, 2006a), the coefficient of the dominant term in the asymptotic limit is also derived.

In Sec. III.2.1, we show numerical results. A maximum likelihood estimator is used, and it is shown that the average expected infidelity of an A-optimal scheme behaves as , illustrating that the A-optimality criterion is indeed making use of adaptation to outperform nonadaptive schemes.

### ii.5 Survey of some other update criteria

We briefly review some of the other adaptive measurement update criteria proposed in the literature, using our terminology and notation introduced in the previous subsections.

Before explaining update criteria that are performed at each and every trial, such as A-optimality, we briefly review a simpler update criterion. The two-step adaptation criterion requires the measurement update only once during a measurement sequence. We have

 un+1(Dn)={Π1stif n

Thus, for all trials up to and including trial a fixed POVM is performed, and an estimate is calculated from the obtained data. Using that data we choose a new POVM for the remaining copies. In Hayashi and Matsumoto (1998); Hayashi and Matsumoto (2005); Gill and Massar (2000); Bagan et al. (2006a), two-step adaptation criteria are used to prove mathematically an asymptotic bound for weighted mean squared errors in 1-qubit state estimation. In Řeháček et al. (2004); Petz et al. (2007), some numerical results are shown for a few two-step adaptation schemes.

#### ii.5.2 N88 criterion

In Nagaoka (1988, 2005); Fujiwara (2006), an update criterion based on the Cramér-Rao inequality is proposed. The update criterion is given by

 un+1(Dn) =argminΠ∈Mn+1tr[H(^sestn)F(Π,^sestn)−1]. (22)

The difference from the A-optimality criterion is that in Eq. (22) the Fisher information matrix used in the update does not take into account all measurements, but about only the -th measurement. The advantage of course is that this reduces the computational cost of updates. The disadvantage is that when consists of informationally incomplete POVMs, as is the case in most experiments, the estimates cannot converge to the true state. As explained in Sec. II.4, in this paper is restricted to rank-1 projective measurements, and in this setting Eq. (22) does not work well.

#### ii.5.3 FKF00 criteria

In Fischer et al. (2000), two update criteria are proposed.

1. The first criterion is based on the Shannon entropy of the estimated measurement probability distribution, and is given by

 un+1 (Dn)=argmaxΠ∈Mn+1 (23)
2. The second criterion uses a third state estimator such that

 (un+1 (Dn),^^ρestn(Dn))=argmax(Π,σ)∈Mn+1×O (∑x∈Xn+1p(x;Π|^ρestn(Dn))Δ(^ρestn+1(Dn+1),σ)). (24)

Numerical simulation is performed for the case where is the set of 1-qubit pure states and is the set of projective measurements, while is a biased maximum likelihood estimator, is a Bayesian estimator up to . Average (not expected) infidelity is used as the evaluation function.

#### ii.5.4 HF08 criterion

In Happ and Freyberger (2008), an update criterion given by

 un+1 (Dn)=argmaxΠ∈Mn+1 (∫Odρ∑x∈Xn+1p(x;Π|ρ)Δ(^ρestn+1(Dn+1),ρ)), (25)

is proposed. A numerical simulation is performed in Happ and Freyberger (2008), where the setting is that is the set of 1-qubit pure states, is a set of parity measurements using an ancilla system, and and are maximum likelihood estimators. The behavior of the average expected fidelity is numerically analyzed up to .

#### ii.5.5 HF11 criterion

An update criterion proposed in Happ and Freyberger (2011) is given by

 un+1 (Dn)=argmaxΠ∈Mn+1 (−∑x∈Xn+1n∑i=1Tr[Πi,xiΠx]lnTr[Πi,xiΠx]), (26)

and the estimator is defined as

 ρestn(Dn)=argmaxρ∈OTr[ρ¯ρ(Dn)], (27) ¯ρ(Dn)=1nn∑i=1Πi,xi. (28)

In the numerical simulations, the estimation setting is such that is the set of pure states on -dimensional Hilbert space , and is the set of projective measurements on . Numerical simulations of average expected fidelity are shown for and , all up to .

#### ii.5.6 FF00 criterion

In Fischer and Freyberger (2000), an update criterion based on Bayesian estimation and Shannon entropy is proposed. Let denote a prior distribution on . The update criterion is

 un+1 (Dn)=argmaxΠ∈Mn+1 (∑x∈Xn+1pave(x;Π|Dn)∫OdρP(ρ|Dn+1)lnP(ρ|Dn+1)P(ρ|Dn)) (29) (Dn)=argmaxΠ∈Mn+1 (−∫ρ∈OdρP(ρ|Dn)lnP(ρ|Dn)+ ∑x∈Xn+1pave(x;Π|Dn)∫OdρP(ρ|Dn+1)lnP(ρ|Dn+1)) (30)

where

 pave(x;Π|Dn):=∫OdρP(ρ|Dn)p(x;Π|ρ), (31) P(ρ|Dn):=P(ρ)p(Dn|ρ)∫OdσP(σ)p(Dn|σ). (32)

In Fischer and Freyberger (2000), the case in which is the set of 1-qubit mixed states and is the set of projective measurements is numerically analyzed up to . The evaluation function used is the average (not expected) infidelity.

#### ii.5.7 HH11 criterion

In Huszár and Houlsby (2011), an update criterion given by

 un+1 (Dn)=argmaxΠ∈Mn+1(−∑x∈Xn+1pave(x;Π|Dn)lnpave(x;Π|Dn) +∫OdρP(ρ|Dn)∑x∈Xn+1p(x;Π|ρ)lnp(x;Π|ρ)), (33)

is proposed, where Eqs. (31) and (32) have been used. From a simple calculation, we can see that the criteria defined in Eq. (30) and in Eq. (33) are equivalent. This criterion involves an integration which requires high computational cost. In Huszár and Houlsby (2011), a special technique for calculating the integral, called a sequential importance sampling method, is used in order to reduce that computational cost. The authors performed numerical simulation for the case in which is the set of 1-qubit mixed states and are projective measurements up to . They also considered the case in which is the set of 2-qubit states and are a set of mutually unbiased bases, a set of pairwise Pauli measurements, and a set of separable measurements up to . The evaluation function is the average expected infidelity, and it is shown that their scheme is more precise than standard quantum tomography. In Sec. III.2.1, we point out that our numerical results for 1-qubit show that A-optimality gives even more precise estimates than those given by Eq. (33), at least from to .

## Iii Results and analysis

As explained in Sec. II.4, we consider the A-optimality criterion for 1-qubit state estimation using projective measurements. In Sec. III.1 we give the analytic solution, and in Sec. III.2 we show the results of numerical simulations.

### iii.1 Analytic solution for A-optimality in 1-qubit state estimation

First, we give the explicit form of the Fisher matrix for projective measurements. The probability distribution for the rank-1 projective measurement is given by

 p(±;a|s) =12(1±s⋅a), (34)

and the Fisher matrix is

 F(a,s)= ∇sp(+;a|s)∇Tsp(+;a|s)p(+;a|s) (35) +∇sp(−;a|s)∇Tsp(−;a|s)p(−;a|s) = aaT1−(a⋅s)2. (36)

In this case, Eq. (15) is rewritten in the Bloch vector representation as

 aA\scriptsize-optn+1:=argmina∈Atr[H(^sestn){~Fn(an,^sestn|Dn)+F(a,^sestn)}−1]. (37)

We present the analytic solution of Eq.(37) in the form of the following theorem.

###### Theorem 1

Given a sequence of data , the -th estimate , and a real positive matrix , the A-optimal POVM Bloch vector is given by

 aA\scriptsize-optn+1=Bnemin(Cn)∥Bnemin(Cn)∥, (38)

where

 Bn =√~Fn(an,^sestn|Dn)H(^sestn)−1~Fn(an,^sestn|Dn), (39) Cn =Bn(I−^sestn^sestTn+~Fn(an,^sestn|Dn)−1)Bn, (40)

is the eigenvector of the matrix

corresponding to the minimal eigenvalue, and

is the identity in the parameter space.

We give the proof of Theorem 1 in Appendix A.

In Eq. (40), the inverse of the matrix appears. In the proof of Theorem 1, the invertibility of is assumed. The invertibility of is equivalent to the condition that is a basis of . When we choose the second and third measurements, and are not invertible. Thus the update scheme does not apply to these steps, and the choices are arbitrary. One simple choice is to perform -, -, and -projective measurements at the first, second and third trials respectively, and this can be shown to satisfy Theorem 1 as follows. The choice of the first measurement is always arbitrary, and we choose , a -projective measurement. Then for any true Bloch vector the rank of is , and if we interpret the inverse matrix in Eq. (40) as a generalized inverse matrix, is a rank matrix with minimal eigenvalues . The supports of , , and are the span of . Therefore is an arbitrary vector in the -dimensional space spanned by and , and we choose . Then using the same logic, the third measurement is fixed to .

From the explicit formulae of the squared Hilbert-Schmidt distance and infidelity in Eqs. (18) and (20), we have

 ΔHS(s,s′) =(s′−s)T14I(s′−s), (41) ΔIF(s,s′) =(s′−s)T14(I+ssT1−∥s∥2)(s′−s) +O(∥s′−s∥3). (42)

Therefore when we use the Hilbert-Schmidt distance as our loss function, we substitute and into Eqs.(38), (39), and (40) to obtain

 Bn =~Fn(an,^sestn|Dn), (43) Cn =~Fn(an,^sestn|Dn)(I−^sestn^sestTn)~Fn(an,^sestn|Dn) +~Fn(an,^sestn|Dn), (44)

and we do not need to explicitly calculate the inverse or square root matrices for A-optimality. On the other hand, when our loss function is the infidelity, we must use and .

### iii.2 Numerical simulation

We performed Monte Carlo simulations of the following four experimental designs described in detail below; A-optimal adaptive scheme for the squared Hilbert-Schmidt distance, the same for infidelity, XYZ repetition, and uniformly random selection.

A-optimality for the squared Hilbert-Schmidt distance is the adaptive scheme defined by Eq.(37) with . Similarly, A-optimality for the infidelity is that with . As explained in the previous subsection, the choice of measurement Bloch vectors at the first and second trials is arbitrary; we choose and , i.e., at the first trial we perform the projective measurement of , and that of at the second — the third trial is automatically the projective measurement of , corresponding to . The XYZ repetition scheme is nonadaptive, in which we repeat the measurements of , , and , corresponding to standard quantum state tomography. Uniformly random selection is also nonadaptive, where at each trial we choose the next measurement direction randomly on the Bloch surface, according to the SO(3) Haar measure. For consistency with the other three schemes, we fix the first, second and third measurements to be the projective measurements of , respectively, and randomly select directions from the fourth trial on.

We choose a maximum likelihood estimator in all four experimental designs. It is known that the estimators minimizing and are Bayesian estimators Bagan et al. (2004); Blume-Kohout (2010), but the integrations necessary for Bayesian estimation take too much computation time. For the two A-optimality criteria, we choose both the real and the dummy estimators to be maximum likelihood, . We used a Newton-Raphson method to solve the (log-)likelihood equation and the completely mixed state as the initial point of the iterative method. When a search point came out of the Bloch sphere during the procedure, we chose the previous point (included in the sphere) as the estimate.

In the following subsections, we show the plots for two loss functions; the squared Hilbert-Schmidt distance and infidelity . The average expected losses are shown in Sec. III.2.1, and pointwise expected losses are shown in Sec. III.2.2. In the both subsections, the line styles are fixed as follows: solid (black) line for A-optimality for the squared Hilbert-Schmidt distance (AHS), dashed (red) line for A-optimality for the infidelity (AIF), chain (blue) line for XYZ repetition (XYZ), Dotted (green) line for Uniformly random selection (URS).

#### iii.2.1 Average expected losses

We analyse the average behaviour of the estimation errors over the Bloch sphere. The integration for averaging is approximated by a Monte Carlo routine, and the statistical expectation is approximated by an arithmetric mean using pseudo-random numbers.

Figure 2 shows the average expected loss functions against the number of trials (the horizontal and vertical axes are both logarithmic scale): (HS-Bures) integrated via the Bures distribution , (HS-Euclid) integrated via the Euclidean distribution , (IF-Bures) integrated via , and (IF-Euclid) integrated via . Fig. 2 (HS-Bures) and (HS-Euclid) shows that the estimation errors of the four experimental designs are almost equivalent from the viewpoint of the squared Hilbert-Schmidt distance. As depicted in (HS-Bures), the estimation errors of the two A-optimality schemes are slightly larger than the other nonadaptive schemes; as we show in the next subsection (pointwise analysis), this gap decreases as becomes larger. On the other hand, Fig. 2 (IF-Bures) and (IF-Euclid) show the explicit gap between the adaptive and nonadaptive schemes. The gradients of the curves begin to differentiate from around , and as depicted in (IF-Bures), the gradients of XYZ and URS are almost around . This means that the average expected infidelity behaves as

and is consistent with the result of the asymptotic analysis presented in

Bagan et al. (2004). On the other hand, the gradients of AHS and AIF are greater than the nonadaptive limit , indicating that AHS and AIF make good use of adaptive resources. Around the gradient of AIF is almost , which is the bound for adaptive experimental designs Bagan et al. (2006a).

Let us compare the estimation errors of A-optimality and the HH11 criteria explained in Sec. II.5.6. From Fig. 2 (IF-Bures), the average expected infidelity of AHS and AIF are and at . On the other hand, the corresponding amount for the HH11 criterion can be estimated roughly from Fig. 2 (a) in Huszár and Houlsby (2011) to be . This implies that for 1-qubit state estimation, the average expected infidelity of the A-optimality criterion is about two-times smaller than that of Eq. (33), at least around .

#### iii.2.2 Pointwise expected losses

Next, we analyse the behaviour of the estimation errors at several true Bloch vectors . Figure 3 shows the pointwise expected loss functions against the number of trials (the horizontal and vertical axes are both logarithmic scale): (HS-P1), (HS-P2), and (HS-P3) are plots of the expected squared Hilbert-Schmidt distances for given by , and (IF-P1), (IF-P2), and (IF-P3) are the expected infidelities for the same three true states, respectively.

As depicted in (HS-P1) and (IF-P1), the estimation errors of all four schemes are almost equivalent for the completely mixed state, . As the Bloch radius becomes larger, the differences between the four schemes become clearer. Figure 3 (HS-P2) and (HS-P3) are the plots of the expected squared Hilbert-Schmidt distances at a high purity point, . In the region of to around , the squared Hilbert-Schmidt error of the two adaptive schemes is larger than that of the two nonadaptive schemes. In particular, the error of AHS is larger that that of AIF; this might seem strange, but in the region of , the error of AHS becomes smaller than that of AIF, indeed it eventually becomes the smallest of the four schemes. We believe that there are two reasons for A-optimality’s large error for small . First, the A-optimality criterion is based on an asymptotic theory of statistical estimation. When the number of measurement trials is small, the Cramér-Rao bound is not necessary suitable for characterizing estimation errors. Second, it uses a dummy estimator in the measurement update. When is small, is not a good estimate, and thus the choice of the next measurements can be unreliable. Of course, when becomes sufficiently large, both of these problems are alleviated.

The gap between the estimation errors of adaptive and nonadaptive schemes becomes smaller as becomes larger in (HS-P2) and (HS-P3), while it grows in (IF-P2) and (IF-P3). Only the XYZ scheme changes dramatically between (IF-P2) and (IF-P3); the other three schemes do not because AHS, AIF, and URS are invariant under rotation of the true Bloch vector (for very small , there are differences, and these are because the first three measurements are fixed to -projective measurements and not rotationally invariant). Figure 3 (IF-P2) is the case in which the directions of the measurement and the true Bloch vector are matched (to ). In this case, XYZ is the best scheme, exhibiting the smallest estimation error. Around , the estimation error of AIF becomes as small as that of XYZ. That of AHS is smaller than URS, but larger than the other two schemes. We believe that this is because the selected Hessian matrix used in the update routine is unsuitable for the loss function in (IF-P2) (and (IF-P3)). Figure 3 (IF-P3) is the case in which the directions of the measurement and the true Bloch vector are the most discrepant (for a fixed purity). In this case, the estimation errors of XYZ and URS are almost the same and behave as , and those of the adaptive schemes are smaller than those of the nonadaptive ones, (this behavior of expected infidelity for i.i.d. measurements is discussed in Bagan et al. (2006a); de Burgh et al. (2008), and a detailed analysis will appear in Sugiyama et al. ). When we consider the whole Bloch sphere, of course the cases in which the direction of XYZ measurements and the Bloch vector are matched are few, and therefore the average expected infidelities of AHS and AIF are smaller than those of XYZ and URS. This also indicates that the adaptive schemes have better worst-case performance (lower , Eq. (5)) than the nonadaptive schemes.

#### iii.2.3 Purity dependence

Figure 4 shows the purity dependence of the average expected infidelity at . The average is taken over all directions and for each Bloch radius . It indicates that the average expected infidelities of the two adaptive schemes are smaller than those of the two nonadaptive schemes. The appearance of peaks for XYZ and URS is discussed in Appendix D.

#### iii.2.4 Measurement sequences

Figure 5 is a plot of the measurement Bloch vectors at (left column), (middle column), and (right column) for runs. The true state is , and the upper three subplots are AHS while the lower three are AIF. Figure 5 shows that the measurement Bloch vectors are clustered around the true state, with some interesting behaviour at . In (AHS-10000), the measurement directions are clustered very narrowly at the true state and also around the great circle that it defines. In (AIF-10000), on the other hand, the directions are clustered widely around the true state. This is due to the difference between the loss functions employed in the update routine, namely squared Hilbert-Schmidt distance in the former and infidelity in the latter. We mention that for a completely mixed true state, the measurement Bloch vectors are distributed randomly on the Bloch sphere for large .

## Iv Discussion

### iv.1 Implementation

There are two main issues when considering the practical implementation of an adaptive scheme, namely the ease with which measurement updates can be made in the apparatus, and the time required to compute those updates. In quantum optics, projective measurements and single qubit rotations are standard tools in quantum information processing experiments. Figure 6 illustrates a simple implementation example for a one photon polarization system. In this regard, the first issue is not a problem — in general, of course it will depend on the experimental state of the art.

### iv.2 Generalization to higher dimensional systems

In order to compare the performance of the A-optimality criterion to the other update schemes, we have considered 1-qubit states as the estimation objective. Current and future quantum information processing is concerned with higher dimensional estimation objectives, not only states but also processes. In 1-qubit state estimation, we can reduce the computational cost for A-optimality by using the analytic solution of Theorem 1, but as we see in Appendix A, the techniques used to derive that solution depend on the properties of 1-qubit states and projective measurements. A-optimality in higher dimensional systems will need a new solution, or must deal with the increasing complexity of the nonlinear minimization problem. One possible approach is to place constraints on the measurement class . Instead of considering a continuous set of measurement candidates, we could consider a discrete set. One expects that the resulting discrete minimization problem would be much simpler. If the number of discrete measurement candidates is too small however, the estimation error could be worse than standard quantum tomography. The relation between the reduction in computational cost and the (probable) increase in estimation error by introducing such discrete minimization is an open problem.

## V Summary

In this paper, we considered adaptive experimental design and applied a measurement update method known in statistics as the A-optimality criterion to 1-qubit mixed state estimation using arbitrary rank-1 projective measurements. We derived an analytic solution of the A-optimality update procedure in this case, reducing the complexity of measurement updates considerably. Our analytic solution is applicable to any case in which the loss function can be approximated by a quadratic function to least order. We performed Monte Carlo simulation of this and several nonadaptive schemes in order to compare the behaviour of estimation errors for a finite number of measurement trials. We compared the average and pointwise expected squared Hilbert-Schmidt distance and infidelity of the following four measurement update criteria: A-optimality for the squared Hilbert-Schmidt distance (AHS), A-optimality for the infidelity (AIF), repetition of three orthogonal projective measurements (XYZ), and uniformly random selection of projective measurements (URS). The numerical results showed that AHS and AIF give more precise estimates than URS and XYZ which corresponds to standard quantum tomography with respect to expected infidelity.

###### Acknowledgements.
T.S. would like to thank Fuyuhiko Tanaka for helpful discussion on mathematical statistics and Terumasa Tadano for useful advice on numerical simulation. This work was supported by JSPS Research Fellowships for Young Scientists (22-7564) and Project for Developing Innovation Systems of the Ministry of Education, Culture, Sports, Science and Technology (MEXT), Japan.

## Appendix A Proof of Theorem 1

We give the proof of Theorem 1. First, we introduce a lemma about matrix inverses.

###### Lemma 1

Horn and Johnson (1985


text:
Courses
Courses for Kids
Free study material
Free LIVE classes
More

# The length of one rod is $l_1 = 3.323\,cm$ and the other is $l_2 = 3.321\,cm$. Both rods were measured with one measuring instrument with a least count of 0.001 cm. Then $\left( {{l_1} - {l_2}} \right)$ is

Last updated date: 28th Mar 2023
Total views: 431.7k
Views today: 11.08k
Verified
431.7k+ views

Hint: The lengths of the rods with the least count is found and then subtracted.

Least count of an instrument is the minimum value that we can measure with that instrument.

Length of rod one = $l_1 = (3.323 \pm 0.001)\;cm$

Length of rod two = $l_1 = (3.321 \pm 0.001)\;cm$

Here $\pm 0.001$ is added because of the least count of the instrument.

We have to find the value of $l_1 - l_2$

We also know that the errors always add up, so we get,

$\Rightarrow l_1 - l_2 = (3.323 \pm 0.001) - (3.321 \pm 0.001) = (0.002 \pm 0.002)\;cm$

Note: In such problems, one must be careful while considering the least count and other types of errors. The basic concepts should be clear. Mistakes can be avoided while subtracting and one must consider that the errors will add up.


text:
Thomas Richard

# Abstract

We consider Ricci flow invariant cones 𝒞 in the space of curvature operators lying between the cones “nonnegative Ricci curvature” and “nonnegative curvature operator”. Assuming some mild control on the scalar curvature of the Ricci flow, we show that if a solution to the Ricci flow has its curvature operator which satisfies R+εI𝒞 at the initial time, then it satisfies R+KεI𝒞 on some time interval depending only on the scalar curvature control. This allows us to link Gromov–Hausdorff convergence and Ricci flow convergence when the limit is smooth and R+I𝒞 along the sequence of initial conditions. Another application is a stability result for manifolds whose curvature operator is almost in 𝒞. Finally, we study the case where 𝒞 is contained in the cone of operators whose sectional curvature is nonnegative. This allows us to weaken the assumptions of the previously mentioned applications. In particular, we construct a Ricci flow for a class of (not too) singular Alexandrov spaces.

The author is grateful to Gilles Carron and Harish Seshadri for helpful discussions during the elaboration of this paper. The author also thanks his supervisor Gérard Besson for his interest and support.


text:
Sending a pointer to a function

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

Recommended Posts

This is what Im trying to do:
void foo( int* bar )
{
// lets make a memory leak!
bar = new int(5);
}

int main ()
{
int* myint = NULL;
foo( myint );

return 1;
}

I want to know why "myint" is still NULL after the call to foo(). Must I do something more like the following?
void foo( int** bar )
{
*bar = new int(5);
}

Share on other sites
Yes, you either need a pointer to a pointer (like you do in your 2nd example), or a reference to a pointer. This is essentially the same as a pointer to a pointer, but it looks nicer. ;)

void foo( int*& bar ){   bar = new int(5);}

This is because your function really gets a COPY of what you pass it in the argument list. Thus if you didn't give it a pointer to a pointer (or reference to a pointer), it would make a copy of your pointer, then set that to point at something ... all the while leaving your original pointer unchanged.

P.S. Beware that in your example where you use a pointer to a pointer, it may still be a good idea to check for null (which is not necessary when using a reference because references can't be null).

void foo( int** bar ){   if ( ! bar )   {      return;   }   *bar = new int(5);}

Share on other sites
Well, myint is a local variable of the main function, which was passed by value (and therefore copied) to another function. This means that the variable simply could not have been modified.

The short answer is, "don't do this". Unlike C, in C++, you should always return your results instead of altering the arguments, otherwise you will get into trouble with constructor semantics.

Share on other sites
Quote:
 Original post by ToohrVykThe short answer is, "don't do this". Unlike C, in C++, you should always return your results instead of altering the arguments, otherwise you will get into trouble with constructor semantics.

Right, Ive been told this before but what if a have a huge class or struct in which only one attribute needs to be changed.

class Huge{public:   Huge() : a(0) {}   Huge( Huge& other ) : a(other.a) {}   int a;   // many other attributes};Huge convert( Huge original ){   Huge temp( original ); // copy   temp.a = 5; // change   return temp; // copy again}void main(){   Huge myhuge;   myhuge = convert( myhuge );   cout << myhuge.a << endl;}

In this example, isnt the "Huge" instance copied when calling the function? And a new instance is then created by copying "original" (I hope I got the syntax right for the copy constructor btw) and then yet again when the "temp" instance is returned (since its local)?

I thought it would be nicer to have something along the lines of what I tried to achieve in my first post:

void convert( Huge* original ){   original->a = 5;}

Red Ant already answered my question but I would like to discuss this. Where were you going about the above mentioned strategy would make constructors troublesome?

Share on other sites
Why are you exposing the member variable as public? You could make convert a member function of Huge and make it only modify the one required field. That's what classes are for.

If for some reason you need to use non-member function that modifies the member variable (either directly or via getters/setters, it's irrelevant), I'd pass the Huge object via non-const reference, modify it through that and make it clear that modify will, well, modify the passed-in object.

Share on other sites
Quote:
Original post by Mizipzor
Quote:
 Original post by ToohrVykThe short answer is, "don't do this". Unlike C, in C++, you should always return your results instead of altering the arguments, otherwise you will get into trouble with constructor semantics.

Right, Ive been told this before but what if a have a huge class or struct in which only one attribute needs to be changed.

This is an entirely different thing. In your original example, you created a new value and sent it to the caller through an argument instead of through the return value.

In your second example, it is the caller who sends the function a value as an argument, and the function sends nothing to the caller (it merely does some work on the argument). In short, if you need to create a new object, use return, and if you need to alter an existing object, use an argument.

Note, however, that your second example is unsafe. You will need to do something like:
void convert( Huge* original ){  if (original)    original->a = 5;  else    ; // Do something relevant here}

In practice, if you need a valid argument (a null pointer being an invalid argument), you should be using a reference instead.

Share on other sites
Quote:
 Original post by MizipzorI thought it would be nicer to have something along the lines of what I tried to achieve in my first post:

But that works fine. Here you're changing the contents of the memory that the pointer points to, NOT the pointer itself (unlike your first example).

So the pointer is copied (pass by value), but not what it points to.

Share on other sites
Quote:
 Original post by MizipzorIn this example, isnt the "Huge" instance copied when calling the function?

Probably.

Quote:
 And a new instance is then created by copying "original" (I hope I got the syntax right for the copy constructor btw)

Probably; which is exactly why you wouldn't write the code like this. You were already given a copy; if you want to work on a copy, work on the copy you're given rather than re-copying.

Quote:
 and then yet again when the "temp" instance is returned (since its local)?

Maybe. There exists such a thing as "named return value optimization", whereby the compiler basically figures out to use the space on the stack where the return value goes, for the 'temp' variable.

Of course, all of that could go away, if the function gets inlined, and the code assigns the result back to the original variable, and the compiler is smart enough/doesn't have its hands tied by a weird pointer aliasing issue.

Quote:
 I thought it would be nicer to have something along the lines of what I tried to achieve in my first post:*** Source Snippet Removed ***

Well, you could do that, but normal OO practice is to let work be done by the objects that have the best access to the needed data:

class Huge{public:   Huge() : a(0) {}   Huge( Huge& other ) : a(other.a) {}   int a;   // many other attributes   void convert() { a = 5; } // <-- there you go.};

... And the net effect is that the object is not copied after all (since 'this' is a pointer).

• 32
• 12
• 10
• 9
• 9
• Forum Statistics

• Total Topics
631352
• Total Posts
2999483
×


text:
how to get number of possible public keys in RSA

I need to calculate the number of possible public keys.

The tuple for the public key is defined as: $Key_{Publ} = (n,a)$

So: Let $p:=83$ and $q:=163$

$n= p \cdot q = 83 \cdot 163 = 13529$

$\phi(n) = (p -1 )(q - 1) =(83 - 1)(163 - 1) = 13284$

Question: How is it possible to calculate the number of possible $a$'s in $\gcd(a , \phi(n))$ with $a \in [1, \phi(n)]$ ? So I will be able to calculate the possibilities with $n \cdot a$?

I have two possible ways to calculate $\phi(n):$ $$\phi(n)=(p-1)(q-1)$$ $$\phi(n)=\prod_{p \in \mathbb P}(p^{v_p(n)-1}(p-1))$$

I appreciate every hint.

• I don't understand the Question. Can you either clarify or check you have set it down correctly? Jan 15, 2017 at 22:03

$\phi(\phi(n))$ is the number of possible keys
• can you show an example how you would calculate that with the numbers $p:=83$ and $q=163$, please? Jan 30, 2017 at 22:39
• i believe in your exercise there is a Form how to calculate $\phi(n)$ Jan 30, 2017 at 22:41
• and then ? $phi(13284)=?$ That is not clear to me Jan 30, 2017 at 22:42
• exactly , now that you have 13428 = $2^{2} 3^{4} 41$ you can now find $\phi(13428)$ =$2^{(2-1)}*(2-1)*3^{(4-1)}*(3-1)*41^{(1-1)}*(41-1) = 2*3^{3}*2*40 = 4320$ Jan 30, 2017 at 23:01
• p is Prime number so in our care is 2 or 3 or 41 $v_{p}(n)$ is like $v_{2}(13284) =2$ and $v_{3}(13284) =4$ and $v_{41}(13284)=1$ Jan 30, 2017 at 23:06


text:
Minimization properties and short recurrences for Krylov subspace methods

Rüdiger Weiss

Abstract

It is well known that generalized conjugate gradient (cg) methods, fulfilling a minimization property in the whole spanned Krylov space, cannot be formulated with short recurrences for nonsymmetric system matrices. Here, Krylov subspace methods are proposed that do fulfill a minimization property and can be implemented as short recurrence method at the same time. These properties are achieved by a generalization of the cg concept. The convergence and the geometric behavior of these methods are investigated. Practical applications show that first realizations of these methods are already competitive with commonly used techniques such as smoothed biconjugate gradients or QMR. Better results seem to be possible by further improvements of the techniques. However, the purpose of this paper is not to propagate a special method, but to stimulate research and development of new iterative linear solvers.

Full Text (PDF) [251 KB], BibTeX

Key words

conjugate gradients, convergence, linear systems, Krylov methods.

AMS subject classifications

65F10, 65F50, 40A05.

Links to the cited ETNA articles

 [13] Vol. 1 (1993), pp. 11-32 Gerard L. G. Sleijpen and Diederik R. Fokkema: BiCGstab($l$) for linear equations involving unsymmetric matrices with complex spectrum

< Back


text:
Quick reminder what is frisor

Frisor is a web application in Python/Django which is just a box for interesting urls. When using untrusted network I don’t want to login anywhere to save interesting content I found. More about this is here: Introduction to frisor.

This week I introduced filtering for my urls table. I decided to use django-filter for it and I had some issues with integrating it with other third-party libraries I use.

Frisor on github: firsor repo.

Currently filtering in my application looks like this:

Setting up filtering

Setting up filtering with django-filter is quite straight forward. It has to be installed via pip then added to INSTALLED_APPS in settings.py. After that you need to create an equivalent of form for filtering, manage it in your view and put generated form in your template.

So let’s start from the beginning:

Filtering abstraction

Here is an abstraction for filtering, which will generate a filtering form for me, it derives from django_filters.FilterSet:

UrlFilter will generate a simple form, which will allow to filter by exact match of tag name, title or url.

It uses my Url model and its fields: url, title and tags__name. This last field contains __ - it’s field lookup which is used in Django to access subfields of a structure. In my Url model I’ve a field tags - it has type tagulous_models.TagField, so it has name field. That’s why in UrlFilter form I can access it via tags__name.

Manage filtering in view

My view which manages filtering, pagination and showing list of urls looks like this:

The most important is url_filter = UrlFilter(self.request.GET, queryset=url_list), which creates an UrlFilter object which uses filtering parameters from GET request and list of urls as queryset. For example for GET request:

/?url=vevurka.github.io&title=vevurka&tags__name=github

it will contain only urls with url vevurka.github.io, title vevurka and tag name github. We can access its queryset by url_filter.qs.

We have to put UrlFilter object to rendering context to be able to use its data in template. Now we can set up a template:

Filtering in template

As I’m using django-bootstrap3 for rendering forms I thought it will be simple to use nice bootstrap form in my template. Because I added url_filter to view context, I can access filter form by url_filter.form:

That was it, but it happen that it broke my pagination - after changing page, my filter query disappeared (both from form and url)!

After a bit of debugging and looking into the source of django-bootstrap3 library, I saw that when tag bootstrap_pagination creates a links for pages, it uses current GET request to do it, but clears other parameters except page one… I don’t know why the designers of django-bootstrap3 decided to do this like this:

But I saw hope in extra parameter of the same get_pagination_context function:

After some googling I came up this solution - adding an extra parameter to bootstrap_pagination tag with all parameters from request:

Summing up

So far for me it’s impossible to use any third-party Django libraries without looking to their source. Documentation usually doesn’t cover all special cases. On the other side life is to short to read whole documentation without need … These libraries present different levels of quality, code sometimes is quite bad or designed in strange way. Don’t expect they will work well together.

Tags:

Categories:

Updated:


text:
# Integrating $\frac{x\cos x}{\sin^3x}$.

This has had me going mad for more than an hour now. I'm integrating $\frac{x\cos x}{\sin^3x}~dx$.

First, I change it to $x\cot(x)\csc^2(x)~dx.$

Then, using substitution ($u=-\cot(x), du=\csc^2(x)~dx, x=-\operatorname{arccot}(u)$), I turn it into $\operatorname{arccot}(u)u~du$, which I then solve using integrating by parts. However, my solution is apparently wrong, as wolfram alpha gives an entirely different answer, and I can't for the life of me figure out what I'm doing wrong. I know that the initial part, where I change it to different trigonometric functions, is correct, and that I'm integrating by parts correctly as well. So, the substitution part must be causing the trouble, but I honestly can't figure out what I'm doing wrong. Any hints will be appreciated.

• It is quite possible that both results only differ by a constant, which means that including the constant of integration, you get the same solutions. To check your result, you can differentiate it. – Daniel Fischer Nov 9 '14 at 21:06

Try to integrate by parts right away. The first function you will be differentiating is $x$, the second one to integrate will be $\frac{\cos x}{\sin^3 x}$. For integrating you can use a substitution $u = \sin x$.
$$\int \frac{x\cos x}{\sin^3 x}dx=\int \frac{x}{\sin^3 x}d(\sin x)= \frac{x}{\sin^2 x}-\int \frac{\sin x -3x \cos x}{\sin^3 x}dx=$$ $$=\frac{x}{\sin^2 x}-\int \frac{1}{\sin^2 x} +\int \frac{3x \cos x}{\sin^3 x}dx$$
$$2\int \frac{x \cos x}{\sin^3 x}dx=-\frac{x}{\sin^2 x}+\int \frac{1}{\sin^2 x}$$ So now you just need $\int \csc^2 x dx$ which is standard.


text:
1. Dec 3, 2009

### K Sengupta

Albert, Bob and Cal each gave a birthday gift to their friend Don, who was so impressed by the presents, that he exclaimed: "Good thing your parents gave you credit cards!"

Bob explained that those cards had already been confiscated by the parents of each, and that they had to spend cold hard cash. Albert continued: "We pooled our money, and I spent 50 cents more than 1/4 of the total amount. Bob spent a dollar more than half of what was left after I bought your present, and Cal spent $1.50 more than 3/4 of what was left then. At the end, we only had$5.50 left, so we were forced to share one Big Mac, medium fries and a medium drink."

How much did each spend on Don's present?

2. Dec 3, 2009

### ƒ(x)

Last edited: Dec 3, 2009
3. Dec 3, 2009

### ƒ(x)

Forgive me, I can't find the button for math notations.
T = A + B + C

SA = T/4 + .5
SB = SA/2 + 1 = (T/4 + .5)/2 + 1
SC = (3/4)(SB) + 1.5 = (3/4)(SA/2 + 1) + 1.5 = (3/4)[(T/4 + .5)/2 + 1] + 1.5

T - SA - SB - SC = 5.5
T - (T/4 + .5) - [(T/4 + .5)/2 + 1] - [(3/4)[(T/4 + .5)/2 + 1] + 1.5] = 5.5
T - T/4 - .5 - T/8 - .25 - 1 - 3T/32 - .1875 - .75 - 1.5 = 5.5
17T = 310 (which is odd since it doesn't divide evenly)

4. Dec 7, 2009

### regor60

Albert $20 Bob$30
Cal $22.5 A+B+C=T-5.5 A=(T/4) + .5 B=(T-A)/2 +1 C=1.5+.75(T-A-B) proceed from there 5. Dec 7, 2009 ### regor60 You don't need a "spoiler" unless you come up with an answer... 6. Dec 17, 2009 ### mugaliens$12.50

Here's why:

Last edited: Dec 17, 2009
7. Dec 22, 2009

### regor60

That's not correct and your math is internally inconsistent. Even ignoring this, you've solved for the total, x, which is not the total spent, given the way you've set it up in the first line

You've set up x= spent + residual in the first line, but in the second line you indicate spent=x, based on the spent amounts you indicate for each in their respective boxes

Let's check my results:
Albert spent $20 according to my results. Is this$.50 more than one quarter of the total ?
Total = 20 + 30 + 22.5 + 5.5 = 78 > 1/4 of this is 19.50>>add .50 = 20 CHECK

I say Bob spent \$30. Is this a dollar more than half of what was left after Albert spent ?
After Albert spent remainder = 78-20 = 58> 1/2= 29> +1=30 CHECK

I say Cal spent 22.5. Is this 1.5 more than 3/4 of what was left after Al and Bob spent ?
Remainder after Al and Bob=78-20-30=28 >> 3/4 = 21> +1.5= 22.5 CHECK

Finally, is their 5.50 left after all have spent ?

78-20-30-22.5=5.5 CHECK

But you knew you didn't have the correct answer, so the question is, why did you bother advertising that fact ?

Last edited: Dec 22, 2009
8. Dec 30, 2009

### mugaliens

I apologize - I'm new and wasn't aware of the spoiler tag policy.