Witness for the Prosecution is a 1957 American legal mystery thriller film directed by Billy Wilder. The film, which has elements of bleak black comedy and film noir, is a courtroom drama set in the Old Bailey in London and is based on the 1953 play of the same name by Agatha Christie.
Witness is a 1985 American neo-noir crime thriller film directed by Peter Weir, and starring Harrison Ford. The film went on to become a sleeper hit, grossing over $116 million worldwide (on a budget of $12 million). At the 58th Academy Awards, it earned eight nominations, including Best Picture and Best Actor for Ford, winning Best Original Screenplay and Best Film Editing.
This post is a companion to our new work Interior-point and First-order Methods for Quantum Entanglement Detection, to be presented by Javier Pena at Informs Optimization Society (IOS) Conference in Houston on March 24th.
This line of research is line with my overall program (that I presented at Princeton last year, abstract below):
Quantum Operations Research: Algorithms, Hardware, Applications.
Integer Programming. Queuing. Markov Decision Processes. Semi-definite Programs. These are some of fundamental methodologies in Operations Research (OR) that are used to tackle practical applications from Business (Supply Chain, Finance), Engineering (Communication Networks) and Medicine (Cancer Genomics, Image Recognition). At Tepper Quantum Group, we are exploring the twin questions: (a) what can quantum do for OR and (b) what can OR do for quantum. In this talk, I will present an overview of our progress in (a) Graver Augmented Multi-seed Algorithm (GAMA), a novel hybrid quantum-classical algorithm, for non-linear integer programs, with application to hedge funds, cancer genomics and supply chains; and (b) Ising Hardware (Photonics, Floquet Engineering). If time permits, I will briefly mention queuing analyses for quantum communications (buffering, entanglement switch) and introduce Quantum Information Science (QIS) generally via SDP. It is my hope that this overview will create collaboration opportunities in identifying new applications, building novel hardware or conceiving innovative algorithms utilizing, and enhancing, quantum information science and technologies.
Entanglement is mathematically defined as Not Separable.
A Separation is a 2011 Iranian drama film written and directed by Asghar Farhadi. It won the Academy Award for Best Foreign Language Film in 2012, becoming the first Iranian film to win the award. It had box office of over $24 million (on a budget of $800,000).
Let us think like this:
Separable: Innocent == Entangled: Guilty.
Suppose, you, as a prosecutor, is trying to prove that the accused (quantum state) is guilty (entangled). Just like one is innocent until proven guilty, we have to work in the belief that a given state is separable until it is proven to be entangled.
Presumed Innocent is a 1990 American legal thriller film based on the 1987 novel of the same name by Scott Turow. Directed by Alan J. Pakula, and written by Pakula and Frank Pierson, it stars Harrison Ford. The film follows Rusty Sabich (Ford), a prosecutor who is charged with the murder of his colleague and mistress. It grossed $221 million worldwide (on a budget of $20 million).
If you want to prove that some quantum state is entangled, you have to show that it is not separable, that is, it is not innocent, and so you have to provide a witness that can remove all doubt of its alleged innocence. Otherwise, you will get a “not guilty, your honor” decision from the jury, which does not mean that the person is innocent, but just that you could not, beyond a reasonable doubt, prove that they were guilty.
An Entanglement Witness (EW) is a powerful concept and tool in quantum information theory used to detect entanglement in quantum systems.
An entanglement witness is an observable (a Hermitian operator) whose expectation value can distinguish between entangled and separable states. A negative expectation value of an entanglement witness indicates the presence of entanglement.
It is possible to formulate this as a Semi-definite Program (SDP). See my (with Vikesh Siddhu) tutorial Five Starter Pieces: Quantum Information Science via Semi-definite Programs, that I presented in Indianapolis in 2022. This formulation is not new.
So, what is our contribution?
We explicitly construct both primal and dual feasible solutions – Double Feasibility – and are also able to bound the duality gap.
The dual feasible solution is relatively straightforward to construct.
The construction of the primal feasible solution is based on generalized Gell-Mann matrices.☺️
Double Indemnity is a 1944 American crime thriller film noir directed by Billy Wilder, co-written by Wilder and Raymond Chandler, and produced by Buddy DeSylva and Joseph Sistrom. The screenplay was based on James M. Cain‘s 1943 novel of the same title.
Wilder considered Double Indemnity his best film in terms of having the fewest scripting and shooting errors, and always maintained that the two things he was proudest of in his career were the compliments he received from Cain about Double Indemnity and from Agatha Christie for his handling of her Witness for the Prosecution.
Bound is a 1996 American neo-noir crime thriller film written and directed by the Wachowskis. Bound was the first film directed by the Wachowskis, and they took inspiration from Billy Wilder to tell a noir story filled with sex and violence.
Primal Fear is a 1996 American legal mystery crime thriller film directed by Gregory Hoblit, based on the 1993 novel of the same name by William Diehl. It stars Richard Gere, Laura Linney, John Mahoney, Alfre Woodard, Frances McDormand and Edward Norton in his film debut. The film follows a Chicago defense attorney who believes that his altar boy client is not guilty of murdering a Catholic archbishop. The film was a box office success and received positive reviews, making $102 million (on a budget of $30 million).
The Matrix (see Looking Back: March 31, 1999) is a 1999 science fiction action film written and directed by the Wachowskis. The Wachowskis’ approach to action scenes was influenced by anime and martial arts films (particularly fight choreographers and wire fu techniques from Hong Kong action cinema); other influences include Plato’s Cave and 1990s Telnet hacker communities. The film was a box office success, grossing over $460 million on a $63 million budget. The film received nominations at the 72nd Academy Awards for Best Visual Effects, Best Film Editing, Best Sound, and Best Sound Editing, winning all four categories.
These steps allows us to provide worst-case complexity bound on the number of interior-point steps needed. Of course, the number of steps depend on how “entangled” the state is.
Entanglement robustness is a quantitative measure of the resilience of quantum entanglement in the presence of noise, disturbances, or interactions with an environment. It provides a way to gauge how strongly entangled a quantum state is and how well it can maintain its entanglement properties under less-than-ideal conditions.
Putting it all together:
We get the complexity result displayed in the bottom quadrant of the picture of this post.
What else?
We are able to provide entanglement witnesses for certain special cases without solving SDPs, including one that explicitly shows (the known result) of monogamy of entanglement.
What else?
By exploiting the structure of the polar cone, we create an alternative formulation that is amenable to First-order methods, such as Douglas-Rachford splitting, an attractive – more flexible and faster – alternative to interior point methods.
The Polar Express is a 2004 American animated Christmas adventure fantasy film directed by Robert Zemeckis, who co-wrote the screenplay with William Broyles Jr., based on the 1985 children’s book of the same name by Chris Van Allsburg. It grossed over $426 million on a budget of about $170 million.
If you are the conference, please plan to attend the session and/or stop by and say hello to Javier Pena and Ananth Tenneti (who is presenting Quantum GAGA).
