-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
292 lines (261 loc) · 13.9 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
<html lang="en-US">
<html>
<head>
<title>William Kretschmer</title>
<style type="text/css">
html {
max-width: 1000px
}
li {
margin-top: 1em;
line-height: 125%;
}
body {
font-family: Verdana, Helvetica, Arial, sans-serif;
font-size:15px;
}
a {
color: #c75300; /* previously cc5500, see https://webaim.org/resources/contrastchecker/ */
text-decoration:none;
font-weight : 300;
}
a:hover {
color: #c75300;
text-decoration:underline;
}
</style>
<meta name="google-site-verification" content="UQqN7qwSyg9KufZL6QRNKM5mboqUKMss2hTebd3r45c" />
</head>
<body>
<div id="main">
<h1 align="left">William Kretschmer</h1>
</div>
<div id="about">
<img src="me.jpg" alt="William Kretschmer" style="float:right; width:150px; padding:1em"/>
<h2 align="left">About</h2>
<p>I am a Quantum Postdoctoral Fellow at the Simons Institute for the Theory of Computing. Previously, I did my PhD at UT Austin, where I was fortunate to have <a href="https://scottaaronson.com/">Scott Aaronson</a> as my PhD advisor. Before that, I was an undergrad in Mathematics with Computer Science at MIT.</p>
<p>My research lies broadly in quantum computational complexity theory. Much of my work focuses on (limitations of) quantum algorithms and (in)ability to apply classical algorithmic techniques in quantum computation. Some common topics of study in my research include query complexity, structural complexity, pseudorandom quantum states, learning theory, and the stabilizer formalism, especially as they apply to computational problems involving quantum states and unitary transformations.
</p>
<p>Interested in learning more about my work? Check out this <a href="https://www.quantamagazine.org/cryptographers-discover-a-new-foundation-for-quantum-secrecy-20240603">Quanta Magazine article</a> about my (and others') research on quantum state complexity.</p>
<p>On the side, I have a large interest in combination puzzles, especially Rubik's-type "twisty puzzles". Some of my non-CS theory papers below grew out of this interest. I have also designed more than a dozen unique 3D-printed twisty puzzles, all of which have been shared on the <a href="https://www.twistypuzzles.com/forum/">Twisty Puzzles forum</a>, and most of which can be found in the <a href="http://twistypuzzles.com/cgi-bin/pdb-search.cgi?act=inv&key=297">Twisty Puzzles museum</a>. Many of my designs are also <a href="http://twistypuzzles.com/forum/viewtopic.php?p=365854#p365854">available for download</a>. </p>
</div>
<div id="contact">
<h2 align="left">Contact</h2>
<b>Email:</b> (first 7 letters of last name, all lowercase)@berkeley.edu
<br>
<b>Office:</b> 314 Calvin Lab
</div>
<div id="scholar">
<p>
<a href="https://scholar.google.com/citations?user=gckWFYUAAAAJ">Google Scholar profile</a>
</p>
</div>
<div id="publications">
<h2 align="left">Publications</h2>
<ol reversed>
<li>
<b>Learning the closest product state</b>
<br>
<a href="https://www.aineshbakshi.com//">Ainesh Bakshi</a>, <a href="https://www.johnbostanci.com/">John Bostanci</a>, William Kretschmer, <a href="https://people.eecs.berkeley.edu/~landau/index.htm">Zeph Landau</a>, <a href="https://jerryzli.github.io/">Jerry Li</a>, <a href="https://aliu42.github.io/">Allen Liu</a>, <a href="https://www.cs.cmu.edu/~odonnell/">Ryan O'Donnell</a>, <a href="https://ewintang.com/">Ewin Tang</a>
<br>
<a href="https://arxiv.org/abs/2411.04283">[arXiv]</a>
</li>
<li>
<b>Quantum-Computable One-Way Functions without One-Way Functions</b>
<br>
William Kretschmer, <a href="https://qcry.pt/">Luowen Qian</a>, <a href="https://www.avishaytal.org/">Avishay Tal</a>
<br>
<a href="https://arxiv.org/abs/2411.02554">[arXiv]</a>
</li>
<li>
<b>Agnostic Tomography of Stabilizer Product States</b>
<br>
<a href="https://sabeegrewal.com/">Sabee Grewal</a>, <a href="https://vishnuiyer.org/">Vishnu Iyer</a>, William Kretschmer, <a href="https://daniel-you-liang.github.io/">Daniel Liang</a>
<br>
<a href="https://arxiv.org/abs/2404.03813">[arXiv]</a>
</li>
<li>
<b>Pseudoentanglement Ain't Cheap</b>
<br>
<a href="https://sabeegrewal.com/">Sabee Grewal</a>, <a href="https://vishnuiyer.org/">Vishnu Iyer</a>, William Kretschmer, <a href="https://daniel-you-liang.github.io/">Daniel Liang</a>
<br>
Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)
<br>
<a href="https://arxiv.org/abs/2404.00126">[arXiv]</a>
</li>
<li>
<b>Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates</b>
<br>
<a href="https://sabeegrewal.com/">Sabee Grewal</a>, <a href="https://vishnuiyer.org/">Vishnu Iyer</a>, William Kretschmer, <a href="https://daniel-you-liang.github.io/">Daniel Liang</a>
<br>
Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024)
<br>
<a href="https://arxiv.org/abs/2305.13409">[arXiv]</a>
</li>
<li>
<b>Improved Stabilizer Estimation via Bell Difference Sampling</b>
<br>
<a href="https://sabeegrewal.com/">Sabee Grewal</a>, <a href="https://vishnuiyer.org/">Vishnu Iyer</a>, William Kretschmer, <a href="https://daniel-you-liang.github.io/">Daniel Liang</a>
<br>
Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024)
<br>
<i>Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)</i>, pp. 1352–1363 (2024)
<br>
<a href="https://arxiv.org/abs/2304.13915">[arXiv]</a> <a href="https://doi.org/10.1145/3618260.3649738">[STOC 2024]</a>
</li>
<li>
<b>Two-Disk Compound Symmetry Groups</b>
<br>
<a href="https://scholar.google.com/citations?user=kqB200YAAAAJ&hl=en">Robert A. Hearn</a>, William Kretschmer, <a href="https://tomas.rokicki.com/">Tomas Rokicki</a>, Benjamin Streeter, Eric Vergo
<br>
<i>Proceedings of Bridges 2023: Mathematics, Art, Music, Architecture, Culture</i>, pp. 29–36 (2023)
<br>
<a href="https://arxiv.org/abs/2302.12950">[arXiv]</a> <a href="http://archive.bridgesmathart.org/2023/bridges2023-29.html">[Bridges 2023]</a>
</li>
<li>
<b>A Qubit, a Coin, and an Advice String Walk Into a Relational Problem</b>
<br>
<a href="https://www.scottaaronson.com/">Scott Aaronson</a>, <a href="https://homepages.cwi.nl/~buhrman/">Harry Buhrman</a>, William Kretschmer
<br>
<i>15th Innovations in Theoretical Computer Science Conference (ITCS 2024)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>287</b>, pp. 1:1–1:24 (2024)
<br>
<a href="https://arxiv.org/abs/2302.10332">[arXiv]</a> <a href="https://eccc.weizmann.ac.il/report/2023/015">[ECCC]</a> <a href="https://doi.org/10.4230/LIPIcs.ITCS.2024.1">[ITCS 2024]</a>
</li>
<li>
<b>Quantum Mass Production Theorems</b>
<br>
William Kretschmer
<br>
<i>18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>266</b>, pp. 10:1–10:21 (2023)
<br>
<a href="https://arxiv.org/abs/2212.14399">[arXiv]</a> <a href="https://doi.org/10.4230/LIPIcs.TQC.2023.10">[TQC 2023]</a>
</li>
<li>
<b>Quantum Cryptography in Algorithmica</b>
<br>
William Kretschmer, <a href="https://qcry.pt/">Luowen Qian</a>, <a href="https://makrandsinha.github.io/">Makrand Sinha</a>, <a href="https://www.avishaytal.org/">Avishay Tal</a>
<br>
Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023)
<br>
Presented at the 13th Annual Conference on Quantum Cryptography (QCrypt 2023) as an invited talk
<br>
Presented at the 5th Conference on Information-Theoretic Cryptography (ITC 2024) as an invited talk
<br>
<i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)</i>, pp. 1589–1602 (2023)
<br>
<a href="https://arxiv.org/abs/2212.00879">[arXiv]</a> <a href="https://doi.org/10.1145/3564246.3585225">[STOC 2023]</a>
</li>
<li>
<b>Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom</b>
<br>
<a href="https://sabeegrewal.com/">Sabee Grewal</a>, <a href="https://vishnuiyer.org/">Vishnu Iyer</a>, William Kretschmer, <a href="https://daniel-you-liang.github.io/">Daniel Liang</a>
<br>
<i>14th Innovations in Theoretical Computer Science Conference (ITCS 2023)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>251</b>, pp. 64:1–64:20 (2023)
<br>
<b>ITCS 2023 Best Student Paper Award</b>
<br>
<a href="https://arxiv.org/abs/2209.14530">[arXiv]</a> <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.64">[ITCS 2023]</a>
</li>
<li>
<b>The Acrobatics of BQP</b>
<br>
<a href="https://www.scottaaronson.com/">Scott Aaronson</a>, DeVon Ingram, William Kretschmer
<br>
Presented at the 25th Annual Conference on Quantum Information Processing (QIP 2022) as a short plenary talk
<br>
<i>37th Computational Complexity Conference (CCC 2022)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>234</b>, pp. 20:1–20:17 (2022)
<br>
<b>CCC 2022 Best Paper Award</b>
<br>
<a href="https://arxiv.org/abs/2111.10409">[arXiv]</a> <a href="https://eccc.weizmann.ac.il/report/2021/164/">[ECCC]</a> <a href="https://doi.org/10.4230/LIPIcs.CCC.2022.20">[CCC 2022]</a>
</li>
<li>
<b>Quantum Pseudorandomness and Classical Complexity</b>
<br>
William Kretschmer
<br>
<i>16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>197</b>, pp. 2:1–2:20 (2021)
<br>
<a href="https://arxiv.org/abs/2103.09320">[arXiv]</a> <a href="https://doi.org/10.4230/LIPIcs.TQC.2021.2">[TQC 2021]</a>
</li>
<li>
<b>The Quantum Supremacy Tsirelson Inequality</b>
<br>
William Kretschmer
<br>
Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021)
<br>
<i>12th Innovations in Theoretical Computer Science Conference (ITCS 2021)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>185</b>, pp. 13:1–13:13 (2021)
<br>
<i>Quantum</i> <b>5</b>, 560 (2021)
<br>
<a href="https://arxiv.org/abs/2008.08721">[arXiv]</a> <a href="https://doi.org/10.4230/LIPIcs.ITCS.2021.13">[ITCS 2021]</a> <a href="https://quantum-journal.org/papers/q-2021-10-07-560/">[Journal]</a>
</li>
<li>
<b>Symmetries, graph properties, and quantum speedups</b>
<br>
<a href="https://cs.uwaterloo.ca/~s4bendav/">Shalev Ben-David</a>, <a href="https://www.cs.umd.edu/~amchilds/">Andrew M. Childs</a>, <a href="http://gilyen.hu/">András Gilyén</a>, William Kretschmer, <a href="https://sites.google.com/site/supartha/">Supartha Podder</a>, <a href="https://daochenw.github.io/">Daochen Wang</a>
<br>
Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021)
<br>
<i>Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020)</i>, pp. 649–660 (2020)
<br>
<a href="https://arxiv.org/abs/2006.12760">[arXiv]</a> <a href="https://doi.org/10.1109/FOCS46700.2020.00066">[FOCS 2020]</a>
</li>
<li>
<b>Lower Bounding the AND-OR Tree via Symmetrization</b>
<br>
William Kretschmer
<br>
<i>ACM Transactions on Computation Theory</i> 13:1 (2021)
<br>
<a href="https://arxiv.org/abs/1907.06731">[arXiv]</a> <a href="https://doi.org/10.1145/3434385">[Journal]</a>
</li>
<li>
<b>Quantum Lower Bounds for Approximate Counting via Laurent Polynomials</b>
<br>
<a href="https://www.scottaaronson.com/">Scott Aaronson</a>, <a href="http://www.robinkothari.com/">Robin Kothari</a>, William Kretschmer, <a href="https://people.cs.georgetown.edu/jthaler/">Justin Thaler</a>
<br>
Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020)
<br>
<i>35th Computational Complexity Conference (CCC 2020)</i>, Leibniz International Proceedings in Informatics (LIPIcs) <b>169</b>, pp. 7:1–7:47 (2020)
<!--<br>
Subsumes <a href="https://arxiv.org/abs/1808.02420">arXiv:1808.02420</a> by Scott Aaronson and <a href="https://arxiv.org/abs/1902.02398">arXiv:1902.02398</a> by William Kretschmer.-->
<br>
<a href="https://arxiv.org/abs/1904.08914">[arXiv]</a> <a href="https://eccc.weizmann.ac.il/report/2019/062/">[ECCC]</a> <a href="https://doi.org/10.4230/LIPIcs.CCC.2020.7">[CCC 2020]</a>
<br>
</li>
<li>
<b>Simulation of Qubit Quantum Circuits via Pauli Propagation</b>
<br>
<a href="https://www.patrickrall.com/">Patrick Rall</a>, <a href="https://daniel-you-liang.github.io/">Daniel Liang</a>, Jeremy Cook, William Kretschmer
<br>
<i>Physical Review A</i> <b>99</b>, 062337 (2019)
<br>
<a href="https://arxiv.org/abs/1901.09070">[arXiv]</a> <a href="https://journals.aps.org/pra/abstract/10.1103/PhysRevA.99.062337">[Journal]</a>
</li>
<li>
<b>Structured Factored Inference for Probabilistic Programming</b>
<br>
Avi Pfeffer, <a href="https://scholar.google.com/citations?hl=en&user=2UVuWVwAAAAJ">Brian Ruttenberg</a>, William Kretschmer, Alison O'Connor
<br>
<i>Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018)</i>, Proceedings of Machine Learning Research <b>84</b>, pp. 1224–1232 (2018)
<br>
<a href="http://proceedings.mlr.press/v84/pfeffer18a.html">[PMLR]</a>
</li>
<li>
<b>Groups in Circle Puzzles</b>
<br>
William Kretschmer
<br>
<i>Game and Puzzle Design</i> 3:2, pp. 15–26 (2017)
<br>
<a href="http://gapdjournal.com/issues/issue-3-2/gapd-3-2-03-groups-sample.pdf">[Journal]</a>
</li>
</ol>
</div>
<div id="updated">
Last updated: November 8, 2024
</div>
</body>
</html>