I've submitted my report on The Hidden Subgroup Problem to arXiv.org and I expect it to be published soon.

Comments are welcome on this blog entry.

To content | To menu | To search

Friday, July 30 2010

By fred on Friday, July 30 2010, 22:26

I've submitted my report on The Hidden Subgroup Problem to arXiv.org and I expect it to be published soon.

Comments are welcome on this blog entry.

Saturday, July 24 2010

By fred on Saturday, July 24 2010, 17:15

So I'm finally done with my Master's Project in Quantum Computing at Århus. My final report on The Hidden Subgroup Problem is now available in XHTML and pdf formats. There are also the slides I've made for the oral defense, although as always it is not really useful without the comments. This time, I've used the W3C's slidy tool and so my work is 100% based on Web formats :-)

The Hidden Subgroup Problem still remains difficult with our current knowledge, but I've very appreciated thinking on this challenging topic and I hope my work will help research in this area. As an advocate of the Web as a publishing medium for scientists, I've also found a meta-interest in seeing whether it is possible to use Web formats to produce documents readable both on the screen and on the paper (and in this latter case with the same quality as the more traditional methods). One way to do that is to use TeX-like documents and export them in Web/Printing formats using tools such that Tex4ht or GELLMU. Since my personal preference is to write Web contents by a hybrid method (mixing WYSIWYG and simple-syntax-parsers), I've rather considered how one can print these Web formats. One tool to do that is Prince but I'm not sure it is that good with SVG/MathML (there were some issues last time I tried it). Hence I've preferred to use a free layout engine and thus printed my report with Gecko :-).

One of the difficulty is to handle numbering (pages, sections, formulas, theorems...) and the corresponding references (HTML links or page numbers) either in the table of contents or inside the body of the report itself. Moreover, the report has to be split into several small pieces for otherwise it is too large to be edited easily (in my case, 1.1Mb on a single XHTML page for an amount of 99 pages). Hence at the beginning I had to quickly write once and for all an automated system. I'm not really prude of it - it is truly an usine à gaz involving CSS counters, Flex lexical analyzer and a command line print extension for Firefox - but at least it works almost as I expect. Ideally, it should be possible to print each piece separately before grouping them into one single pdf document. However, because of the choice of CSS counters and the lack of control on page numbering in Mozilla I could only print the whole large XHTML document. This was really not convenient and was one of the main annoying issue. The other one being that there is no access to the page numbers and so for the table of contents, I had to write them manually :-(. It seems that a way to overcome the page number issues would be to implement some CSS rules for printing although I don't know if it helps working on separate pieces.

The other problems are various bugs in Gecko. Thanks to the recent
improvements in MathML (related to stretchy and fonts) , the mathematical
formulas are now displayed with a good quality, or at least one of which I'm
satisfied. One issue is the incorrect
computation of dimension in mtable which is slightly visible for some split
equations. I've also discovered a wrong thickness of
bars which seems to be the only difference between print and screen
renderings. However, I could workaround it and Karl gave me a hint that would
hopefully allow to fix the bug. There are still some annoying bugs with linebreaking within
mathematical expressions and around them. For
the former I can avoid the problem by adding `<mrow/>`

's but
the latter makes particularly weird effects. Typically, when some comma or
period is placed just after an inline formula, a linebreak may happen and move
the punctuation symbol to the beginning of the next line... Regarding quantum
circuits and other schemas, the SVG code I use is very elementary. Hence I
don't have any complaint to formulate, even if I'm among those who are
expecting the possibility to use SVG images in
the standard `<img/>`

tag. Finally, I have some mysterious
bugs with HTML tables printed on several pages and more issues with CSS page
breaking, requiring me to do some small manual tweaking at two or three
places.

As a conclusion, using Web formats to print a scientific report is not yet so easy. However, I'm quite satisfied of the result and I expect the issues above to be fixed in the near future...

Monday, July 5 2010

By fred on Monday, July 5 2010, 11:11

Back to the DHSP again (see part 1 and part 2 in previous blog posts)... This time, I've tried to approximate the value of $d$ rather than finding its parity. For convenience, we assume $N$ to be even and define $N\text{'}=2M=\frac{N}{2}$. We consider for $a\in {\mathbb{Z}}_{N}$ and $b\in {\mathbb{Z}}_{2}$ the sets of $N\text{'}$ successive values$${F}_{a}^{b}=\{f(a+i,b),i\in {\mathbb{Z}}_{N\prime}\}$$

We suppose that we can efficiently create uniform superposition over these states. As in part 2, we have ${F}_{a}^{1}={F}_{a-d}^{0}={F}_{s}^{0}$ with $-N<s<N$ and we measure the tensor product of the uniform superpositions over ${F}_{a}^{1}={F}_{s}^{0}$ and ${F}_{0}^{0}$ in the basis ${\mid x\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$, ${\frac{1}{\sqrt{2}}\left(\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9\right)}_{x<y\in {\mathbb{Z}}_{N}}$, ${\frac{1}{\sqrt{2}}\left(\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9\right)}_{x<y\in {\mathbb{Z}}_{N}}$. We define $l=\mid {F}_{0}^{0}\cap {F}_{a}^{1}\mid $ the number of common elements.

The figure above shows that in the case $0\le s\le N\text{'}$, we have $l=N\text{'}-s$. In general, the expression is

$$l=\mid N\text{'}-\mid s\mid \mid =\mid N\text{'}-\mid d-a\mid \mid $$

Using an analysis similar to the one part 2, we get the probability to measure an element in ${\frac{1}{\sqrt{2}}\left(\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9\right)}_{x<y\in {\mathbb{Z}}_{N}}$:

$$P=\frac{1}{2}[1-{\left(\frac{l}{N\prime}\right)}^{2}]$$

Repeating the measurements, we can approximate $P$, and consequently $l,s$ and finally $d$. We can also play with the value $a$, to improve the approximation. Unfortunately, using a number of repetitions polynomial in $\mathrm{log}N$, it does not seem possible to bound the error better than $O\left(N\right)$. It seems however that it is still a better result than the one that I obtained with the standard Coset Sampling method. Hence it is another hint of the fact that using a superposition over several oracles values would yield improvement.

I'm still wondering how to create efficiently an uniform superposition over
several oracle values. One thing I've read in many papers, is given a
superposition over elements $\mid x\u27e9\mid f(x)\u27e9$, *erase* or *uncompute* the first register to get a
superposition over elements $\mid f(x)\u27e9$. However, I'm not sure what are the requirements to apply such an
operation. If it could work for the algorithm of part
2, then this would solve the case
$N={2}^{n}$.

By fred on Monday, July 5 2010, 11:09

Microsoft has a page to provide
feedback to the Internet Explorer team, but it seems very far from being as
good as other tracking systems. In the bug reports I have read, the answers of
the IE team are essentially pre-made messages and they have the bad habit to
close reports without fixing the bugs. Two months ago, I requested a modest
feature: since Internet Explorer does not have native implementation for
MathML, I asked support for attributes
`altimg`

/`alttext`

, so that people can provide
alternative content. A few days later, I received a notification:

Thank you for your feedback. We will take your feedback into consideration in our ongoing process of improving Internet Explorer.

and another one, two months later:

Thank you again for your feedback. Since this is a feature request, we will resolve this as by design. However, we have taken your feedback into consideration.

Field Status changed from [Active] to [Resolved]

Field Resolution changed from [None] to [By Design]

Field Status changed from [Resolved] to [Closed]

Not sure how I should interpret these messages, but I'm not really optimistic about that.

Sunday, June 20 2010

By fred on Sunday, June 20 2010, 22:36

In a previous post, I've proposed a way to solve the Dihedral Hidden Subgroup Problem using a superposition of oracle evaluations. However, it seems to require a way to inverse the functions $x\mapsto f\left(x,.\right)$ which is a bit cheating since we do not have this feature for the classical problem. In this post, we will consider the case $M=\frac{N}{N\text{'}}=2$, $d=2d\text{'}+b$ and try to determine the parity $b$ of $d$. If $N$ is a power of two, this is enough to find $d$ recursively. As in the previous post, the main idea is to consider the superpositions

$$\mid {\psi}_{0}\u27e9=\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(2i,0)\u27e9$$

and

$$\mid {\varphi}_{0}\u27e9=\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(2i,1)\u27e9$$

Using the equality $f\left(g\left(d,1\right)\right)=f\left(g\right)$ we can rewrite the latter state

$$\mid {\varphi}_{0}\u27e9=\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(2i-b,0)\u27e9$$

If $b=0$, the latter state is the same superposition as the former state, over $N\text{'}$ values of ${\mathbb{Z}}_{N}$. Otherwise, $b=1$ and the latter state is the superposition over the $N\text{'}$ other values of ${\mathbb{Z}}_{N}$. We let ${f}_{i}^{b}=f(2i-b,0)$ and measure the product state $\mid {\psi}_{0}\u27e9\mid {\varphi}_{0}\u27e9$ in the basis ${\mid x\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$, ${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$, ${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ . It turns out that this allows to distinguish the two cases:

- If $b=0$, the product contains vectors with the same coordinates $\mid {f}_{i}^{0}\u27e9\mid {f}_{i}^{0}\u27e9$ for $i\in {\mathbb{Z}}_{N}$. For the other vectors, we have a symmetry between the two coordinates. Hence we can group them by pairs $\mid {f}_{{i}_{1}}^{0}\u27e9\mid {f}_{{i}_{2}}^{0}\u27e9+\mid {f}_{{i}_{2}}^{0}\u27e9\mid {f}_{{i}_{1}}^{0}\u27e9$ for ${i}_{1}<{i}_{2}\in {\mathbb{Z}}_{N}$. Finally, the product state belongs to the space spanned by ${\mid x\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$ and ${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$.
- If $b=1$, the product contains vectors $\mid {f}_{{i}_{1}}^{0}\u27e9\mid {f}_{{i}_{2}}^{1}\u27e9$ where the two coordinates are not equal. We never have two symmetric vectors i.e. which are the same after permutating the two coordinates. Moreover, each vector $\mid {f}_{{i}_{1}}^{0}\u27e9\mid {f}_{{i}_{2}}^{1}\u27e9$ is the expression of a sum/difference (according to the respective order of ${f}_{{i}_{1}}^{0}$ and ${f}_{{i}_{2}}^{1}$) of two vectors $\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9$ and $\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9$. So the product state belongs half to ${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ and half to ${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$.

Suppose that we have a procedure to create many states $\mid {\psi}_{0}\u27e9$ and $\mid {\varphi}_{0}\u27e9$. We measure a state in the space ${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ with probability $\frac{b}{2}$. So repeating the procedure a constant number of times allow to determine $b$ with high probability.

The only gap in the previous algorithm is whether we can create the states $\mid {\psi}_{0}\u27e9$ and $\mid {\varphi}_{0}\u27e9$. As in the previous post, this is possible if the gates ${V}_{f,.}$ are available. Otherwise, we can create a superposition of states over ${\mathbb{Z}}_{N\text{'}}$ and use the gate ${U}_{f}$ as well as a Quantum Fourier Transform to randomize the first coordinate. We get two random numbers ${j}_{1},{j}_{2}\in {\mathbb{Z}}_{N\text{'}}$ and the states

$$\mid {\psi}_{{j}_{1}}\u27e9=\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}{e}^{\frac{2i\pi {j}_{1}i}{N\prime}}\mid f(2i,0)\u27e9$$

and$$\mid {\varphi}_{{j}_{2}}\u27e9=\frac{{e}^{\frac{2i\pi {j}_{2}d\prime}{N\prime}}}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}{e}^{\frac{2i\pi {j}_{2}i}{N\prime}}\mid f(2i-b,0)\u27e9$$

Next, we can apply the same measurement as above. After a bit of calculation,we get the probabilities:

Space | case $b=0$ | case $b=1$ |
---|---|---|

${\mid x\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$ | $\frac{1}{N\text{'}}$ | 0 |

${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ | $\frac{2}{{N\prime}^{2}}\sum _{{i}_{2}=0}^{N\prime -1}\sum _{{i}_{1}=0}^{{i}_{2}-1}{\mathrm{cos}}^{2}\frac{\pi}{N\prime}({j}_{2}-{j}_{1})({i}_{2}-{i}_{1})$ | $\frac{1}{2}$ |

${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ | $\frac{2}{{N\prime}^{2}}\sum _{{i}_{2}=0}^{N\prime -1}\sum _{{i}_{1}=0}^{{i}_{2}-1}{\mathrm{sin}}^{2}\frac{\pi}{N\prime}({j}_{2}-{j}_{1})({i}_{2}-{i}_{1})$ | $\frac{1}{2}$ |

If we repeat the procedure several times, we need to take the means over the choice of ${j}_{1},{j}_{2}\in {\mathbb{Z}}_{N\text{'}}$. Using some trigonometric identities, it is possible to write the sums of the first column $\frac{1}{2}+S+o\left(\frac{1}{N\text{'}}\right)$ where $S$ is a sum of cosinus. Unfortunately, evaluating $S$ with a computer suggests that $S=\Theta \left(\frac{1}{N\text{'}}\right)$ . Hence, we can not distinguish the two cases with only a polynomial (in $\mathrm{log}N$) number of samplings.

It is still open whether we can find a variation to make such an algorithm efficient...

Wednesday, June 16 2010

By fred on Wednesday, June 16 2010, 15:32

This morning, I've been thinking again about a way to solve the Hidden Subgroup
Problem for the dihedral group
${D}_{N}={\mathbb{Z}}_{N}{\u22ca}_{\phi}{\mathbb{Z}}_{2}$ (where $\phi \left(1\right)$ is the inversion of ${\mathbb{Z}}_{N}$). It is well-known that there exists a reduction to the case where the
hidden subgroup is $H=\u27e8(d,1)\u27e9$ for some $d\in {\mathbb{Z}}_{N}$. In that case, if we fix
$b\in \{0,1\}$, the elements $\left(i,b\right)$ for $i\in {\mathbb{Z}}_{N}$ form a complete set of coset representatives, so
$f$ is one-to-one over ${\mathbb{Z}}_{N}\times \left\{b\right\}$. Thus, $x\mapsto f\left(x,b\right)$ is a *permutation* of
${\mathbb{Z}}_{N}$, a property that will be used below to construct a unitary
transform.

First let's recall the classical inductive method to determine $d$. If $M$ is a divisor of $N$, let $N\text{'}=\frac{N}{M}$ and write the euclidean division $d=Md\text{'}+r$. If we are able to determine $r$ in polynomial time, then we can define the oracle $f\text{'}(x,y)=f(Mx+r,y)$ for $x\in {\mathbb{Z}}_{N\text{'}}$ and $y\in {\mathbb{Z}}_{2}$ and obtain a dihedral HSP with hidden subgroup $\u27e8(d\text{'},1)\u27e9$. Since the prime factorization has only $O\left(\mathrm{log}N\right)$ factors, we can repeat this inductive step to get an efficient algorithm. Of course, this is likely to be useful only when the factors are small for otherwise it may be as much difficult to determine $r$ as to determine the whole $d$. One interesting case is $N={2}^{n}$ and $M=2$: at each step, $N$ remains a power of 2 and we determine the parity of $d$.

For $0\le l<M$, we consider the $N\text{'}$-dimensional subspace spanned by the vectors $\mid lN\text{'}+m\u27e9$ for $0\le m<N\text{'}$. Since these $M$ subspaces are orthogonal, we can construct a unitary transform by applying a Quantum Fourier Transform ${F}_{N\text{'}}$ on each subspace separately. Finally, we apply the permutation mentionned at the beginning for $b=0$. We get a unitary transform $W$ below where $x=Mi+k$ is the euclidean division of $x$ by $M$:

$$\forall x\in {Z}_{N},W\mid x\u27e9=\frac{1}{\sqrt{N\prime}}\sum _{j=0}^{N\prime -1}{e}^{2i\pi \frac{ij}{N\prime}}\mid f(Mj+k,0)\u27e9$$

Now, let's consider the superposition (again, we see that it is well-defined by considering the permutation mentionned at the beginning for $b=1$):

$$\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(Mi,1)\u27e9$$

The state can be rewritten, using the fact that $f$ is constant on $H=\u27e8(d,1)\u27e9$:

$$\begin{array}{rl}\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(Mi,1)\u27e9& =\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(Mi-d,0)(d,1)\u27e9\\ & =\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(Mi-d,0)\u27e9\\ & =\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(Mi-\left(Md\prime +r\right),0)\u27e9\\ & =\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(M(i-d\prime +(N\prime -1))+(M-r),0)\u27e9\\ & =\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(Mi+(M-r),0)\u27e9\end{array}$$

Applying ${W}^{-1}$ to this state gives $\mid M-r\mathrm{mod}\left(M\right)\u27e9$ and so the value of $r$ by a measurement in the standard basis.

Two questions remain: can we implement $W$ and create the state $\mid \Psi \u27e9$ efficiently? If $N={2}^{n}$ and $M=2$, there are many simplifications because we are working with qubits. In that case, it is easy to see that the answer to the previous questions is affirmative if we have gates ${V}_{f,b}\mid x\u27e9=\mid f\left(x,b\right)\u27e9$ implementing the permutation mentioned at the beginning. However, it is not clear how to build ${V}_{f,b}$ from the gate ${U}_{f}$ generally given in the classical presentation of the problem...

update: OK, there is also the trivial solution $N=M,N\text{'}=1$where the algorithm above is just computing ${V}_{f,0}^{-1}{V}_{f,1}\mid 0\u27e9=\mid N-d\mathrm{mod}\left(N\right)\u27e9$. However, I'm still wondering if there is a way to modify the previous method to work with ${U}_{f}$.

Monday, June 14 2010

By fred on Monday, June 14 2010, 11:49

MathML 3 comes with a new
version of the operator dictionary and I expect to update Mozilla's own
version accordingly. Some members of the MathML WG have actually written a
separate recommendation XML
Entity Definitions for Characters which contains various information on
Unicode characters, including some properties relevant to mathematical
operators. They provide a file unicode.xml
which is very large (> 6Mb) so I've written an XSLT stylesheet to extract
only the information required for the operator dictionary. The stylesheet does
nothing magical: it only creates an XML document with a
`<root/>`

and `<entry/>`

's children. The
attributes from the initial unicode.xml are attached to each of these entries,
using the compact form of the MathML 3 dictionary for boolean-valued
properties.

Using the xsltproc tool, the typical command is

```
xsltproc -o dictionary.xml operatorDictionary.xsl
unicode.xml
```

which produces a XML file `dictionary.xml`

of moderate size (<
150 ko) that should be easier to process. I hope it will help developers of
MathML tools to align on the new operator dictionary. Note that the stylesheet
is distributed under a triple MPL/GPL/LGPL licence, so people should be able to
use it freely.

Friday, June 11 2010

By fred on Friday, June 11 2010, 12:06

Two weeks ago, STIX Fonts Version
1.0 was finally released! Hence after about 15 years of work and
regular announce of upcoming
release, we now have a comprehensive set of Unicode fonts for mathematical
symbols. Hopefully, this will greatly improve the rendering of MathML in
browsers. However, this new version is not entirely
compatible with the current version of Firefox, because some font files
were renamed. A patch
landed yesterday on trunk to fix this issue but I don't know whether it
will also be pushed to old branch. For those who want to test the new STIX
Fonts with the current version of Firefox, you just need to install STIX 1.0
and keep the former `STIXSiz*.otf`

files from STIX Beta...

Sunday, May 30 2010

By fred on Sunday, May 30 2010, 17:54

Today, I have added some pages to the international section of the website. Apart my hand-in exam for the course Category Theory for Computer Science, there are pages on Riemannian Geometry: my notes for the oral exam, my proposal of solutions to the exercises 4.12 and 7.1 of Lee's book (Riemannian Manifolds, An Introduction to Curvature) and my proof of the fact that in a 3-dimensional riemannian manifold, the curvature tensor is determined by the Ricci curvature. This proof uses a funny relationship between the determinant of the linear system involved and the one of the matrix of the riemannian metric that I have obtained using Maxima (yes, I'm too lazy to compute the determinant of a $6\times 6$ matrix). I haven't written material about the other courses but I hope to make available my report on Quantum Computation when I'm finished.

Monday, May 24 2010

By fred on Monday, May 24 2010, 22:42

Today, I have finished the preliminary version of my report on the Hidden Subgroup Problem (HSP). For those who have never heard about it before, we are given a finite group $G$, a subgroup $H$ and a function $f:G\to S$. This function is constant on each (left) coset of $H$ but takes different values on distinct cosets. Said otherwise we have:

$$\forall {g}_{1},{g}_{2}\in G,f({g}_{1})=f({g}_{2})\iff {g}_{1}H={g}_{2}H$$The purpose is to identify the "hidden" subgroup $H$ (for instance we can return a generating set) with a complexity polynomial in $\mathrm{log}\mid G\mid $. Although it may seem really abstract, this problem allows to describe various quantum algorithms exponentially faster than their known classical versions. This includes the famous Shor's algorithm for integer factorization, which can break the ubiquitous RSA cryptosystem. Shor's algorithm uses a solution to HSP over a cyclic group but we have quantum algorithms for the larger class of dedekindian groups as well as miscellaneous other groups. Unfortunately, these algorithms are not enough to solve HSP over the dihedral group or the symmetric group. These two cases are particularly interesting since the former could solve a lattice problem used in cryptography to establish security proofs while a solution to the latter provides an efficient algorithm for the graph isomorphism problem.

For the moment, I have essentially reviewed the major results on dedekindian, dihedral and symmetric groups. Even if there is not many new things for researchers working on that topic, I hope it could serve as an introduction to the subject and be a useful review of the state-of-the-art. In particular, I plan to complete the Table of Hidden Subgroup Problems which gives a good overview. There are at least two contributions I brought to the topic that I would like to discuss briefly in this blog post.

First, I
have studied how Regev's algorithm works. As stated in his paper, we have a
solution to the $\text{poly}\left(\mathrm{log}N\right)$-uniqueSVP if we can find a hidden subgroup
$H=\u27e8(d,1)\u27e9$ in the dihedral group ${D}_{N}$ using *coset sampling on the whole group*. This point is often
overlooked in several papers, where the reader could understand that an
arbitrary solution to the dihedral HSP works. Fortunately, Regev's algorithm is
sufficiently close to the coset sampling procedure so that we can modify it to
include some kinds of *recursive* algorithm. With such a modification, a
solution like Kuperberg's algorithm (where we apply coset sampling on subgroups
of ${D}_{N}$) becomes acceptable. Actually, we can also modify the algorithm to work
with the generalized
dihedral group. Another remark is about the degree of the approximation
given by Regev's algorithm: I have shown that we have a solution to the
$\Theta \left({n}^{\frac{1}{2}+2D}\right)$-uniqueSVP if the query complexity of the HSP algorithm used is
$O\left({\left(\mathrm{log}N\right)}^{D}\right)$, thus providing a more accurate statement.

Recently, I have considered a general approach to the HSP using the classical description of finite group via composition series and simple groups. The idea is that if $N$ is a non-trivial normal subgroup of $G$ we can split the problems on two HSPs over $\raisebox{1ex}{$G$}\!\left/ \!\raisebox{-1ex}{$N$}\right.$ and $N$. We can repeat the procedure until we reach simple groups. Because the length of a composition series is polynomial in $\mathrm{log}\mid G\mid $, we get a solution to the general HSP under two conditions: we have algorithms for HSP over simple groups and we can build efficient oracles on the "reduced" groups. I've succeeded to find an alternative algorithm for the abelian case based on that framework but for the dihedral/symmetric, it seems that the two previous assumptions are exactly what we are stuck on. However, it could still be useful to solve HSP over other groups.

Now, my priority is to review the results we have for some semidirect products but I hope to have time to study various open issues such that HSP over simple groups, HSP-based algorithms etc

Thursday, May 6 2010

By fred on Thursday, May 6 2010, 10:09

The `<semantics/>`

has long been used by people who work on
MathML tools. The idea is to have a MathML formula as the first child and to
use the other children as annotations. These are an important information for
software tools but should really not be shown by viewers. Roger B. Sidje fixed
bug 154931
about seven years ago by adding CSS rules to display only the first child of a
`<semantics/>`

element. This looks an appropriate fix. However
several
issues have been reported in the last two years, regarding the
`<semantics/>`

element.

Some of these issues involved complicated context such that combination with
`<maction/>`

or javascript. Fortunately, some reduced
testcases were provided afterwards. I could at least explain one of these
bugs: the fact that displaystyle is not
inherited through a `<semantics/>`

element. Indeed, this
inheritance is implemented in MathML frame classes but no class existed for
`<semantics/>`

! Of course, this absence of class was also
likely to break many things in the MathML layout mechanisms since it basically
prevented communication between MathML element frames.

Hence I've written a patch which is just implementing a
`nsMathMLsemanticsFrame`

class (the only thing this class adds with
respect to its parent is the handling of embellished operator data). As
expected, this simple change fixed the displaystyle bug. Furthermore, it also
solved all the other `<semantics/>`

-related issues as I could
easily check using the testcases.

This is an example where something that looks like a minor defect - namely, the lack of frame class for a MathML element - can lead to many non-trivial bugs! Moreover, it demonstrates once again the importance of bug triage, since reducing testcases and grouping the <semantics/>-related issues in one meta bug have been very useful for solving that issue. The fix I've proposed does not add the desired behaviour for semantics, but maybe someone else will work on this in the future...

Sunday, May 2 2010

By fred on Sunday, May 2 2010, 17:17

Of course, the first thing I've checked after setting this blog is whether
it is possible to have a `XHTML+MathML+SVG`

page in dotclear. As indicated in the Mozilla
MathML Project page, one has to:

- serve the page as
`application/xhtml+xml`

.This is simply done by editing the value of parameter

`$content_type`

in the function`serveDocument`

of the file`dotclear/inc/public/lib.urlhandlers.php`

. - write well-formed XML document.
Apparently, dotclear is good enough to do that. However, its editor does not seem to have any option for producing MathML or SVG. Personally, I don't use the wiki syntax and prefer to write the XHTML page myself with the tools I'm used to (no, I don't mean a code editor... I'm not crazy!). As a consequence, this is not really a problem for me.

It is also a good idea to write a

*valid*XML document. By default, dotclear uses the doctype`XHTML 1.0 Strict`

so I had to modify the files`themes/name_of_your_theme/tpl/*.html`

to set`XHTML+MathML+SVG`

instead.

Once this simple changes are made, you can insert MathML formulas such that this expression of a general Quantum Fourier Transform over a finite group:$$\forall g\in G,{F}_{G}\mid g\u27e9=\frac{1}{\sqrt{\mid G\mid}}\sum _{\rho \in \hat{G}}\sqrt{{d}_{\rho}}\sum _{i,j=1}^{{d}_{\rho}}{\rho}_{ij}(g)\mid \rho ij\u27e9$$

or SVG images such that this quantum circuit used in the famous Shor's algorithm:

Voilà!

By fred on Sunday, May 2 2010, 17:07

Voilà, je viens de mettre en place ce blog aujourd'hui. J'espère ainsi
profiter des avantages offerts par ce medium: syndication de contenu, archivage
en catégories, possibilité d'avoir des commentaires etc. Je compte m'en servir pour parler de
mes différents travaux et il me sera alors indispensable
de pouvoir utiliser le format `XHTML+MathML+SVG`

. Par conséquent,
mon prochain billet sera sur la manière de paramètrer Dotclear pour pouvoir
répondre à ce besoin.