Contact tracing is critical to controlling COVID-19, but most protocols only "forward-trace" to notify people who were recently exposed. Using a stochastic branching-process model, we find that "bidirectional" tracing to identify infector individuals and their other infectees robustly improves outbreak control. In our model, bidirectional tracing more than doubles the reduction in effective reproduction number ($R_\mathsf{eff}$) achieved by forward-tracing alone, while dramatically increasing resilience to low case ascertainment and test sensitivity. The greatest gains are realised by expanding the manual tracing window from 2 to 6 days pre-symptom- onset or, alternatively, by implementing high-uptake smartphone-based exposure notification; however, to achieve the performance of the former approach, the latter requires nearly all smartphones to detect exposure events. With or without exposure notification, our results suggest that implementing bidirectional tracing could dramatically improve COVID-19 control.