- algorithms for optimization: QAOA, approximate message-passing
- random Max-CSPs and connections to spin glasses; average-case quantum circuit lower bounds
- quantum complexity “around” QMA, including QCMA and QMA(2)

You can find all of my papers on Google Scholar or on arXiv.

Here is a wordcloud of my research.

I’m interested in technological tools that make research easier. If you have a favorite tool, please write to me!

**Writing papers**: I use Overleaf. But in the brainstorming phase, Overleaf feels way too formal, so I use HackMD. It’s still shareable and you can write in Markdown and LaTeX. I switch over when the project has enough steam.

**Reading literature**: I occasionally check SciRate (and as of 2022, I’m the project maintainer). Another graduate student at UChicago set up bots that message on Slack with all the newest CS theory papers and also all papers with “quantum” in the title. I skim through the titles of those most days. I also have Google Scholar updates which send TONS of email, so I set up scholar-alert-digest to convert it into a single page (and it archives my emails). Write to me if you want help setting this up.

**Diagrams**: My favorite is draw.io (which renamed to diagrams.net). I like its simplicity and the “Sketch” feature.

**Presentations**: I have two recommendations here:

Google Slides. They are very simple to make, and you know exactly what it looks like. I use the default templates. I use this scratchpad to write LaTeX equations and take screenshots.

I

**really**like the “Slide Mode” in HackMD. You can get a feel for it here and see an example here. I love being able to use Markdown and LaTeX; to edit from any computer and share the link easily; and to not worry much about formatting. I used it for a talk in 2023 and loved it.

August 2023 note: One downside with HackMD slides is actually exporting to PDF (vs using the online slide viewer). To do this, I use decktape. You can install it with `npm install -g decktape`

. Then run: `decktape generic 'https://hackmd.io/@kmarw/SJxRLR3DO2?controls=false&fragments=false' ~/output.pdf —-key=ArrowDown —-key=ArrowRight`

. The `?fragments=false`

only exports the slide where all slide animations/fragments have been run. (Note: sometimes the `--`

symbol doesn’t copy-paste correctly, so type it yourself.)

December 2023 note: `decktape`

is also good for exporting Google Slides to PDF with slide animations/fragments! The standard export to PDF doesn’t do this. Get the Share link, and change `/edit`

to `/present`

.

For recording videos, I record the screen with OBS and use a (cheap, small) microphone that plugs into my computer.

**Posters**: So far, I’ve made Google slides, export them as PDF, convert to PNG online, and use ImageMagick to convert them to a grid: `montage -density 2400 -tile 3x0 -geometry +0+0 -bordercolor "#000000" -border 10 *.png ../poster.png`

See also my projects related to research.

I’d love to see these solved! (updated Feb 2022)

- This one: if you solve it, let me know and we’ll finish a paper together!
- My paper has a recurrence relation to calculate the performance of the QAOA at any depth p. What happens when the depth goes to infinity? (Conjecture: it should approach the Parisi value…) If you are excited about this, let me or Eddie Farhi know.
- This paper shows a NLTS-based obstruction to low-depth quantum algorithms, including the QAOA, for Max-Cut. My later paper extends this from Max-Cut to Max-3-XOR. Can this be extended to Max-k-XOR for any k? This would be a great project to get started with theory. It might not be strong enough for a paper on its own; still, it could lead to something…
- My paper can calculate the performance of the QAOA at any depth p. Can you do the same for a local classical algorithm? If you’re interested in this, let me or Matt Hastings know.
- We don’t know much about finite Steiner systems. We know NO Steiner systems where t=6 or higher. Can you find one? See this reference.
- Is the “approximate counting” problem in QMA(2)? This problem has query complexity outside of QMA. If it’s in QMA(2), it would show a classical oracle separation of QMA and QMA(2). If you have any ideas, let me or William Kretschmer know.
- Can you use LOCC to get from a graph state of a “circle graph” to that of a grid graph? If so, any series of graph states of unbounded rank-width would be universal. If this is interesting, let me or Daniel Grier know.