Hello!
Hi! My name’s Alex Meiburg.
I’m at postdoc at University of Waterloo’s IQC and the Perimeter Institute. My interests generally consist of quantum information and quantum complexity theory. I got my physics PhD at UC Santa Barbara in June 2023, advised by Bela Bauer, funded by Microsoft Station Q. My undergrad was at Caltech where I earned a dual B.S. in Math and Physics.
This site
I’ve got a few pages you might like, if you like complexity theory, graph theory, or math in general.
I have a page for discussing different types of graph substrcture, such as the different ways to combine graphs together, modify them, or recognize different types of graph ‘containment’. There’s a related page for graph parameters.
I collect fun math terms. Please let me know about other ones to add!
And then I (try to) maintain a browseable complexity zoo. This is based on the Complexity Zoo wiki, but mine aims to be machine readable. This is the pretty viewer and this is the GitHub repo if you have suggestions.
Stuff I’ve Done
Below I’ve gathered my more successful pursuits. You can also check out my blog, email me (click to show), or look at other links. Here’s a link to my resume.
Papers
- In 2016, I became interested in the CSP Dichotomy Conjecture, which was proved independently by Zhuk and Bulatov at essentially the same time in 2017. This states that all constraint problems are in P or are NP-Complete. Since quantum constraint problems were known to include at least the additional cases of QMA_1, and MA, I wanted to know what other possibilities there were – the obvious one being BQP, the problems efficiently solvable by a quantum computer. I successfully showed this in 2021, also getting the cases QCMA and coRP in the process.
- I was trying to work out some more exact formulas for Quantum State Tomography when I realized that the expressions were in fact matrix permanents. I failed to find an efficient algorithm for computing these formulas, and instead showed that they were NP-hard to compute. But, this resolved an important open problem about the hardness of Positive Semidefinite Permanents, which arise in thermal BosonSampling problems and has been discussed in several contexts. The paper was presented at FOCS 2022.
- My first paper with my advisor has involved applying Gaussian Fermionic Matrix Product States to more efficiently simulate quasi-1D fermion systems (read: problems involving electrons, where the material is much longer than it is wide). We showed that we could use this to e.g. explore superconductivity at weak couplings much faster and more accurately.
- My second paper with my advisor is on better inference of Green’s functions from noisy NISQy samaples, based on his prior work. It seems to reasonably provide a factor of ~100x improvement on sample complexity, on problems of interest.
- An internship with Zapata Computing in Summer 2022 lead to a work on extending Matrix Product States to continuous-valued data. Paper still in preparation, but I presented on it at March Meeting 2023.
On the less serious side,
- The summer before college I worked with the Climate Hazards Center at UCSB’s Geography department. My small portion of the work consisted of trying various ways to filter clouds out of infrared satellite imagery, in order to infer a more complete temperature record. The paper has more citations than the rest of my work combined, ironically.
- I’m interested in the PACE challenge, and I participated in the 2022 version, of computing a minimal Directed Feedback Vertex Set. My submission was the second-highest scoring, but a bug at submission time (fixed shortly after) disqualified it from a prize. The submission was somewhat unique in that I did not code any search routines whatsoever: it just (very) aggressively simplifies the problem, and then hands it off to an ILP optimizer (SCIP). 🥲 Code is here, writeup is here.
- This led to development of Java support for SCIP, a separate project here.
- There’s a cute question regarding the convergence of the Flint-Hills series and the irrationality measure of Pi. This was pointed out in a work of Max Alekseyev. I was able to prove a converse, at which point I was informed that the converse had already been proven in a MathOverflow comment!
In the likely event that this page is out of date (Last Updated: Jun 2023), you can check my Google Scholar.
Presentations
You can see my PhD defense and accompanying slides.
Here’s my Advancement to Candidacy presentation, which was on the BQP-complete constraint problems.
This was my presentations on PSD permanent hardness for FOCS 2022.
This was my presentation on generalized Hartree-Fock, for APS March Meeting 2022.
This was my presentation (PPT) on Continuous-valued Matrix Product States, for APS March Meeting 2023.
Teaching
In Fall 2022, I taught a course on numerical algorithms for engineers. Course webpage here.
Computer Security
In high school I co-founded 1064CBread, a competitive computer-hacking team. We won first place in PicoCTF 2013, which was aimed at high schoolers. We then decided to aim higher at the college-level CSAW CTF. To our surprise, we qualified for the finals, and got to fly across the country to NYC. After that we had a decently successful run, becoming finalists or winners in quite a number of competitions and winning prize money here and there. Although we’ve been less active in recent years, we were finalists in Hack-A-Sat 2020, an Air Force competition about satellite hacking, where we won $10k and a satellite.
You can find a lot of my writeups on my blog. The team also has a Github repo, and a CTFTime page.
I’ve also played with UCSB’s team Shellphish a few times, although I’ve never been a core member by any means.
Vulnerabilities
In 2016, I found a security vulnerability in Facebook Messenger and received a bug bounty for reporting it. They promptly fixed it.
In 2012 I found a trivially exploitable vulnerability in a popular online education platform. They have still have not patched it, despite a few reminders on my part.
In 2020 I found a vulnerability in a popular online cloud computing platform. It was patched quicky, but sadly I did not receive a bounty, and they’ve expressed that they would prefer I not talk about it publically – as some users likely using old versions of the software locally and could remain vulnerable.
Finance
I’ve enjoyed applying my math knowledge to win some money with Quantiacs. My code has managed several million USD for them over the years, and they came to Caltech and did an inteview with me. It’s given me a useful side-income. I think that a worrying large fraction of quantitative finance is essentially numerology, and that approaches should either rely on news and principals (which I will readily I admit I know nothing about) or principled mathematical foundations - not just drawing lines on a graph or magic numbers.
Here are some examples of “explanations” that I think are, frankly, garbage: 1, 2, 3.
I’m legally required, I think, to make clear that I’m not providing investment advice! - but if you want to talk math and stocks, I’d be happy to chat. Just email.
Fun
I enjoy the card game Magic: the Gathering and have a page to sort and search through my pretty sizable card collection. It intelligently cross-references with Scryfall, to allow more sophisticated searching. I also had a phone-based scavenger hunt that I used to propose to my now-wife.
I made a simple little game and got it featured on Steam! It’s called Quatris and it’s Free, wow, what a steal! I made it with my friends Charlie and Cole in high school but didn’t put it online until a while later. Hey, it even has achievements!
I enjoy attending MIT Mystery Hunt each year, and other, similar, events.
Back in high school I ran a coded chat platfom for fans of the webcomic https://www.homestuck.com/ to hang out together. During its prime years, the site had roughly 100k distinct monthly users.