Blog de Frédéric

To content | To menu | To search

Friday, July 30 2010

Master's Project - The Hidden Subgroup Problem

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

Using Mozilla to print a scientific report based on Web formats

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

Thoughts on the Dihedral Hidden Subgroup Problem (part 3)

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 ' = 2 M = N 2 . We consider for a N and b 2 the sets of N ' successive values F a b = { f ( a + i , b ) , i N }

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 x x x N , 1 2 ( x y + x y ) x < y N , 1 2 ( x y x y ) x < y N . We define l = F 0 0 F a 1 the number of common elements.

f ( 0 , 0 ) f(0,0) f ( N ' , 0 ) f(0,0) f ( N 1 , 0 ) f(0,0) F 0 0 F_0^0 F s 0 F_s^0 s s l l N ' N' 0 s N ' 0 ≤ s ≤ N'

The figure above shows that in the case 0 s N ' , we have l = N ' s . In general, the expression is

l = N ' s = N ' d a

Using an analysis similar to the one part 2, we get the probability to measure an element in 1 2 ( x y x y ) x < y N :

P = 1 2 [ 1 ( l N ) 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 log N , it does not seem possible to bound the error better than O ( N ) . 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 x f ( x ) , erase or uncompute the first register to get a superposition over elements f ( x ) . 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 .

Alternative content for the top-level math element and Internet Explorer feedback website

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

Thoughts on the Dihedral Hidden Subgroup Problem (part 2)

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 f ( x , . ) 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 = N N ' = 2 , d = 2 d ' + 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

ψ 0 = 1 N i = 0 N 1 f ( 2 i , 0 )

and

ϕ 0 = 1 N i = 0 N 1 f ( 2 i , 1 )

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

ϕ 0 = 1 N i = 0 N 1 f ( 2 i b , 0 )

If b = 0 , the latter state is the same superposition as the former state, over N ' values of N . Otherwise, b = 1 and the latter state is the superposition over the N ' other values of N . We let f i b = f ( 2 i b , 0 ) and measure the product state ψ 0 ϕ 0 in the basis x x x N , x y + x y x < y N , x y x y x < y N . It turns out that this allows to distinguish the two cases:

  • If b = 0 , the product contains vectors with the same coordinates f i 0 f i 0 for i N . For the other vectors, we have a symmetry between the two coordinates. Hence we can group them by pairs f i 1 0 f i 2 0 + f i 2 0 f i 1 0 for i 1 < i 2 N . Finally, the product state belongs to the space spanned by x x x N and x y + x y x < y N .
  • If b = 1 , the product contains vectors f i 1 0 f i 2 1 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 f i 1 0 f i 2 1 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 x y + x y and x y x y . So the product state belongs half to x y + x y x < y N and half to x y x y x < y N .

Suppose that we have a procedure to create many states ψ 0 and ϕ 0 . We measure a state in the space x y x y x < y N with probability 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 ψ 0 and ϕ 0 . As in the previous post, this is possible if the gates V f , . are available. Otherwise, we can create a superposition of states over N ' 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 N ' and the states

ψ j 1 = 1 N i = 0 N 1 2 π j 1 i N f ( 2 i , 0 )

and ϕ j 2 = 2 π j 2 d N N i = 0 N 1 2 π j 2 i N f ( 2 ib , 0 )

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
x x x N 1 N ' 0
x y + x y x < y N 2 N 2 i 2 = 0 N 1 i 1 = 0 i 2 1 cos 2 π N ( j 2 j 1 ) ( i 2 i 1 ) 1 2
x y x y x < y N 2 N 2 i 2 = 0 N 1 i 1 = 0 i 2 1 sin 2 π N ( j 2 j 1 ) ( i 2 i 1 ) 1 2

If we repeat the procedure several times, we need to take the means over the choice of j 1 , j 2 N ' . Using some trigonometric identities, it is possible to write the sums of the first column 1 2 + S + o ( 1 N ' ) where S is a sum of cosinus. Unfortunately, evaluating S with a computer suggests that S = Θ ( 1 N ' ) . Hence, we can not distinguish the two cases with only a polynomial (in 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

Thoughts on the Dihedral Hidden Subgroup Problem

This morning, I've been thinking again about a way to solve the Hidden Subgroup Problem for the dihedral group D N = N φ 2 (where φ ( 1 ) is the inversion of N ). It is well-known that there exists a reduction to the case where the hidden subgroup is H = ( d , 1 ) for some d N . In that case, if we fix b { 0 , 1 } , the elements ( i , b ) for i N form a complete set of coset representatives, so f is one-to-one over N × { b } . Thus, x f ( x , b ) is a permutation of 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 ' = N M and write the euclidean division d = M d ' + r . If we are able to determine r in polynomial time, then we can define the oracle f ' ( x , y ) = f ( M x + r , y ) for x N ' and y 2 and obtain a dihedral HSP with hidden subgroup ( d ' , 1 ) . Since the prime factorization has only O ( log N ) 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 l < M , we consider the N ' -dimensional subspace spanned by the vectors l N ' + m for 0 m < N ' . Since these M subspaces are orthogonal, we can construct a unitary transform by applying a Quantum Fourier Transform F N ' 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 = M i + k is the euclidean division of x by M :

x Z N , W x = 1 N j = 0 N 1 2 π i j N f ( M j + k , 0 )

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 ):

1 N i = 0 N 1 f ( M i , 1 )

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

1 N i = 0 N 1 f ( M i , 1 ) = 1 N i = 0 N 1 f ( M i d , 0 ) ( d , 1 ) = 1 N i = 0 N 1 f ( M i d , 0 ) = 1 N i = 0 N 1 f ( M i ( M d + r ) , 0 ) = 1 N i = 0 N 1 f ( M ( i d + ( N 1 ) ) + ( M r ) , 0 ) = 1 N i = 0 N 1 f ( M i + ( M r ) , 0 )

Applying W 1 to this state gives M r   mod   ( M ) and so the value of r by a measurement in the standard basis.

Two questions remain: can we implement W and create the state Ψ 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 x = f ( x , b ) 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 ' = 1 where the algorithm above is just computing V f , 0 1 V f , 1 0 = N d   mod   ( N ) . However, I'm still wondering if there is a way to modify the previous method to work with U f .

Monday, June 14 2010

XSLT Stylesheet to help updating the MathML Operator Dictionary

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

stixfonts.org was last updated on 28 May. The next update will occur mid-June.

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

New pages written during the first semester at Århus

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 × 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

Two contributions to the Hidden Subgroup Problem

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 S . This function is constant on each (left) coset of H but takes different values on distinct cosets. Said otherwise we have:

g 1 , g 2 G , f ( g 1 ) = f ( g 2 ) 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 log G . 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 poly ( log N ) -uniqueSVP if we can find a hidden subgroup H = ( d , 1 ) 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 Θ ( n 1 2 + 2 D ) -uniqueSVP if the query complexity of the HSP algorithm used is O ( ( log N ) D ) , 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 G N and N . We can repeat the procedure until we reach simple groups. Because the length of a composition series is polynomial in log G , 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

To kill five bugs with one stone

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

Hacking Dotclear 2 for writing XHTML+MathML+SVG

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:

  1. 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.

  2. 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: g G , F G g = 1 G ρ G ̂ d ρ i , j = 1 d ρ ρ i j ( g ) ρ i j

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

0 n |0^n⟩ 0 n |0^n⟩ U f U_f F N F_N F N F_N

Voilà!

Mise en place d'un blog

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.