Andreas BärtschiScientist in CCS-3
Postdoc in CNLS and NSEC until 2021 Theoretical Computer Science, Quantum Computing 
Office: TA-3, Bldg 508, Room 127
Mail Stop: B256
Phone: (505) 667-8734
Fax: baertschi@lanl.gov
home page Research highlight
-
A linear-depth quantum circuit for deterministic preparation of Dicke states (superpositions of n-qubit computational basis states of Hamming weight k).
Applications include (i) linear-depth circuits for deterministic preparation of arbitrary symmetric pure states and
(ii) a quasi-linear-depth circuit for quantum compression of symmetric pure states into logarithmically many qubits.
See our arXiv preprint, an example of a
5-qubit Dicke state preparation,
or a
quantum compression circuit.
-
Approximation and exact algorithms as well as hardness and inapproximability results for efficient package delivery with mobile agents,
each having a constrained energy resource β, a fuel consumption weight ω, and a maximum velocity υ.
See the Handout of my CNLS Talk or my PhD Thesis.
-
The currently best known upper bound for the conflict-free chromatic art gallery problem:
For every simple n-vertex polygon there is a conflict-free covering by at most n guards with at most 3 log n + 3 colors,
i.e., for every building an interference-free wireless reception of a whole floor can be achieved with few frequencies (the colors) and few antennas (the guards).
See the full paper at SoCG 2014.
-
I was Organizing Committee Chair of the European Girls' Mathematical Olympiad 2017 in Zürich, Switzerland with
around 400 Participants, 44 Teams and a ~600,000 USD budget.
See our homepage www.egmo2017.ch,
the official EGMO website www.egmo.org,
or the Final Report.
|  | Educational Background/Employment:- PhD Computer Science (2017), Advisor: Peter Widmayer, ETH Zürich
- MSc Mathematics (2011), BSc Mathematics (2009), ETH Zürich
- Employment before joining LANL in October 2018:
- 2018: Postdoctoral Research Associate, Department of Computer Science D-INFK, ETH Zürich
- 2013 ‐ 2017: Research and Teaching Assistant, Department of Computer Science D-INFK, ETH Zürich
- 2012 ‐ 2013: Mathematics and ICT Teacher, Kathmandu International Study Center KISC (Swiss civilian service)
- 2012: Research Assistant, Swiss Federal Institute for Forest, Snow and Landscape Research WSL (Swiss civilian service)
- 2011: Visiting Research Scholar, Host: Subhash Suri, University of California, Santa Barbara
- Professional Teaching Certification: Didaktikzertifikat (2011, to teach at college level) and Lehrdiplom (2019, to teach at high school level), Mathematics, ETH Zürich
Research Interests:
My research interests lie in quantum computing and in combinatorial optimization, in particular how methods from the two areas inform each other. For example, I work on quantum algorithms for solving approximate optimization problems, but also on graph theory methods to compile quantum circuits and Ising models to current noisy and intermediate scale quantum (NISQ) hardware, such as:
- Quantum Alternating Operator Ansatz (QAOA),
including initial state preparation and the design, compilation and analysis of mixing operators and phase-separation operators;
- Quantum Annealing with D-Wave,
including classical preprocessing and graph embedding tasks.
Selected Recent Publications:
The publications below are based on work done up to the end of my Postdoc in March 2021.
Recent publication lists are available on Google Scholar or in the DBLP Computer Science Bibliography.
Peer-reviewed journals:
- Abhijith J., with others, Stephan Eidenbenz, Andreas Bärtschi, Patrick J. Coles, Marc Vuffray, and Andrey Y. Lokhov.
Quantum Algorithm Implementations for Beginners.
ACM Transactions on Quantum Computing, 3(4):18:1–18:92, 2022.
doi:10.1145/3517340,
arXiv:1804.03719.
- John Golden, Andreas Bärtschi, Daniel O'Malley, and Stephan Eidenbenz.
Fair Sampling Error Analysis on NISQ Devices.
ACM Transactions on Quantum Computing, 3(2):8:1–8:23, 2022.
doi:10.1145/3510857,
arXiv:2101.03258.
- Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, and Matúš Mihalák.
Near-gathering of energy-constrained mobile agents.
Theoretical Computer Science 849:35–46, 2021.
doi:10.1016/j.tcs.2020.10.008.
- Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, and Matúš Mihalák.
Collaborative delivery with energy-constrained mobile robots.
Theoretical Computer Science 810:2–14, 2020.
doi:10.1016/j.tcs.2017.04.018.
- Andreas Bärtschi and Subhash Suri.
Conflict-Free Chromatic Art Gallery Coverage.
Algorithmica 68(1):265–283, 2014.
doi:10.1007/s00453-012-9732-5.
Peer-reviewed conference proceedings:
- Elijah Pelofske, John Golden, Andreas Bärtschi, Daniel O'Malley, and Stephan Eidenbenz.
Sampling on NISQ Devices: "Who's the Fairest One of All?".
IEEE International Conference on Quantum Computing and Engineering, QCE'21, 207–217, 2021.
doi:10.1109/QCE52317.2021.00038.
arXiv:2107.06468.
- John Golden, Andreas Bärtschi, Daniel O'Malley, and Stephan Eidenbenz.
Threshold-Based Quantum Optimization.
IEEE International Conference on Quantum Computing and Engineering, QCE'21, 137–147, 2021.
doi:10.1109/QCE52317.2021.00030.
arXiv:2106.13860.
- Andreas Bärtschi and Stephan Eidenbenz.
Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation.
IEEE International Conference on Quantum Computing and Engineering, QCE'20, 72–82, 2020.
doi:10.1109/QCE49297.2020.00020,
arXiv:2006.00354.
- Jeremy Cook, Stephan Eidenbenz and Andreas Bärtschi.
The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover.
IEEE International Conference on Quantum Computing and Engineering, QCE'20, 83–92, 2020.
doi:10.1109/QCE49297.2020.00021,
arXiv:1910.13483.
- Stefanie Zbinden, Andreas Bärtschi, Hristo Djidjev and Stephan Eidenbenz.
Embedding Algorithms for Quantum Annealers with Chimera and Pegasus Connection Topologies.
International Conference on High Performance Computing, ISC HPC'20, 187–206, 2020.
doi:10.1007/978-3-030-50743-5_10.
- Andreas Bärtschi and Stephan Eidenbenz.
Deterministic Preparation of Dicke States.
22nd International Symposium on Fundamentals of Computation Theory FCT'19, 126–139, 2019.
doi:10.1007/978-3-030-25027-0_9,
arXiv:1904.07358.
- Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, and Matúš Mihalák.
Near-gathering of energy-constrained mobile agents.
26th International Colloquium on Structural Information and Communication Complexity SIROCCO'19, 52–65, 2019.
doi:10.1007/978-3-030-24922-9_4.
- Andreas Bärtschi, Daniel Graf, and Matúš Mihalák.
Collective Fast Delivery by Energy-Efficient Agents.
43rd International Symposium on Mathematical Foundations of Computer Science MFCS'18, 56:1–56:16, 2018.
doi:10.4230/LIPIcs.MFCS.2018.56,
arXiv:1809.00077.
- Andreas Bärtschi and Thomas Tschager.
Energy-Efficient Fast Delivery by Mobile Agents.
21st International Symposium on Fundamentals of Computation Theory FCT'17, 82–95, 2017.
doi:10.1007/978-3-662-55751-8_8.
- Andreas Bärtschi, Daniel Graf, and Paolo Penna.
Truthful Mechanisms for Delivery with Agents.
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems ATMOS'17, 2:1–2:17, 2017.
doi:10.4230/OASIcs.ATMOS.2017.2,
arXiv:1702.07665.
- Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna.
Energy-efficient Delivery by Heterogeneous Mobile Agents.
34th International Symposium on Theoretical Aspects of Computer Science STACS'17, 10:1–10:14, 2017.
doi:10.4230/LIPIcs.STACS.2017.10,
arXiv:1610.02361.
- Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, and Matúš Mihalák.
Collaborative Delivery with Energy-Constrained Mobile Robots.
23rd International Colloquium on Structural Information and Communication Complexity SIROCCO'16, 258–274, 2016.
doi:10.1007/978-3-319-48314-6_17,
arXiv:1608.08500.
- Andreas Bärtschi, Barbara Geissmann, Daniel Graf, Tomas Hruz, Paolo Penna, and Thomas Tschager.
On Computing the Total Displacement Number via Weighted Motzkin Paths.
27th International Workshop on Combinatorial Algorithms IWOCA'16, 423–434, 2016.
doi:10.1007/978-3-319-44543-4_33,
arXiv:1606.05538.
- Andreas Bärtschi and Fabrizio Grandoni.
On Conflict-Free Multi-coloring.
14th International Symposium on Algorithms and Data Structures WADS'15, 103–114, 2015.
doi:10.1007/978-3-319-21840-3_9.
- Andreas Bärtschi, Subir Kumar Ghosh, Matúš Mihalák, Thomas Tschager, and Peter Widmayer.
Improved bounds for the conflict-free chromatic art gallery problem.
30th International Symposium on Computational Geometry SoCG'14, 144–153, 2014.
doi:10.1145/2582112.2582117.
- Andreas Bärtschi and Subhash Suri.
Conflict-free Chromatic Art Gallery Coverage.
29th International Symposium on Theoretical Aspects of Computer Science STACS'12, 160–171, 2012.
doi:10.4230/LIPIcs.STACS.2012.160.
Other:
- Andreas Bärtschi.
Efficient Delivery with Mobile Agents.
Doctoral Thesis, ETH Zürich, 2017.
doi:10.3929/ethz-b-000232464.
- Andreas Bärtschi.
Spieltheorie.
Unterrichtsmaterialien Mathematik, 2011.
EducETH.
Invited Talks:
- QLunch, University of Copenhagen, and QIT Group Seminar, ETH Zürich:
Preparation and Compression of Symmetric Pure Quantum States, August 2019.
A talk on circuits for symmetric pure quantum states, extending work on Dicke states published at FCT 2019.
Slides.
- CASIS "Quantum Sensing and Information Processing" Summer Lecture Series, Lawrence Livermore National Laboratory:
Quantum Computing Algorithms, July/August 2019.
Introduction to quantum algorithms with interactive circuit examples.
Lecture Series with Video,
Slides,
Interactive Examples.
- ISTI Seminar Series, Los Alamos National Laboratory:
Efficient Delivery by Heterogeneous Mobile Agents, August 2017.
A whiteboard talk on time-sensitive and energy-efficient transportation problems.
- DKE, Maastricht University:
Energy-efficient Delivery by Heterogeneous Mobile Agents, June 2017.
A talk based on work published at STACS 2017.
Slides.
- LIF, Aix-Marseille University:
Collaborative Delivery with Energy-Constrained Mobile Robots, December 2016.
A blackboard talk based on work published at SIROCCO 2016.
- 11th Swiss Scientific Olympiads Day, University of Bern:
Vom Plattenleger zum Plattenputzer, October 2015.
A talk on coloring problems in mathematical olympiads and in computer science research.
Slides.
|
