2009

• Sebastian Dörn, Quantum Algorithms for Graph and Algebra Problems, to appear at Recent Patents on Computer Science, 2009.
  

  Abstract: Quantum algorithms have the potential to demonstrate that for some problems quantum computation is more efficient than classical computation. A goal of quantum computing is to determine for which problems quantum computers are faster than classical computers. In our survey we present recent quantum algorithms for basic problems from graph and algebra theory. The quantum algorithms for these problems use a combination of Grover’s search algorithms, quantum amplitude amplification and quantum random walks. These quantum algorithms are faster than the best known classical algorithms for the corresponding problems.

• Sebastian Dörn, Daniel Haase, Jacobo Toran, Fabian Wagner, Isomorphism and Factorization-Classical and Quantum Algorithms, In Mathematical Analysis of Evolution, Information and Complexity, Wiley, 2009.
  Abstract: In this paper we give an overview of several attempts for obtaining efficient classical and quantum algorithms for Integer Factorization (IF) and Graph Isomorphism (GI). In doing this we point out several similarities between both problems. Finally we review a result showing that IF and GI are in fact particular instances of a more general algebraic problem, the ring isomorphism problem.

2008

• Sebastian Dörn, Quantum Algorithms for Matching Problems, Theory of Computing Systems, 2008.
  Abstract: We present quantum algorithms for matching problems in unweighted and weighted graphs. Our results improve the best classical complexity bounds for the corresponding problems.

• Sebastian Dörn, Thomas Thierauf, The quantum query complexity of the determinant, Information Processing Letters, 2008.
  Abstract: In this paper we give tight quantum query complexity bounds of some important linear algebra problems. We prove n^2 http://www.sciencedirect.com/science?_ob=MathURL&_method=retrieve&_udi=B6V0F-4TYJV2R-2&_mathId=mml1&_user=10&_cdi=5645&_rdoc=1&_acct=C000050221&_version=1&_userid=10&md5=034ce0cd4674bfe7eb131957de960fe7 quantum query bounds for verify the determinant, rank, matrix inverse and the matrix power problem.

• Sebastian Dörn, Thomas Thierauf, Quantum Algorithms for Algebraic Problems, submitted to Journal, 2008.
  Abstract: In this paper we present quantum query and time complexity bounds for several group testing problems. For a set S and a binary operation on S, we consider the decision problems whether a given structure with the promise of being a groupoid, semigroup, monoid or quasigroup is in fact a semigroup, monoid, quasigroup or a group. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha [MNRS07] that improves the previous bounds by Ambainis [Amb04] and Szegedy [Sze04]. Our quantum algorithms for these problems improve the best known classical complexity bounds. We also present upper and lower bounds for testing distributivity and commutativity.

• Sebastian Dörn, Thomas Thierauf, The Quantum Complexity of Group Testing, Proceedings of SOFSEM'08, 2008.
  Abstract: We present quantum query and time complexity bounds for group testing problems. For a set S and a binary operation on S, we consider the decision problem whether a groupoid, semigroup or quasigroup is a group. Our quantum algorithms for these problems improve the best known classical complexity bounds. We also present upper and lower bounds for testing associativity, distributivity and commutativity.

2007

• Sebastian Dörn, Quantum Complexity of Graph and Algebraic Problems, Dissertation, University of Ulm, 2007.
  Abstract: In our thesis we present new quantum algorithms for graph and algebra problems.

• Sebastian Dörn, Thomas Thierauf, The Quantum Query Complexity of Algebraic Properties, Proceedings of FCT'07, 2007.
  Abstract: We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation, we consider the decision problem whether S is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems  that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha, that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
  
  
• Sebastian Dörn, Quantum Algorithms for Graph Traversals and Related Problems, Proceedings of CIE'07, 2007.
  Abstract: We study the complexity of algorithms for graph traversal problems on quantum computers. More precisely, we look at eulerian tours, hamiltonian tours, travelling salesman problem and project scheduling. We present quantum algorithms and quantum lower bounds for these problems. We prove that the quantum algorithms for the eulerian tour and the project scheduling problem are optimal in the query model.
      
• Sebastian Dörn, Quantum Algorithms for Optimal Graph Traversal Problems, Proceedings of Quantum Information and Computation V, 2007.
  Abstract: We study the quantum complexity of algorithms for optimal graph traversal problems. We look at eulerian tours, optimal postman tours, approximation of travelling salesman tours and self avoiding walks. We present quantum algorithms and quantum lower bounds for these problems. Our results improve the best classical algorithms for the corresponding problems.
    
• Sebastian Dörn, Quantum Complexity Bounds for Independent Set Problems, Proceedings of SOFSEM'07 (SRF), 2007.
  Abstract: We present quantum complexity lower and upper bounds for independent set problems in graphs. In particular, we give quantum algorithms for computing a maximal and a maximum independent set in a graph. We present applications of these algorithms for some graph problems. Our results improve the best classical complexity bounds for the corresponding problems.

2004

• Sebastian Dörn, Selbstvermeidende Irrfahrten im hyperdimensionalen Gitter, Diplomarbeit, Hochschule Mittweida, 2004.
  Zusammenfassung: Ziel der Diplomarbeit ist es, selbstvermeidende Irrfahrten im d-dimensionalen Gitter zu untersuchen. Eine wichtige Frage hierbei ist die Bestimmung der Anzahl aller selbstvermeidenden Irrfahrten der Länge N von einem gegebenen Punkt aus. Nach einer Einführung in das Thema der selbstvermeidenden Irrfahrten werden Untergraphen des zweidimensionalen Gitters diskutiert, für welche sich erzeugende Funktionen für die Anzahl aller selbstvermeidenden Irrfahrten in diesen Graphen herleiten lassen. Desweiteren wird vorgestellt, wie mittels Automaten sich Irrfahrten beschreiben lassen, die keine Kurzzyklen enthalten. Anschließend wird erläutert, wie mit Hilfe der Lace Expansion eine Formel für die erzeugende Funktion der Anzahl aller selbstvermeidenden Irrfahrten zwischen zwei Punkten x; y des d-dimensionalen aufgestellt wird. Zuletzt erfolgt eine Einordnung des Problems der Bestimmung der Anzahl aller selbstvermeidenden Irrfahrten der Länge N zwischen zwei Punkten des Z2 in die Komplexitätstheorie und im besonderen in die Klasse der #P-vollständigen Probleme.