text:
Meetings Coverage and Press Releases
SG/A/1826-BIO/5120-PI/2234
Secretary-General Appoints Samir Aldarabi Director of United Nations Information Centre in Manama
United Nations Secretary‑General António Guterres has appointed Samir Aldarabi as Director of the United Nations Information Centre in Manama, covering Bahrain, Qatar and the United Arab Emirates. Mr. Aldarabi assumed his duties on 1 August 2018.
Prior to this appointment, Mr. Aldarabi was the Acting Director of the United Nations Information Centre in Manama, leading the strategic communications and building understanding and support for the aims and goals of the United Nations in Bahrain, Qatar and the United Arab Emirates since June 2015.
From 2002 to 2015, Mr. Aldarabi held progressively responsible public information positions across the United Nations Secretariat. He served as Director of the United Nations Information Centre in Sana'a from 2010 to 2015, where he also joined the United Nations Special Political Mission for Yemen; as the National Deputy Director of Radio Miraya with the United Nations Mission in Sudan in Khartoum from 2009 to 2010; and as a radio producer at United Nations Headquarters from 2002 to 2009.
Before joining the United Nations, Mr. Aldarabi was the Spokesperson and Arab Press Coordinator for the Palestinian Initiative for the Promotion of Global Dialogue and Democracy, a non‑governmental organization, from 2003 to 2004; and led the media campaign for the first‑ever population, housing and establishment census at the Palestinian Bureau of Statistics from 1997 to 1998.
A national of Jordan, Mr. Aldarabi holds a Master of Arts degree in social science and United Nations studies from Long Island University in the United States, and a Bachelor of Arts degree from Bethlehem University. He is fluent in Arabic and English.
For information media. Not an official record.
Round-up of the Security Council's activities
New York, Jan-Dec 2020
Main part of the 75th session of the General Assembly
New York, Sep-Dec 2020
High-Level Meetings of the 75th General Assembly
New York, 21 Sep-2 Oct 2020
Daily Noon Briefing
According to the Office of the United Nations High Commissioner for Refugees (UNHCR), Jordan launched one of the world's first COVID-19 vaccination drives for refugees on 14 January. An Iraqi woman in the city of Irbid was the first registered refugee to be vaccinated as part of Jordan's national campaign.
Latest Noon Briefings
News & Media Resources
UNIFEED
Spokesperson for the Secretary-General
Latest Noon Briefing
A–Z Site Index


After weeks of unsubstantiated leaks, odd discoveries, and a whole lot of speculation, Infinity Ward finally unleashed an official reveal trailer for their upcoming game, Call of Duty: Infinite Warfare. Prior to its release there was an elaborate teaser involving a spaceship flying into Nuk3town on Black Ops 3, an audio clip played on the same map, images on Instagram / Snapchat, and even a scripted chat-bot on Facebook messenger.
It was quite the spectacle, but today topped it all with the unveiling of the official reveal trailer. As is tradition, the developers held back any details about multiplayer, but gave us a short, intriguing look into the game's campaign mode.
The trailer featured lots of action, explosions, and some brief dialogue that hinted at the game's storyline focus – a group known as the Settlement Defense Front (SDF) has staged a full-on attack on the world and we are in an all-out war with them.
This short video also officially confirmed that a remastered version of the original Call of Duty: Modern Warfare (CoD 4) will be bundled with the Legacy edition of Infinite Warfare. This edition of the game is priced at $79.99 and includes the base Infinite Warfare game and MW remastered.
The remastered CoD 4 features the full, original campaign as well as 10 multiplayer maps. Details about which maps actually made the cut have not been revealed just yet.
Call of Duty: Infinite Warfare will be released on November 4th, 2016 for Playstation 4, Xbox One, and PC. DLC for the game will be available first on the PS4, then on the Xbone and PC 30 days later.


This gorgeous Tutu Skirt features 3 tiers of soft tulle, satin ties with an adjustable waistband and cotton lining. Our Tutu Skirts are perfect for twirling in, whether it be at ballet, a party or everyday wear. These skirts would go perfectly with our Tulle Collar Leotards and / or our Rose Gold Bolero to make an adorable Christening or Flower Girl outfit.
WASH GUIDE: Cool hand wash or gentle machine wash inside out. Do not mix colours, bleach, wring or tumble dry. Light spin and line dry in the shade. Cool iron on lining.


An art studio and private office for a family home in Westport Connecticut, steps away from Compo beach, on the Long Island Sound. V.F. Schweitzer won the Open Auditions contest by Architectural Digest in 2008, and the American Architecture prize in 2017. It has since been published online globally in over 12 countries.
The large skylight eliminates the need for daylighting while providing privacy from the outside world, a workspace and a retreat.
The studio intentionally shuts out distractions with its fortress-like walls, and carefully placed windows for cross-ventilation in summer.
The main house, shingle-style modern, is in dialog with the smaller outbuilding, both with steep gables.
Light diffues the space making it airy and ideal for a workshop/studio.
Studio is enconced in nature.
View of changing skies and evening summer light.
The slabs of wood and stucco have a stonehenge primititivity, while the complex forms speak to a futuristic sensibility.
Organic design whereby the central glass expanse resembles a lake, surrounded by mountains in the form of wood and stucco.


text:
\section{Introduction}
Arthur-Merlin games and the class \kJmbkUXz{} was defined by
Babai \cite{Babai1985} as natural extension of the class \OktNAkJL{}
using randomization.
In the definition of \kJmbkUXz{} the prover (Merlin) gives a polynomial
length `proof' to the verifier (Arthur), who then performs a
polynomial-time randomized computation and has to decide
if an input $x$ is in a language or not.
The verifier is allowed to make some error in the decision,
hence making the class \kJmbkUXz{} possibly more powerful than \OktNAkJL.
If we add communication to the model, \WpedDmmP{} the prover and
the verifier can exchange a polynomial number of messages then
we get the class \FmrmOQaW{} \cite{Goldwasser1989}.\footnote{Babai also defined
an interactive version of \kJmbkUXz, that can be thought of as a
`public-coin' version of \FmrmOQaW.
Later Goldwasser and Sipser \cite{Goldwasser1986} showed
that this class has the same expressive power as \FmrmOQaW.}
The classes \FmrmOQaW{} and \kJmbkUXz{} has been extensively studied and
it is known that in both cases we can make the protocol to have
one-sided, exponentially small error without hurting the
power of the proof system.
\qpcpnInM{} the verifier only makes an error if the input is not
in the language, and even in this case the error
probability is at most an inverse-exponential
function of the input length.
Surprisingly, it turned out that \FmrmOQaW{} is equal to the class
of problems decidable in polynomial space (\LHqjxWJM)
\cite{Lund1992,Shamir1992}.
For more information on these classes see \eRAJAvVL{} the book
of Arora and Barak \cite{Arora2009}.
\par
Quantum Merlin-Arthur proof systems (and the class \SHvwttaw)
were introduced by Knill \cite{Knill1996}, Kitaev
\cite{Kitaev2002}, and also by Watrous \cite{Watrous2000}
as a natural extension
of \kJmbkUXz{} and \OktNAkJL{} to the quantum computational setting.
Similarly, \XaOdbtsT{}s (and the class \JWevirQe) were introduced by
Watrous \cite{Watrous2003} as a quantum
analogue of \FmrmOQaW.
These classes have also been well studied and now it's known
that the power of \XaOdbtsT{}s is the same as the classical ones,
\WpedDmmP{} $ \JWevirQe = \FmrmOQaW = \LHqjxWJM $ \cite{Jain2010}.
Furthermore, \XaOdbtsT{}s still have the same expressive power
if we restrict the number of messages to three and
have exponentially small one-sided error \cite{Kitaev2000}.
The class \SHvwttaw{} can also be made to have exponentially small error,
and has natural complete problems \cite{Aharonov2002}.
Interestingly it's not known if we can make \SHvwttaw{} to have
one-sided error.\footnote{In a recent paper, Jordan
\QgZuCZdC\ \cite{Jordan2011} showed that the proof system can achieve
perfect completeness if the prover's message is classical.}
\par
Several variants of \JWevirQe{} and \SHvwttaw{} have also been studied.
For example one can consider the case where some or
all of the messages are
short, meaning at most logarithmic in the input length
\cite{Marriott2005,Beigi2011,Pereszlenyi2011}.
Our focus will be more on the setting that was introduced by
Ito, Kobayashi and Watrous \cite{Ito2010}.
They studied quantum classes where the gap between the
completeness and soundness parameter is very small.
Their main result is that quantum interactive proofs with
double-exponentially small gap is characterized by
\QZccOLoE{} (deterministic exponential time).
\par
Probably the most interesting generalization of \SHvwttaw{}
is by Kobayashi, Matsumoto and Yamakami \cite{Kobayashi2003}
who defined the class \lrcGeBqo{k}.
In this setting there are $k$ provers who send $k$ quantum proofs
to the verifier, and these proofs are guaranteed to be unentangled.
Note that in the classical setting this generalization is not
interesting since we can just concatenate the $k$ proofs and
treat them as one proof.
However, in the quantum case a single prover can entangle
the $k$ proofs and no method is known to detect such
a cheating behavior.
\par
Obviously the most important question is whether more
provers make the class more powerful or not.
In a later version of their paper, Kobayashi \QgZuCZdC\ \cite{Kobayashi2003}
(and independently Aaronson \QgZuCZdC\ \cite{Aaronson2009})
showed that $ \lrcGeBqo{2} = \lrcGeBqo{k} $ for all
polynomially-bounded $k$ \iZJgfzde{} \lrcGeBqo{2} can be amplified
to exponentially small error.
Later Harrow and Montanaro \cite{Harrow2010} showed that the above equality
indeed holds.
The question now is whether \SHvwttaw{} is equal to \lrcGeBqo{2},
or in other words, does unentanglement actually help?
There are signs that show that the above two classes are
probably not equal.
For example, Liu, Christandl, and Verstraete \cite{Liu2007} found a problem
that has a \lrcGeBqo{2} proof system, but not known to belong
to \SHvwttaw.
Blier and Tapp \cite{Blier2009} showed that all problems in
\OktNAkJL{} have a \lrcGeBqo{2} proof system where the length of
both proofs are logarithmic in the input length.
On the other hand, if \SHvwttaw{} has one logarithmic-length proof
then it has the same expressive power as \VGZgApSi{} \cite{Marriott2005}.
Since \VGZgApSi{} is not believed to contain \OktNAkJL{},
\lrcGeBqo{2} with logarithmic length proofs is probably
more powerful than \SHvwttaw{} with a logarithmic proof.
The above proof system had some inverse-polynomial
gap, and this gap was later improved by several papers
\cite{Beigi2010,Chiesa2011,Gall2011}.
However, in all of these improvements the gap is still an
inverse-polynomial function of the input
length.\footnote{It is not believed that
the gap in this setting can be improved to a constant
because it would imply that $ \lrcGeBqo{2} = \vxJDyEiW $. \cite{Aaronson2009}}
Another evidence is by Aaronson \QgZuCZdC\ \cite{Aaronson2009}
who found a \lrcGeBqo{\CNzHFRry{\sqrt{n}}} proof
system for \hpRexCjN{} with constant gap
and where each proof consist of \FIqGvTZG{n} qubits.
Again, it seems unlikely that \hpRexCjN{}
has a proof system with one \CNzHFRry{\sqrt{n}}-length proof.
\subsection{Our Contribution}
We study multiple-proof \SHvwttaw{} proof systems in the setting
where the completeness-soundness gap is exponentially
small or even smaller.
We examine three variants of these proof systems
as described below.
\subsubsection{\texorpdfstring{\lrcGeBqo{k} with Small Gap}
{QMA[k] with Small Gap}}
The first variant we look at is the small-gap version of \lrcGeBqo{k}
mentioned above.
We show that this class is exactly characterized
by \vxJDyEiW{} if the number of proofs are between $2$ and
\wrDoIJTw{n}, and the completeness-soundness gap is between
exponentially or double-exponentially small.
The power of the proof system is still \vxJDyEiW{} if
we require it to have one-sided error.
More precisely we show the following theorem.
\begin{thm}
$ \displaystyle \vxJDyEiW =
\KOzxJkVZ{\ipeoICuS}{2}{1}{1 - \uaivIgOh{4^{-n}}} =
\bigcup_{\substack{0 < s < c \leq 1, \\ c-s \geq 2^{ -2^{\ipeoICuS} }}}
\KOzxJkVZ{\ipeoICuS}{\ipeoICuS}{c}{s} $,
where \HxLQfJAj{c}{n} and \HxLQfJAj{s}{n} can be calculated in time
at most exponential in $n$ on a classical computer.
\label{NmPOZGKI}
\end{thm}
In the notation above the first parameter of \SHvwttaw{} is
the upper-bound on the length of each proofs the verifier
receives, in qubits. The second parameter denotes
the number of unentangled proofs, while the third
is the completeness and the fourth is the soundness parameter.
For a precise definition of the above notation
see \HVRLKXNY{EriaXXKj}.
Note that in \MJqbMYrm{NmPOZGKI} the \vxJDyEiW{} upper-bound
is trivial, as it follows from exactly the same argument that
shows the \vxJDyEiW{} upper-bound to the `normal-gap' \lrcGeBqo{2}.
Interestingly, there is no other upper-bound known for \lrcGeBqo{2},
and it is a big open question to strengthen this bound
\cite{Aaronson2009}.
The surprising phenomenon is that if we relax the bound
on the gap, then the expressive power of the class jumps
all the way up to the trivial upper-bound.
Note that an \QZccOLoE{} upper-bound for the small-gap, single-prover
\SHvwttaw{} is easily seen, so we have a separation between
\SHvwttaw{} and \lrcGeBqo{k} in the small-gap setting.
For more discussion about this and other consequences see
\HVRLKXNY{HujYVLzw}.
\par
The non-trivial part of the proof is proving the \vxJDyEiW{}
lower-bound.
For this we use the protocol of Blier and Tapp \cite{Blier2009}
on a \vxJDyEiW-complete language which we call \HNGSAaAW,
the succinct version of graph 3-coloring.
The proof of \MJqbMYrm{NmPOZGKI} is
presented in \HVRLKXNY{jvxzezwT}.
\subsubsection{\texorpdfstring{\pUeVeClC{k} with Small Gap}
{BellQMA[k] with Small Gap}}
The class \pUeVeClC{k} was defined by
Aaronson \QgZuCZdC\ \cite{Aaronson2009},
Brand\~{a}o \cite{Brandao2008}, and
Chen and Drucker \cite{Chen2010}.
The above definitions are not exactly the same,
but the subtle difference doesn't matter in either
of the above papers, neither it does in this paper.
The exact definition of the class can be found
in \HVRLKXNY{EriaXXKj}.
Roughly, the difference between \lrcGeBqo{k} and
\pUeVeClC{k} is that in the latter the verifier
has to measure each proof separately and non-adaptively,
then based on the outcomes has to make its decision.
Aaronson \QgZuCZdC\ \cite{Aaronson2009} asked the question whether
\pUeVeClC{k} has the same power as \lrcGeBqo{k} and
if there is a \cdToKcBp{} protocol for \hpRexCjN{}
with similar parameters as theirs.
A partial positive answer to the first question was
given by Brand\~{a}o \cite{Brandao2008}, who showed that
$ \pUeVeClC{\QUPOtzml{1}} = \SHvwttaw $, and
a positive answer to the second question
was given by Chen and Drucker \cite{Chen2010}.
The power of \pUeVeClC{k} with super-constant $k$
remains an open problem.
\par
In this paper we study the small-gap version of
\pUeVeClC{k}, where again small means
exponentially or double-exponentially small.
One can observe that
Brand\~{a}o's proof of $ \pUeVeClC{\QUPOtzml{1}} = \SHvwttaw $
doesn't go through if the gap is so small.\footnote{Aaronson
\QgZuCZdC\ \cite{Aaronson2009} also defined
the class \ANJFILuJ{} similarly to
\cdToKcBp{} but allowing the verifier to make adaptive
and even several measurements on the same proofs.
Brand\~{a}o, Christandl, and Yard \cite{Brandao2011}
showed that $ \GOljMfAR{\QUPOtzml{1}} = \SHvwttaw $.
This proof also breaks down if the gap is small.}
So we don't know the power of \pUeVeClC{k} with
constant $k$ in the small-gap setting.
However, we show that if $k = \uaivIgOh{n}$
then \pUeVeClC{k} has the same power as
\lrcGeBqo{k}, \WpedDmmP{} it also equals to \vxJDyEiW.
This is expressed by the following theorem.
\begin{thm}
$ \displaystyle \vxJDyEiW =
\fiWpgtYc{\ipeoICuS}{\uaivIgOh{n}}{c}{s} =
\bigcup_{\substack{0 < s' < c' \leq 1, \\ c'-s' \geq 2^{ -2^{\ipeoICuS} }}}
\fiWpgtYc{\ipeoICuS}{\ipeoICuS}{c'}{s'} $,
for some $c$ and $s$ with
$ \HxLQfJAj{c}{n} - \HxLQfJAj{s}{n} = \uaivIgOh{4^{-n}} $, and where
\HxLQfJAj{c'}{n} and \HxLQfJAj{s'}{n} can be calculated in time
at most exponential in $n$ on a classical computer.
\label{nKVfzRHR}
\end{thm}
In the above the \vxJDyEiW{} upper-bound is again trivial,
so the only thing we need to do is give a \cdToKcBp{}
protocol for \vxJDyEiW.
Just as in the proof of the previous theorem,
we will use the same language (\HNGSAaAW) and
give a proof system for that.
For this we will use the protocol of
Chen and Drucker \cite{Chen2010}.
Note that similarly to their original
protocol we don't have
perfect completeness either.
\par
Knowing that having sufficiently many
provers makes \pUeVeClC{k} as powerful as
\lrcGeBqo{k}, it would be very interesting
to know the power of \pUeVeClC{k} with
small gap and constant $k$.
It's either more powerful then
$\pUeVeClC{1} = \SHvwttaw $, or somewhere between
constant and linear number of provers there is
an increase in the expressive power.
A more detailed discussion about this can be found
in \HVRLKXNY{fCJGhyBh}, and the proof of
\MJqbMYrm{nKVfzRHR} is presented in
\HVRLKXNY{BXwCHKEG}.
\subsubsection{\texorpdfstring{\lrcGeBqo{k} with Small Gap and Short Proofs}
{QMA[k] with Small Gap and Short Proofs}}
We also study the small-gap version of \lrcGeBqo{k}
where each proof is short \WpedDmmP{} at most
\FIqGvTZG{n}-many qubits.
One would expect that in this case the
class gets weaker then \vxJDyEiW.
We could only show this in the case when
the gap is inverse-exponential, which follows
from a few simple observations.
For the case when the gap is smaller than this
we give a lemma that simplifies the proof system,
which may help to prove non-trivial upper-bounds
for these classes later.
The lemma roughly says that instead of
\FIqGvTZG{n}-many qubits, we can consider the
case when all the proof are just $1$ qubits.
The above mentioned results are described in
more detail in \HVRLKXNY{sec:QMAlog}.
\subsection*{Organization of the Paper}
The remainder of the paper is organized as follows.
\HVRLKXNY{EriaXXKj} discusses the background
theorems and definitions needed for the rest of the paper.
\HVRLKXNY{jvxzezwT} presents the proof of
our first main theorem, \MJqbMYrm{NmPOZGKI},
with the last part of the proof presented
in \IhApwfvN{WEFVXHAK}.
In \HVRLKXNY{BXwCHKEG} we explain
the proof of our other main theorem,
\MJqbMYrm{nKVfzRHR}.
We end the paper with some conclusions and open
problems in \HVRLKXNY{HujYVLzw}, with
one last proof presented in
\IhApwfvN{zKhwWgDg}.
\section{Preliminaries}
\label{EriaXXKj}
We assume familiarity with quantum information and
computation \cite{Nielsen2000}; such as
quantum states, unitary operators, measurements, etc.
We also assume the reader is familiar with
computational complexity, both classical \cite{Arora2009}
and quantum \cite{Watrous2008a}.
Throughout the paper we will talk about complexity
classes like \sVwdElyU, \LHqjxWJM, \QZccOLoE, \vxJDyEiW,
\VGZgApSi, \AIJjtsxK, \SHvwttaw, and \JWevirQe.
In this section we only define the classes that
are the most relevant to our discussions,
where the definition of the rest can be found
in the above mentioned references.
The purpose of this section is to present some of the notations
and background information (definitions,
theorems) required to understand the rest of the paper.
\par
We denote the set of functions of $n$ that are
upper-bounded by some polynomial in $n$ by \wrDoIJTw{n}.
If the argument is clear, we omit it and just
write \ipeoICuS.
We denote the imaginary unit by \WHYFCIFc{} instead of
$i$, which we use as an index in summations for example.
\begin{defi}
In the paper we use some well-known quantum gates.
We define them here.
\begin{align*}
\gctqElrH &\faJHPjTb \GyFczGjW{00} + \GyFczGjW{01} +
\ZFdmJtwX{11}{10} + \ZFdmJtwX{10}{11} \\
\lDGygnkY &\faJHPjTb \frac{1}{\sqrt{2}}
\DnoYoBfx{\GyFczGjW{0} + \ZFdmJtwX{0}{1} + \ZFdmJtwX{1}{0} - \GyFczGjW{1} } \\
\sYcexCeY{x}{\omega} &\faJHPjTb \cos \frac{\omega}{2} \GyFczGjW{0}
-\WHYFCIFc \sin \frac{\omega}{2} \ZFdmJtwX{0}{1}
-\WHYFCIFc \sin \frac{\omega}{2} \ZFdmJtwX{1}{0}
+ \cos \frac{\omega}{2} \GyFczGjW{1} \\
\sYcexCeY{z}{\omega} &\faJHPjTb \GyFczGjW{0} + e^{\WHYFCIFc \omega} \GyFczGjW{1}
\end{align*}
\end{defi}
Whenever we talk about quantum polynomial-time algorithms
or quantum verifiers, we always mean polynomial-time uniformly
generated quantum circuits consisting of some
universal set of gates.
For example, the gates \gctqElrH, \lDGygnkY, and \sYcexCeY{z}{\frac{\pi}{4}}
form a universal set, and there are many other sets
that are universal.
Usually it doesn't matter which set we choose when we
define quantum verifiers and classes like \SHvwttaw{} and \JWevirQe,
because it is known that each universal set can approximate
any other set with exponential precision.
However, in the following we will use error parameters
that are smaller then this, hence the power of those
classes may change with respect to what set of gates
the verifier is using.
In this paper we only assume that the verifier
can perform or perfectly simulate the \gctqElrH{} and
the \lDGygnkY{} gate, besides being able to perform any
polynomial-time classical computation.
This assumption is enough for all our results, so
we won't bother about the gate set in the rest of the paper.
\begin{defi}[\cite{Kobayashi2003,Aaronson2009}]
\label{TJOqWPoY}
For functions \FyOFSCmf{\ell, k}{\CYLQkbAO}{\VrXQeMta},
\FyOFSCmf{c, s}{\CYLQkbAO}{ \left( 0, 1 \right] }
a language $L$ is in \KOzxJkVZ{\ell}{k}{c}{s} if there
exist a quantum verifier \wQoFYwHz{V} \ygMPbVVP{} for all
$ n \in \CYLQkbAO $ and inputs $ x \in \GGfSpoIn{0,1}^n $,
\HxLQfJAj{\wQoFYwHz{V}}{x} is a quantum circuit generated in
\wrDoIJTw{n}-time and the following holds.
\begin{description}
\item[Completeness:]
If $x \in L$ then there exist quantum proofs
\raIfJZxu{\phi_1}, \ldots, \raIfJZxu{\phi_{\HxLQfJAj{k}{n}}},
where for all $i$, \raIfJZxu{\phi_i} is made up of
at most \HxLQfJAj{\ell}{n} qubits, and the acceptance
probability of \HxLQfJAj{\wQoFYwHz{V}}{x} on input
$ \raIfJZxu{\phi_1} \NUxdODWZ \cdots \NUxdODWZ
\raIfJZxu{\phi_{\HxLQfJAj{k}{n}}} $ is $ \geq \HxLQfJAj{c}{n} $.
\item[Soundness:]
If $x \notin L$ then for all states
\raIfJZxu{\phi_1}, \ldots, \raIfJZxu{\phi_{\HxLQfJAj{k}{n}}},
where for all $i$, \raIfJZxu{\phi_i} is made up of
at most \HxLQfJAj{\ell}{n} qubits, \HxLQfJAj{\wQoFYwHz{V}}{x}
accepts with probability $ \leq s $,
given $ \raIfJZxu{\phi_1} \NUxdODWZ \cdots \NUxdODWZ
\raIfJZxu{\phi_{\HxLQfJAj{k}{n}}} $ as its input.
\end{description}
If the class is denoted by \KOzxJkVZ{\ell}{k}{c}{<s}, then
the probability bound in the soundness case is
$ < s $ instead of $ \leq s $.
\end{defi}
\begin{rem}
If we just give one parameter to \SHvwttaw, then
it indicates the number of provers.
So the notation \lrcGeBqo{k} is defined as
$ \lrcGeBqo{k} \faJHPjTb \KOzxJkVZ{\wrDoIJTw{n}} {k} {\frac{2}{3}} {\frac{1}{3}} $.
With our notation the class \SHvwttaw{} is defined as
$ \SHvwttaw \faJHPjTb \lrcGeBqo{1} $.
\end{rem}
\begin{defi}[\cite{Brandao2008,Aaronson2009}]
The class \fiWpgtYc{\ell}{k}{c}{s} is defined almost the same
way as \KOzxJkVZ{\ell}{k}{c}{s} in \MOVPSHbF{TJOqWPoY},
except that the verifier \wQoFYwHz{V} is not an
arbitrary \ipeoICuS-time quantum computation.
The restriction we put on the verifier is the following.
\wQoFYwHz{V} upon seeing $x$ performs a classical
randomized \ipeoICuS-time computation and produces
circuits for measurements $M_1$, \ldots, $M_{\HxLQfJAj{k}{n}}$,
where each $M_i$ is a POVM on at most \HxLQfJAj{\ell}{n} qubits.
Then for all $i$, the verifier measures
\raIfJZxu{\phi_i} with $M_i$, and obtains outcome $m_i$.
After all measurements were performed, \wQoFYwHz{V}
runs a classical computation on inputs
$m_1$, \ldots, $m_{\HxLQfJAj{k}{n}}$, and
decides whether to accept or reject.
\end{defi}
Note that in the above definition the verifier
has to measure each proofs separately.
Moreover, non of the circuits of the measurements can depend
on the outcome of any previous measurement.
Chen and Drucker \cite{Chen2010} defined \cdToKcBp{}
in a slightly different way by allowing the verifier
to do quantum computations before and after
the measurements.
Our result also holds if we take their definition.
The reason we chose the above definition is
because we will prove a lower-bound for our
\cdToKcBp{} class, and so with the more restricted
definition our result is slightly stronger.
\begin{defi}
The class \vtZmVJmM{c}{s} is defined analogously to
\SHvwttaw{} of \MOVPSHbF{TJOqWPoY} with the difference
that the proof must be a classical string.
We will always take this string to be polynomial-length.
Since the string is classical, it doesn't make sense
to have several proofs, so we drop the parameters of
proof lengths and number of proofs.
As in the previous definitions, $c$ is the completeness
and $s$ is the soundness parameter.
\end{defi}
\begin{defi}[\cite{Galperin1983}]
Let \HxLQfJAj{G}{V,E} be an undirected graph where
$V = \HelzWRDf{m}$ and $ m \leq 2^n $ for some $n$.
We define \oVrArWkh{} to be a \emph{small circuit representation}
of $G$ if the following hold:
\begin{itemize}
\item \oVrArWkh{} is a circuit containing AND, OR and NOT gates.
\item \oVrArWkh{} has two inputs of $n$ bits each.
\item \oVrArWkh{} has \wrDoIJTw{n} gates.
\item The output of \oVrArWkh{} is given by
\[
\HxLQfJAj{\oVrArWkh}{u,v} =
\begin{cases}
00 & \text{if } u \notin V \text{ or } v \notin V
\text{ or } u \geq v \text{,} \\
10 & \text{if } u < v \text{ and } \DnoYoBfx{u, v} \notin E \text{,} \\
11 & \text{if } u < v \text{ and } \DnoYoBfx{u, v} \in E \text{.}
\end{cases}
\]
\end{itemize}
\end{defi}
\begin{defi}
Let the decision problem \HNGSAaAW{} be the set of small circuit representations
of graphs that are 3-colorable.
\end{defi}
\begin{thm}[\cite{Papadimitriou1986}]
\HNGSAaAW{} is \vxJDyEiW{}-complete.
\end{thm}
In the following discussion we will use the
`SWAP-test' of \cite{Barenco1997,Buhrman2001},
and the following property of this test.
\begin{thm}[\cite{Buhrman2001}]
When the SWAP-test is applied to two states
\raIfJZxu{\varphi} and \raIfJZxu{\psi} (with the same dimension),
it accepts with probability
$ \frac{1}{2} \DnoYoBfx{1 + \AfBMaxZI{\NChmtXsR{\varphi}{\psi}}^2} $.
\label{QzwgCixS}
\end{thm}
Note that in order to perform the SWAP-test we need
two Hadamard (\lDGygnkY) gates, \gctqElrH{} gates with the
amount linear in the number of qubits
\raIfJZxu{\varphi} and \raIfJZxu{\psi} are stored on,
and we need to measure a qubit in the standard basis.
\begin{defi}
We define the state \raIfJZxu{u_m} as the uniform superposition
of the standard basis states, \WpedDmmP{}
\[ \raIfJZxu{u_m} \faJHPjTb \frac{1}{\sqrt{m}} \sum_{i=0}^{m-1} \raIfJZxu{i} . \]
We also define the projective measurement
that projects onto this state, or more formally
the measurement
$ \GGfSpoIn{ \nVzyhtCm{P}_0, \nVzyhtCm{P}_1 } $ where
\[ \nVzyhtCm{P}_0 \faJHPjTb \GyFczGjW{u_m} \text{,} \qquad
\nVzyhtCm{P}_1 \faJHPjTb \YMElKjII - \GyFczGjW{u_m} \text{.} \]
We say that $\nVzyhtCm{P}_0$ (and $\nVzyhtCm{P}_1$)
corresponds to outcome $0$ (and $1$).
\label{NlcnHZqK}
\end{defi}
Note that the above measurement can be performed
using \NpwuHusD{\log m} Hadamard gates and single-qubit
measurements.
\section{\texorpdfstring{\lrcGeBqo{k} with Small Gap Equals \vxJDyEiW}
{QMA[k] with Small Gap Equals NEXP}}
\label{jvxzezwT}
This section proves \MJqbMYrm{NmPOZGKI}, \WpedDmmP{}
we show that \lrcGeBqo{k} equals \vxJDyEiW{} if $k$ is at least
$2$ and at most \wrDoIJTw{n}, and the completeness-soundness
gap is bounded away by an inverse-exponential or doubly exponential
function of $n$.
\par
The proof of this theorem is divided into \dWQdKYxc{ULcFIvTl}
and \MJqbMYrm{QoOYZYVy},
according to the two directions of the containment.
As mentioned in the Introduction,
only \MJqbMYrm{QoOYZYVy} is actually new.
\begin{lem}
$ \displaystyle \bigcup_{\substack{0 < s < c \leq 1, \\
c-s \geq 2^{ -2^{\ipeoICuS} }}}
\KOzxJkVZ{\ipeoICuS}{\ipeoICuS}{c}{s}
\subseteq \vxJDyEiW $,
where \HxLQfJAj{c}{n} and \HxLQfJAj{s}{n} can be calculated in time
at most exponential in $n$ on a classical computer.
\label{ULcFIvTl}
\end{lem}
\begin{proof}[Proof sketch]
Let $ L \in \KOzxJkVZ{\ipeoICuS}{\ipeoICuS}{c}{s} $ with some
$c$ and $s$ satisfying the conditions in the lemma.
The proofs in the \SHvwttaw{} proof system are \ipeoICuS-many quantum states on
\ipeoICuS-many qubits, which are vectors in the complex euclidean
space with exponential dimension.
These vectors can be described up to an exponential number of
bits of accuracy by a classical proof of exponential length.
Given this proof to a \vxJDyEiW{} machine, it can calculate the
acceptance probability of the \SHvwttaw{} verifier to an exponential
number of bits of accuracy;
and it can decide whether this probability is more
then $c$ or less then $s$.
This means that $ L \in \vxJDyEiW $.
\end{proof}
The other direction of the containment is formulated
by the following theorem.
\begin{thm}
$ \displaystyle \vxJDyEiW \subseteq
\KOzxJkVZ{\ipeoICuS}{2}{1}{1 - \uaivIgOh{4^{-n}}} $.
\label{QoOYZYVy}
\end{thm}
We will prove this result through several lemmas.
This will prove \MJqbMYrm{NmPOZGKI}
as well.
\begin{proof}[Proof of \MJqbMYrm{NmPOZGKI}]
The theorem immediately follows from \dWQdKYxc{ULcFIvTl},
\MJqbMYrm{QoOYZYVy} and the observation that
$ \KOzxJkVZ{\ipeoICuS}{2}{1}{1 - \uaivIgOh{4^{-n}}} \subseteq
\bigcup_{\substack{0 < s < c \leq 1, \\
c-s \geq 2^{ -2^{\ipeoICuS} }}}
\KOzxJkVZ{\ipeoICuS}{\ipeoICuS}{c}{s} $.
\end{proof}
In order to prove \MJqbMYrm{QoOYZYVy} we
construct a \SHvwttaw{} verifier \wQoFYwHz{V} for
the \vxJDyEiW-complete language \HNGSAaAW.
We use the protocol of Blier and Tapp \cite{Blier2009},
with similar argument as theirs.
\par
Let the input to \HNGSAaAW{} be denoted by \oVrArWkh{} and it's
length by $ n = \AfBMaxZI{\oVrArWkh} $.
Let \wQoFYwHz{V} get its two unentangled proofs in registers
$ \VSdxZJNO{R}_1 $ and $ \VSdxZJNO{R}_2 $.
Both $ \VSdxZJNO{R}_i $'s have two parts,
$ \VSdxZJNO{R}_i = \VSdxZJNO{N}_i \VSdxZJNO{C}_i $,
where $\VSdxZJNO{N}_i$ is the `node' part and
$\VSdxZJNO{C}_i$ is the `color' part.
$\VSdxZJNO{N}_1$ and $\VSdxZJNO{N}_2$ have associated Hilbert space
$ \VWqEPttf^{2^n} $, while $\VSdxZJNO{C}_1$ and $\VSdxZJNO{C}_2$
have associated space $ \VWqEPttf^3 $.
The procedure \wQoFYwHz{V} performs is described in
\FxucuSoM{jEVcePOJ}.
\par
\begin{algorithm}[h t b]
\caption{Description of verifier \wQoFYwHz{V} in the proof of
\MJqbMYrm{QoOYZYVy}.}
\label{jEVcePOJ}
\begin{algorithmic}[1]
\ZNbYlnmP classical circuit \oVrArWkh, quantum registers
$\VSdxZJNO{R}_1$ and $\VSdxZJNO{R}_2$,
where the state of $\VSdxZJNO{R}_1$ and
$\VSdxZJNO{R}_2$ is separable
\tkOoHzex accept or reject
\STATE With probability $1/3$ do
the \textbf{Equality Test} (line~\ref{yeMuKErF}),
the \textbf{Consistency Test} (line~\ref{YKlinzMJ}), or
the \textbf{Uniformity Test} (line~\ref{DOkcHsyK}).
\STATE \textbf{Equality Test.} Perform the SWAP-test on
$ \VSdxZJNO{R}_1 $ and $ \VSdxZJNO{R}_2 $.
\label{yeMuKErF}
\IF{the SWAP-test fails}
\RETURN reject
\COMMENT{The two registers are not equal.}
\ELSE
\RETURN accept
\ENDIF
\STATE \textbf{Consistency Test.}
\label{YKlinzMJ}
Measure $ \VSdxZJNO{N}_1 $, $ \VSdxZJNO{C}_1 $,
$\VSdxZJNO{N}_2 $ and $ \VSdxZJNO{C}_2 $
in the computational basis and get
$v_1$, $c_1$, $v_2$ and $c_2$.
\IF{($ v_1 = v_2 $) \AND ($ c_1 \neq c_2 $)} \label{DkvnMEbW}
\RETURN reject
\COMMENT{The same vertex has two colors.}
\ELSIF{($ \HxLQfJAj{\wQoFYwHz{C}}{v_1, v_2} = 11 $)
\COMMENT{Assume that $ v_1 < v_2 $ otherwise swap them.}
\AND ($ c_1 = c_2 $)}
\RETURN reject
\COMMENT{Adjacent vertices have same color.}
\ELSE
\RETURN accept
\ENDIF
\STATE \textbf{Uniformity Test.}
Measure $ \VSdxZJNO{N}_1 $ and $ \VSdxZJNO{C}_1 $ separately
according to the measurement of
\MOVPSHbF{NlcnHZqK}.
\label{DOkcHsyK}
\IF{(the outcome on $ \VSdxZJNO{C}_1 $ is $0$)
\AND (the outcome on $ \VSdxZJNO{N}_1 $ is $1$)}
\label{GTSlDeLX}
\RETURN reject
\COMMENT{Not all nodes are present.}
\ELSE
\RETURN accept
\ENDIF
\end{algorithmic}
\end{algorithm}
Note that \wQoFYwHz{V} runs in \wrDoIJTw{n}-time,
because the SWAP-test, evaluating the circuit \oVrArWkh,
and performing the measurement of
\MOVPSHbF{NlcnHZqK} for
$ m=2^n $ all can be performed in polynomial time.
The following lemma,
which is essentially the same as Theorem~2.4 of \cite{Blier2009},
proves completeness for \wQoFYwHz{V}.
\begin{lem}[Completeness]
If $ \oVrArWkh \in \HNGSAaAW $ then there exist a pair of proofs,
with which \wQoFYwHz{V} will
accept with probability $1$.
\label{ueMCbSRk}
\end{lem}
\begin{proof}
For $ i \in \HelzWRDf{m} $ let $ \HxLQfJAj{c}{i} \in \GGfSpoIn{0,1,2} $
be a valid coloring of the graph $G$,
where $m$ is the number of nodes.
For $ i \in \GGfSpoIn{m, \ldots, 2^n-1} $ let $ \HxLQfJAj{c}{i} = 0 $.
Let the state of both $ \VSdxZJNO{R}_1 $ and $ \VSdxZJNO{R}_2 $ be
\begin{align}
\raIfJZxu{\phi} = \frac{1}{\sqrt{2^n}}
\sum_{i=0}^{2^n - 1} \raIfJZxu{i} \raIfJZxu{\HxLQfJAj{c}{i}} \text{,}
\label{BGuJsFqG}
\end{align}
where \raIfJZxu{i} is on the node register (\VSdxZJNO{N})
and \raIfJZxu{\HxLQfJAj{c}{i}} is on the color register (\VSdxZJNO{C}).
From \MJqbMYrm{QzwgCixS}
it follows that the Equality Test succeeds with probability $1$.
Since $ c $ is a valid 3-coloring, the Consistency Test
succeeds with probability $1$ as well.
To see the same for the Uniformity Test,
let us calculate the resulting state
after measuring $0$ on $ \VSdxZJNO{C}_1 $ in
line~\ref{GTSlDeLX} of
\FxucuSoM{jEVcePOJ}.
Up to some normalization factor, the state is
\[ \DnoYoBfx{\YMElKjII \NUxdODWZ \GyFczGjW{u_3}} \raIfJZxu{\phi} =
\frac{1}{3 \sqrt{2^n}} \DnoYoBfx{\sum_{i=0}^{2^n - 1} \raIfJZxu{i}}
\NUxdODWZ \DnoYoBfx{\sum_{k=0}^{2} \raIfJZxu{k}} . \]
This means that the state of $ \VSdxZJNO{N}_1 $
is \raIfJZxu{u_{2^n}}, so the Uniformity Test always succeeds.
\end{proof}
The proof of soundness is presented in \IhApwfvN{WEFVXHAK}
on page~\pageref{WEFVXHAK}, because it
closely follows the analysis of Blier and Tapp \cite{Blier2009}
and of Chiesa and Forbes \cite{Chiesa2011},
although with different parameters.
\section{\texorpdfstring{\pUeVeClC{\uaivIgOh{n}} with Small Gap Equals \vxJDyEiW}
{BellQMA[Omega(n)] with Small Gap Equals NEXP}}
\label{BXwCHKEG}
In this section we prove \MJqbMYrm{nKVfzRHR},
\WpedDmmP{} we show that \SHvwttaw{} with exponentially
small gap still equals to \vxJDyEiW{} if we restrict
the verifier to only be able to perform Bell-measurements.
However, we will need at least \uaivIgOh{n} proofs.
We essentially use the algorithm of Chen
and Drucker \cite{Chen2010} on the succinct version of graph
3-coloring (\HNGSAaAW).
We also use one of their lemmas, but
our proof will be simpler then theirs,
because we don't aim for constant gap.
We don't use the PCP theorem either.
Note that in the previous section we already
argued about the \vxJDyEiW{} upper-bound on the
\SHvwttaw{} classes.
The same argument applies here too.
It's also easy to see that restricting the verifier
can only make the power of the proof system weaker.
So the only statement left to prove, in order to prove
\MJqbMYrm{nKVfzRHR}, is the following.
\begin{thm}
$ \vxJDyEiW \subseteq \fiWpgtYc{\wrDoIJTw{n}}{\uaivIgOh{n}}{c}{s} $,
for some $c$ and $s$
with $ \HxLQfJAj{c}{n} - \HxLQfJAj{s}{n} = \uaivIgOh{4^{-n}} $.
\label{okAAwxmt}
\end{thm}
To prove \MJqbMYrm{okAAwxmt},
we construct a \cdToKcBp{} verifier \wQoFYwHz{V} for
\HNGSAaAW{} which will show that
$ \HNGSAaAW{} \in \fiWpgtYc{\wrDoIJTw{n}}{\uaivIgOh{n}}{c}{s} $.
Since \HNGSAaAW{} is \vxJDyEiW-complete,
\MJqbMYrm{okAAwxmt} will follow.
Just as in the previous section,
let the input to \HNGSAaAW{} be denoted by \oVrArWkh{} and it's
length by $ n = \AfBMaxZI{\oVrArWkh} $.
Verifier \wQoFYwHz{V} will receive $k$ quantum proofs
in registers
$\VSdxZJNO{N}_1, \VSdxZJNO{C}_1, \ldots, \VSdxZJNO{N}_k, \VSdxZJNO{C}_k$,
where for each $ i \in \iteYiYHH{k} $,
the state of $\VSdxZJNO{N}_i \VSdxZJNO{C}_i$ is
separable from the rest of the registers.
The registers $\VSdxZJNO{N}_i$ have associated space
$ \VWqEPttf^{2^n} $ and registers $\VSdxZJNO{C}_i$
have associated space $ \VWqEPttf^3 $, similarly as in
the previous section.
The behavior of \wQoFYwHz{V} is described
in \FxucuSoM{NuAJSVLc}.
\begin{algorithm}[h t b]
\caption{Description of verifier \wQoFYwHz{V} in the proof of
\MJqbMYrm{okAAwxmt}.}
\label{NuAJSVLc}
\begin{algorithmic}[1]
\ZNbYlnmP classical circuit \oVrArWkh, quantum registers
$\VSdxZJNO{N}_1, \VSdxZJNO{C}_1, \ldots,
\VSdxZJNO{N}_k, \VSdxZJNO{C}_k$,
where $ \forall i \in \iteYiYHH{k} $,
the state of $\VSdxZJNO{N}_i \VSdxZJNO{C}_i$ is
separable from the rest of the registers
\tkOoHzex accept or reject
\STATE With probability $ \frac{1}{2} $ do the
\textbf{Consistency Test} (line~\ref{NgopDguv})
or the \textbf{Uniformity Test}
(line~\ref{qMwgVWBk}).
\label{GJhSCbBL}
\STATE \textbf{Consistency Test.}
\label{NgopDguv}
\FORALL{$ i \in \iteYiYHH{k} $}
\STATE Measure $\VSdxZJNO{N}_i$ and $\VSdxZJNO{C}_i$
in the computational basis and get $v_i$ and $c_i$.
\label{qAGbukNT}
\ENDFOR
\FORALL{$ 1 \leq i < j \leq k $}
\IF{($ v_i = v_j $) \AND ($ c_i \neq c_j $)}
\RETURN reject
\COMMENT{The same vertex has two colors.}
\label{FMIMsMqc}
\ELSIF{($ \HxLQfJAj{\wQoFYwHz{\oVrArWkh}}{v_i, v_j} = 11 $)
\AND ($ c_i = c_j $)}
\RETURN reject
\COMMENT{Adjacent vertices have same color.}
\label{eIpHlpwC}
\ENDIF
\ENDFOR
\RETURN accept
\STATE \textbf{Uniformity Test.}
\label{qMwgVWBk}
\FORALL{$ i \in \iteYiYHH{k} $}
\STATE Measure $ \VSdxZJNO{C}_i $ with the measurement
of \MOVPSHbF{NlcnHZqK}
and denote the outcome by $x_i$.
\label{ZtoStVJz}
\STATE Measure $ \VSdxZJNO{N}_i $ with the measurement
of \MOVPSHbF{NlcnHZqK}
and denote the outcome by $y_i$.
\label{fEiSBHoN}
\ENDFOR
\STATE Let $ Z \faJHPjTb \lUlEWeUc{i}{x_i = 0} $.
\IF{$ \AfBMaxZI{Z} < k/6 $}
\RETURN reject
\label{czNyFhpM}
\ENDIF
\FORALL{$ i \in Z $}
\IF{$ y_i = 1 $}
\RETURN reject
\COMMENT{Not all nodes are present.}
\ENDIF
\ENDFOR
\RETURN accept
\end{algorithmic}
\end{algorithm}
We split the proof of \MJqbMYrm{okAAwxmt}
into \dWQdKYxc{iQoQORKN},
which proves completeness for \wQoFYwHz{V} and
\dWQdKYxc{gFZRHSOy}, which proves its soundness.
\begin{lem}[Completeness]
If $ \oVrArWkh \in \HNGSAaAW $ then there exist quantum states
on registers $\VSdxZJNO{N}_1, \VSdxZJNO{C}_1, \ldots,
\VSdxZJNO{N}_k, \VSdxZJNO{C}_k$, such that if they are input to
\wQoFYwHz{V}, defined by \FxucuSoM{NuAJSVLc},
then \wQoFYwHz{V} will accept with probability at least
$ 1 - 2^{- \frac{k}{40}} $.
\label{iQoQORKN}
\end{lem}
\begin{proof}
For all $ i \in \iteYiYHH{k} $, let the state of
$\VSdxZJNO{N}_i \VSdxZJNO{C}_i$ be \raIfJZxu{\phi},
where \raIfJZxu{\phi} is defined by equation~\eqref{BGuJsFqG}
on page~\pageref{BGuJsFqG}.
For exactly the same reason as in the proof of
\dWQdKYxc{ueMCbSRk} the Consistency Test will
succeed with probability $1$.
As for the Uniformity Test, note that for all
$i \in Z$, the measurement of $\VSdxZJNO{N}_i$
in line~\ref{fEiSBHoN}
of \FxucuSoM{NuAJSVLc} yields $1$ with
probability $1$.
The argument for this is also in the proof of
\dWQdKYxc{ueMCbSRk}.
\par
This means that given the above input, the only place where
\FxucuSoM{NuAJSVLc} may reject is at
line~\ref{czNyFhpM}, \WpedDmmP{}
when $ \AfBMaxZI{Z} < \frac{k}{6} $.
So in the following we only need to upper-bound
this probability.
We do it similarly to the proof of Lemma~1 of \cite{Chen2010}.
By direct calculation the probability that
$x_i = 0$ in line~\ref{ZtoStVJz} is
\[ \TdSeQgKh{x_i = 0} =
\fHAwcqZo{\phi} \DnoYoBfx{\YMElKjII \NUxdODWZ \GyFczGjW{u_3}} \raIfJZxu{\phi} =
\frac{1}{3} . \]
This means that $ \YcVNkVQD{\AfBMaxZI{Z}} = \frac{k}{3} $.
Since the $x_i$'s are independent, we can use the
\fKqDCezI{} and get that
\[ \TdSeQgKh{\AfBMaxZI{Z} < \frac{k}{6}} <
e^{- \frac{k}{48}} <
2^{- \frac{k}{40}} . \]
This finishes the proof of the lemma.
\end{proof}
\newcommand{\vXoALQtP}[1]{\ensuremath{ \alpha_{v}^{\DnoYoBfx{#1}} }}
\newcommand{\yJgNrafg}[1]{\ensuremath{ \beta_{v,j}^{\DnoYoBfx{#1}} }}
\newcommand{\ensuremath{ \gamma_{v}^{\DnoYoBfx{i}} }}{\ensuremath{ \gamma_{v}^{\DnoYoBfx{i}} }}
We are left to prove soundness for \wQoFYwHz{V}.
From now on let's denote the quantum input to
\FxucuSoM{NuAJSVLc} by \raIfJZxu{\varphi_1}, \ldots,
\raIfJZxu{\varphi_k}.
For each $ i \in \iteYiYHH{k} $, we write
\[ \raIfJZxu{\varphi_i} = \sum_{v=0}^{2^n-1} \vXoALQtP{i} \raIfJZxu{v}
\sum_{j=0}^2 \yJgNrafg{i} \raIfJZxu{j} \text{,} \]
where \raIfJZxu{v} is a state on $\VSdxZJNO{N}_i$,
\raIfJZxu{j} is a state on $\VSdxZJNO{C}_i$, furthermore
$ \sum_{v=0}^{2^n-1} \AfBMaxZI{\vXoALQtP{i}}^2 = 1 $ for each $i$, and
$ \sum_{j=0}^2 \AfBMaxZI{\yJgNrafg{i}}^2 = 1 $ for each $i$ and $v$.
Similarly to the notation in \cite{Chen2010} let
\[ Z' \faJHPjTb \lUlEWeUc{i}{ \TdSeQgKh{x_i = 0} \geq \frac{1}{12} } . \]
\par
We need a lemma from \cite{Chen2010} which we will
state and use with a bit different parameters.
Intuitively the lemma says that in order to avoid rejection
in line~\ref{czNyFhpM}, we must
have a constant fraction of registers for which,
with at least a constant probability, the outcome
of the measurement in
line~\ref{ZtoStVJz} is $0$.
\begin{lem}[Lemma~2 of \cite{Chen2010}]
If $ \AfBMaxZI{Z'} \leq k/6 $ and if in
line~\ref{GJhSCbBL} of
\FxucuSoM{NuAJSVLc} the Uniformity
Test is chosen, then the test will reject in
line~\ref{czNyFhpM} with
probability \uaivIgOh{1}.
\label{vzMhnkxb}
\end{lem}
We want all nodes to appear with sufficiently
big amplitude in \raIfJZxu{\varphi_i}, for each $i \in Z'$.
This is formalized by the following lemma.
\begin{lem}
Suppose that the Uniformity Test rejects with probability
at most $ 200^{-1} \cdot 4^{-n} $.
Then $ \forall i \in Z' $ and $ \forall v \in \HelzWRDf{2^n} $
it holds that
\[ \AfBMaxZI{\vXoALQtP{i}}^2 > \frac{1}{24 \cdot 2^n} . \]
\label{UDjzaeqm}
\end{lem}
\begin{proof}
Let's pick an $i \in Z'$, and consider the state
\raIfJZxu{\varphi_i} on register $\VSdxZJNO{N}_i \VSdxZJNO{C}_i$.
Suppose that we measured $0$ on $\VSdxZJNO{C}_i$ with
the measurement of \MOVPSHbF{NlcnHZqK},
and denote the resulting state on $\VSdxZJNO{N}_i$ by
\[ \raIfJZxu{\xi_i} = \sum_{v=0}^{2^n-1} \ensuremath{ \gamma_{v}^{\DnoYoBfx{i}} } \raIfJZxu{v} . \]
Note that since $i \in Z'$, this outcome happens with
probability $ \geq \frac{1}{12} $.
Assume towards contradiction that $ \exists v $ \ygMPbVVP{}
$ \AfBMaxZI{\ensuremath{ \gamma_{v}^{\DnoYoBfx{i}} }}^2 < \frac{1}{2 \cdot 2^n} $.
Using \dWQdKYxc{tAaagiyx}
from page~\pageref{tAaagiyx},
we get that when we measure \raIfJZxu{\xi_i} with the measurement
of \MOVPSHbF{NlcnHZqK},
we get outcome $1$ with probability at least
$ \frac{1}{16 \cdot 4^{n}} $.
But this means that the Uniformity Test rejects with
probability at least
$ \frac{1}{12 \cdot 16 \cdot 4^{n}} >
\frac{1}{200 \cdot 4^{n}} $.
This contradicts to the statement of the lemma,
so it must be that
$ \AfBMaxZI{\ensuremath{ \gamma_{v}^{\DnoYoBfx{i}} }}^2 \geq \frac{1}{2 \cdot 2^n} $
for all $v$.
\dWQdKYxc{KHySvfFa} implies that
for all $v$,
\[ \AfBMaxZI{\vXoALQtP{i}}^2 \geq
\frac{1}{12 \cdot 2 \cdot 2^n} . \qedhere \]
\end{proof}
We are now ready to prove soundness for \wQoFYwHz{V}.
\begin{lem}[Soundness]
If $ \oVrArWkh \notin \HNGSAaAW $ then \wQoFYwHz{V} of
\FxucuSoM{NuAJSVLc} will reject with
probability at least $ 12000^{-1} \cdot 4^{-n} $.
\label{gFZRHSOy}
\end{lem}
\begin{proof}
Suppose that the Uniformity Test rejects with probability at most
$ \frac{1}{200 \cdot 4^{n}} $,
as otherwise we are done.
From \dWQdKYxc{vzMhnkxb}, $ \AfBMaxZI{Z'} > \frac{k}{6} $.
Since $ \frac{k}{6} = \uaivIgOh{n} $, we can always take
$ k \geq 12 $ so we have $ \AfBMaxZI{Z'} > 2 $.
Let's pick two elements $ q,r \in Z' $.
We define two colorings $c_1$ and $c_2$ the
following way,
\begin{align*}
\HxLQfJAj{c_1}{v} &\faJHPjTb \argmax_j \AfBMaxZI{\yJgNrafg{q}}
\intertext{and similarly}
\HxLQfJAj{c_2}{v} &\faJHPjTb \argmax_j \AfBMaxZI{\yJgNrafg{r}} \text{,}
\end{align*}
for all $ v \in \HelzWRDf{2^n} $.
If the maximum is not well defined then just choose
an arbitrary $j$ for which \AfBMaxZI{\yJgNrafg{.}} is maximal.
From \dWQdKYxc{UDjzaeqm}
the probability that we get \DnoYoBfx{v, \HxLQfJAj{c_1}{v}}
when we measure \raIfJZxu{\varphi_q} in the standard basis is
at least $ \AfBMaxZI{\vXoALQtP{q}}^2 \cdot \frac{1}{3} >
\frac{1}{72 \cdot 2^n} $, for all $v$,
and the same lower-bound is true for getting
\DnoYoBfx{v, \HxLQfJAj{c_2}{v}}, when measuring \raIfJZxu{\varphi_r}.
We split the rest of the proof into two cases.
\begin{itemize}
\item Suppose that the two colorings are different, \WpedDmmP{}
$ \exists v $ \ygMPbVVP{} $ \HxLQfJAj{c_1}{v} \neq \HxLQfJAj{c_2}{v} $.
In this case in line~\ref{qAGbukNT}
we get \DnoYoBfx{v, \HxLQfJAj{c_1}{v}} when measuring
$\VSdxZJNO{N}_q \VSdxZJNO{C}_q$ and
\DnoYoBfx{v, \HxLQfJAj{c_2}{v}} when measuring $\VSdxZJNO{N}_r \VSdxZJNO{C}_r$
with probability at least
$ \DnoYoBfx{\frac{1}{72 \cdot 2^n}}^2 >
\frac{1}{6000 \cdot 4^{n}} $.
It means that with at least the above probability
the Consistency Test will reject in
line~\ref{FMIMsMqc}.
\item Suppose that the two colorings are the same, \WpedDmmP{}
$ \forall v : \HxLQfJAj{c_1}{v} = \HxLQfJAj{c_2}{v} $.
Since $G$ is not 3-colorable,
$ \exists v_1, v_2 \in \HelzWRDf{2^n} $ \ygMPbVVP{}
\DnoYoBfx{v_1, v_2} is an edge in $G$ and
$ \HxLQfJAj{c_1}{v_1} = \HxLQfJAj{c_1}{v_2} $, or equivalently
$ \HxLQfJAj{\oVrArWkh}{v_1, v_2} = 11 $.
Similarly as above, with probability at least
$ \frac{1}{6000 \cdot 4^{n}} $,
we get \DnoYoBfx{v_1, \HxLQfJAj{c_1}{v_1}} when measuring
$\VSdxZJNO{N}_q \VSdxZJNO{C}_q$ and \DnoYoBfx{v_2, \HxLQfJAj{c_1}{v_2}}
when measuring $\VSdxZJNO{N}_r \VSdxZJNO{C}_r$
in line~\ref{qAGbukNT}
of the algorithm.
In this case the Consistency Test will reject with
at least the above probability in
line~\ref{eIpHlpwC}.
\end{itemize}
Since in both cases the Consistency Test rejects with
probability at least $ \frac{1}{6000 \cdot 4^{n}} $,
and the test is chosen with probability $\frac{1}{2}$,
the lemma follows.
\end{proof}
\begin{proof}[Proof of \MJqbMYrm{okAAwxmt}]
Note that \FxucuSoM{NuAJSVLc} runs in
polynomial time.
Furthermore, for both the Consistency and
the Uniformity Test, the algorithm starts with
measuring all the quantum registers according to a
fixed measurement.
So \wQoFYwHz{V} is a proper \cdToKcBp{} verifier.
\dWQdKYxc{iQoQORKN} shows that the
completeness of the protocol is
$ c > 1 - 2^{- \frac{k}{40}} $, while
\dWQdKYxc{gFZRHSOy} shows that the
soundness is $ s < 1 - 12000^{-1} \cdot 2^{-2n} $.
If $ k \geq 120 n $ then $ c - s = \uaivIgOh{2^{-2n}} $
so the theorem follows.
\end{proof}
\section{Conclusions and Open Problems}
\label{HujYVLzw}
In this section we discuss some of the consequences
of the previous results, \WpedDmmP{}
the consequences of \MJqbMYrm{NmPOZGKI} and
\ref{nKVfzRHR}.
We also raise some related open problems.
\subsection{Tightness of the Soundness Analyses}
One can observe that both the \lrcGeBqo{2} verifier
of \FxucuSoM{jEVcePOJ} and the \cdToKcBp{}
verifier of \FxucuSoM{NuAJSVLc}
have soundness parameter $ 1 - \uaivIgOh{4^{-n}} $
and gap $\uaivIgOh{4^{-n}}$.
(As shown by \dWQdKYxc{SaalgorQ}
and \dWQdKYxc{gFZRHSOy}.)
Note that this bound is tight up to a constant
factor in case of \FxucuSoM{jEVcePOJ} and
tight up to some low-order term in case of
\FxucuSoM{NuAJSVLc}.
The reason for this is the same as what was
observed in one of the remark in \cite{Chiesa2011}.
\par
The argument is briefly the following.
Suppose that $ \oVrArWkh \notin \HNGSAaAW $ and
that $G$ is such, that there exist a coloring
\ygMPbVVP{} only one pair of nodes are colored inconsistently.
If the prover gives states of the form defined by
equation~\eqref{BGuJsFqG} but using this
coloring, then the verifier won't notice this
in either of the Uniformity Tests nor in the
Equality Test.
The only place where the verifier can catch the prover
is in the Consistency Test when it checks the colors
of the nodes according to the constraints posed by the graph $G$.
The prover gets caught if the verifier gets
the inconsistently colored nodes in the measurement outputs.
This happens with probability \QUPOtzml{2^{-2n}}
in case of \FxucuSoM{jEVcePOJ} and
\QUPOtzml{n^2 2^{-2n}} in case of \FxucuSoM{NuAJSVLc}.
This means that it is possible to fool the verifier
of \FxucuSoM{jEVcePOJ} with probability
$ 1 - \QUPOtzml{4^{-n}} $ and to fool the verifier of
\FxucuSoM{NuAJSVLc} with probability
$ 1 - \CNzHFRry{4^{-n}} $.
\subsection{\texorpdfstring{Separation Between \SHvwttaw{} and \lrcGeBqo{2}
in the Small-Gap Setting}
{Separation Between QMA and QMA[2] in the Small-Gap Setting}}
\label{BhXaffZV}
As we said in the Introduction, it is a
big open problem whether \SHvwttaw{} is equal to
\lrcGeBqo{2} or not, and we mentioned some evidences
that suggest us that they are not equal.
Here we give another evidence, \WpedDmmP{}
we show that under plausible complexity-theoretic
assumptions \lrcGeBqo{2} is \emph{strictly} more
powerful than \SHvwttaw{} in the low-gap setting.
We elaborate on this in the following.
\par
\MJqbMYrm{NmPOZGKI} shows
that \lrcGeBqo{2} with exponentially or double-exponentially
small gap is exactly characterized by \vxJDyEiW.
So it is natural to ask, what is the power of
\SHvwttaw{} with the same gap, or what upper-bounds can
we give for it?
In a related paper, Ito \QgZuCZdC\ \cite{Ito2010}
showed that \XaOdbtsT{}s (or the class \JWevirQe) with double-exponentially
small gap are exactly characterized by \QZccOLoE.
Since \JWevirQe{} contains \SHvwttaw{} with the same gap,
we have a separation between \SHvwttaw{} and \lrcGeBqo{2}
in the setting where the gap is exponentially or
double-exponentially small, unless $ \QZccOLoE = \vxJDyEiW $.
Note that the result of Ito \QgZuCZdC\ is quite involved.
But if we are only interested in the upper-bound
on \SHvwttaw, then we can give a very simple argument for it,
which we state and prove in the following lemma.
\begin{lem}
$ \displaystyle \bigcup_{\substack{0 < s < c \leq 1, \\
c-s \geq 2^{ -2^{\ipeoICuS} }}}
\KOzxJkVZ{\ipeoICuS}{1}{c}{s}
\subseteq \QZccOLoE $,
where \HxLQfJAj{c}{n} and \HxLQfJAj{s}{n} can be calculated in time
at most exponential in $n$ on a classical computer.
\label{XYHrJdGo}
\end{lem}
\begin{proof}[Proof sketch]
Let $x$ be an input to \KOzxJkVZ{\ipeoICuS}{1}{c}{s} with $c$ and
$s$ having the above property.
The action of the verifier can be described by a
binary-valued measurement
\GGfSpoIn{\nVzyhtCm{P}_0^x, \nVzyhtCm{P}_1^x} on
the proof state, where $\nVzyhtCm{P}_1^x$ corresponds to
acceptance and $\nVzyhtCm{P}_0^x$ corresponds to
rejecting.
Note that the maximum acceptance probability of the
verifier is equal to the spectral norm of
$\nVzyhtCm{P}_1^x$.
(Or in other words the biggest eigenvalue of
$\nVzyhtCm{P}_1^x$.)
Since the proof is on \ipeoICuS-many qubits, the
dimension of $\nVzyhtCm{P}_1^x$ is exponential.
An \QZccOLoE-machine, knowing $x$, can approximate
$\nVzyhtCm{P}_1^x$ with up to an exponential amount
of digits of accuracy.
This is because the verifier is a uniform
quantum circuit of polynomial size.
Now the \QZccOLoE-machine can approximate the spectral
norm of $\nVzyhtCm{P}_1^x$ up to an exponential
amount of bits of accuracy.
\end{proof}
\subsubsection{One-Sided Error Case}
Note that the \vxJDyEiW{} characterization of the small-gap
\lrcGeBqo{2} proof system still holds if we restrict
the proof system to have one-sided error.
Moreover, it is not known whether \SHvwttaw{} can be
made to have one-sided error, so we can investigate
the relation between these classes as well.
Interestingly, it turns out that we can state
an even stronger separation in this case.
This is due to a result by Ito \QgZuCZdC\ \cite{Ito2010}.
\begin{thm}[Theorem~11 of \cite{Ito2010}]
$ \KOzxJkVZ{\ipeoICuS}{1}{1}{<1} \subseteq \LHqjxWJM $.
\end{thm}
This means that in the one-sided error case \lrcGeBqo{2}
with exponentially small gap is \emph{strictly}
more powerful then \SHvwttaw{} with even unbounded gap,
unless $ \LHqjxWJM = \vxJDyEiW $!
\subsection{Nonexistence of Disentanglers}
The discussions in \HVRLKXNY{BhXaffZV}
have an interesting consequence to the existence
question of certain operators called disentanglers.
They were defined by Aaronson \QgZuCZdC\ \cite{Aaronson2009},
as the following.
\begin{defi}[Definition~40 of \cite{Aaronson2009}]
Let us have a superoperator
\FyOFSCmf{\Phi} {\KKIedNYP{\VWqEPttf^N}}
{\KKIedNYP{\VWqEPttf^M \NUxdODWZ \VWqEPttf^M}}.\footnote{We
denote the set of all density operators on space
\zdLEuPyh{H} by \KKIedNYP{\zdLEuPyh{H}}.}
We say that $\Phi$ is an \DnoYoBfx{\varepsilon,
\delta}-disentangler if
\begin{itemize}
\item \HxLQfJAj{\Phi}{\rho} is $\varepsilon$-close
to a separable state for every $\rho$, and
\item for every separable state $\sigma$,
there exists a $\rho$ \ygMPbVVP{} \HxLQfJAj{\Phi}{\rho} is
$\delta$-close to $\sigma$.
\end{itemize}
\label{IYzbetOO}
\end{defi}
Note that if there exist a
\DnoYoBfx{\frac{1}{\wrDoIJTw{\log M}}, \frac{1}{\wrDoIJTw{\log M}}
}-disentangler with $ \log N = \wrDoIJTw{\log M} $,
and if that disentangler can be implemented in
\wrDoIJTw{\log M}-time, then $ \SHvwttaw = \lrcGeBqo{2} $.
So it is not believed that such a disentangler exist.
Towards proving this, Aaronson \QgZuCZdC\ showed that no \DnoYoBfx{0,0}-disentangler
exists for any finite $N$ and $M$.
The discussion in the previous section implies that
there exist no disentangler with approximation error
inverse of the square of the dimension.
More precisely we have the following corollary.
\begin{cor}
There exist a function $ \HxLQfJAj{f}{M} = \uaivIgOh{M^{-2}} $,
\ygMPbVVP{} there exist no \wrDoIJTw{\log M}-time implementable
\DnoYoBfx{\HxLQfJAj{f}{M}, \HxLQfJAj{f}{M}
}-disentangler with $ \log N = \wrDoIJTw{\log M} $,
unless $ \QZccOLoE = \vxJDyEiW $.
\end{cor}
\begin{proof}
Suppose that there exist such a disentangler $\Phi$,
for $ \HxLQfJAj{f}{M} = \kappa_1 \cdot M^{-2} $,
for some constant $ \kappa_1 $ to be specified later.
Let $ L \in \vxJDyEiW $.
\MJqbMYrm{QoOYZYVy} implies that
$ L \in \KOzxJkVZ{\ipeoICuS}{2}{1}{1 - \kappa_2 \cdot 4^{-n}} $,
for some constant $ \kappa_2 $ and where the
dimension of both proof states are $ 3 \cdot 2^n $.
Let \wQoFYwHz{V} be the corresponding verifier.
We show that $ L \in \KOzxJkVZ{\ipeoICuS}{1}{c}{s} $ with
$ c-s = \uaivIgOh{4^{-n}} $ by constructing a
verifier \wQoFYwHz{W} that uses only one proof.
By \dWQdKYxc{XYHrJdGo} it holds that
$ \KOzxJkVZ{\ipeoICuS}{1}{c}{s} \subseteq \QZccOLoE $
so we get that $ \QZccOLoE = \vxJDyEiW $.
\par
We are left to define verifier \wQoFYwHz{W}.
\wQoFYwHz{W} fist applies $\Phi$ on its quantum proof
then simulates \wQoFYwHz{V} on the output of $\Phi$
and outputs whatever \wQoFYwHz{V} outputs.
Note that $\Phi$ is \ipeoICuS-time implementable and
the size of the proof of \wQoFYwHz{W} is also
polynomial.
To see completeness for \wQoFYwHz{W}, note that
there exist a state $ \raIfJZxu{\psi} \NUxdODWZ \raIfJZxu{\psi} $
with which \wQoFYwHz{V} accepts with probability $1$.
From \MOVPSHbF{IYzbetOO} there exist a
$ \rho $ \ygMPbVVP{} \HxLQfJAj{\Phi}{\rho} is
\HxLQfJAj{f}{3 \cdot 2^n}-close to
$ \raIfJZxu{\psi} \NUxdODWZ \raIfJZxu{\psi} $.
Since $ \HxLQfJAj{f}{3 \cdot 2^n} =
\frac{\kappa_1}{9} \cdot 4^{-n} $,
the probability of acceptance of \wQoFYwHz{W} is
at least $ 1 - \frac{\kappa_1}{9} \cdot 4^{-n} $.
Similarly, for the soundness of \wQoFYwHz{W},
we have that for all separable states,
\wQoFYwHz{V} accepts with probability
at most $ 1 - \kappa_2 \cdot 4^{-n} $.
Again from \MOVPSHbF{IYzbetOO},
for all $\rho$, \HxLQfJAj{\Phi}{\rho} is
\HxLQfJAj{f}{3 \cdot 2^n}-close to a separable state.
So the probability of acceptance of \wQoFYwHz{W}
is at most $ 1 - \kappa_2 \cdot 4^{-n}
+ \frac{\kappa_1}{9} \cdot 4^{-n} $.
If $ \kappa_1 $ is sufficiently small then
$ c-s = \uaivIgOh{4^{-n}} $, so the corollary follows.
\end{proof}
\subsection{\texorpdfstring{Notes on \cdToKcBp{} Proof Systems}
{Notes on BellQMA Proof Systems}}
\label{fCJGhyBh}
An interesting consequence of
\MJqbMYrm{NmPOZGKI} and
\ref{nKVfzRHR} is that
in the small-gap setting, \pUeVeClC{k} proof
systems have the same power as \lrcGeBqo{k} proof
systems if $k$ is at least a linear function of
the input length.
Such a result is not known to hold in the
normal-gap setting.
As we mentioned before, in the normal-gap
setting we now that if $k$ is constant
then \pUeVeClC{k} collapses to \SHvwttaw,
and the proof of this fact doesn't generalize
to the small-gap setting.
This means that it is an interesting open question
to figure out the power of \pUeVeClC{2} with
exponentially small gap.
There could be two possibilities:
\begin{itemize}
\item It is quite unlikely that the small-gap
version of $\pUeVeClC{2} = \vxJDyEiW$,
because it would give a very powerful proof
system, and moreover it would show that
if a verifier is restricted to Bell-measurements
then it gains a lot of extra power if we decrease the bound on
the gap; since $\pUeVeClC{2} = \SHvwttaw$ if the gap
is inverse-polynomial, but $\pUeVeClC{2} = \lrcGeBqo{2}$
if it is inverse-exponential.
\item So we conjecture that the small-gap
$\pUeVeClC{2} \subset \vxJDyEiW$.
But this would imply that somewhere
between constant and linear number of provers,
the power of \pUeVeClC{k} significantly increases.
\end{itemize}
We leave the study of this class for future work.
\subsection{Error and Proof Reduction}
Note that as a side-product of our results,
in both the \pUeVeClC{k} and \lrcGeBqo{k} proof
systems we can `amplify' the error from
double-exponentially small gap to single-exponentially
small gap.
Also in the case of \lrcGeBqo{k}, we can make the proof
system to have \emph{one-sided error},
which up to our knowledge,
has only been shown to hold for \ACroxxZA{} \cite{Jordan2011}.
(Additionally, the number of proofs can be reduced to two,
but this also follows from \cite{Harrow2010},
where an essentially different argument was used.)
\subsection{\texorpdfstring{\lrcGeBqo{k} with Small Gap and Logarithmic-Length Proofs}
{QMA[k] with Small Gap and Logarithmic-Length Proofs}}
\label{sec:QMAlog}
We also examine multi-prover \SHvwttaw{} proof systems
with small gap and where each proof consist of at most
\FIqGvTZG{n} qubits, in the hope that we can separate them
from the ones that have \wrDoIJTw{n}-length proofs.
Unfortunately we were not able to do this in general,
only in the case where the gap is inverse-exponential,
which follows from a few simple observations.
If the gap is smaller, say double-exponentially small
or unbounded, then we give a lemma which simplifies the
proof system by converting it to one with single-qubit
proofs without changing the order of magnitude of the gap.
The details follow.
\begin{lem}
$ \displaystyle \sVwdElyU =
\bigcup_{\substack{0 < s < c \leq 1, \\ c-s \geq 2^{ - \ipeoICuS }}}
\KOzxJkVZ{\FIqGvTZG{n}}{\wrDoIJTw{n}}{c}{s} $,
where \HxLQfJAj{c}{n} and \HxLQfJAj{s}{n} can be calculated in
\wrDoIJTw{n}-time on a classical computer.
\end{lem}
\begin{proof}[Proof sketch]
The containment $ \sVwdElyU \subseteq
\bigcup_{\substack{0 < s < c \leq 1, \\ c-s \geq 2^{ - \ipeoICuS }}}
\KOzxJkVZ{\FIqGvTZG{n}}{\wrDoIJTw{n}}{c}{s} $ is trivial
since in \sVwdElyU{} the gap is always at least
inverse-exponential.
So we only need to prove the other direction.
Consider the class \KOzxJkVZ{\FIqGvTZG{n}}{\wrDoIJTw{n}}{c}{s}
for some $c$ and $s$, for which the conditions in the
lemma hold.
Note that $ \KOzxJkVZ{\FIqGvTZG{n}}{\wrDoIJTw{n}}{c}{s} \subseteq
\vtZmVJmM{c'}{s'} $, where $ c' - s' \geq 2^{ - \ipeoICuS } $.
(In fact they are equal.)
The reason behind it is that for each proof there exists
a unitary transformation that creates it, say, from \raIfJZxu{0}.
Since the unitaries are on \FIqGvTZG{n}-many qubits,
they can be described up to exponential precision
by quantum circuits of size \wrDoIJTw{n}.
The \ACroxxZA{} verifier expects these descriptions as its proof.
The completeness and soundness follows easily.\footnote{For
a detailed (but a bit different) proof of this fact
see \cite{Gharibian2011}.}
\par
The above \ACroxxZA{} proof system can be converted to an \kJmbkUXz{}
proof system with exponentially small gap in the following way.
The \kJmbkUXz{} proof is the same as the \ACroxxZA{} proof.
Once the proof is fixed the question is to estimate the
acceptance probability of a \ipeoICuS-time quantum computation
to exponential precision.
This problem is in \AIJjtsxK, and since $ \AIJjtsxK = \sVwdElyU $,\footnote{\AIJjtsxK{}
is the unbounded-gap version of \VGZgApSi.
For the exact definition of the class and the proof of the above
equality see for example the survey by Watrous \cite{Watrous2008a}.}
we have an \kJmbkUXz{} proof system with the given parameters.
This \kJmbkUXz{} class is obviously in \sVwdElyU{} via the same argument
as $ \kJmbkUXz \subseteq \sVwdElyU $ for the normal-gap version of \kJmbkUXz.
\end{proof}
\begin{rem}
Note that if we decrease the proof lengths to only $1$
qubits then the resulting class is obviously still
equals to \sVwdElyU.
More formally
\[ \displaystyle \sVwdElyU =
\bigcup_{\substack{0 < s < c \leq 1, \\ c-s \geq 2^{ - \ipeoICuS }}}
\KOzxJkVZ{1}{\wrDoIJTw{n}}{c}{s} \text{,} \]
where \HxLQfJAj{c}{n} and \HxLQfJAj{s}{n} can be calculated in
\wrDoIJTw{n}-time on a classical computer.
\end{rem}
This observation is generalized by the following lemma
to any smaller gaps.
\begin{lem}
$ \displaystyle \KOzxJkVZ{\FIqGvTZG{n}} {\ipeoICuS} {c} {s}
\subseteq \KOzxJkVZ{1} {\ipeoICuS}
{1 - 2^{- t} \cdot \DnoYoBfx{1-c}}
{1 - 2^{- t} \cdot \DnoYoBfx{1-s}} $,
for some $t$ \ygMPbVVP{} $ \HxLQfJAj{t}{n} \in \wrDoIJTw{n} $,
and $c$ and $s$ are arbitrary functions of $n$.
\label{HTTPbCwP}
\end{lem}
We present the proof of this lemma in
\IhApwfvN{zKhwWgDg}
on page~\pageref{zKhwWgDg}.
Let us explicitly state here the previously mentioned corollary.
\begin{cor}
It holds that
\begin{align*}
\bigcup_{\substack{0 < s < c \leq 1, \\ c-s \geq 2^{ - 2^{\ipeoICuS} }}}
\KOzxJkVZ{\FIqGvTZG{n}}{\ipeoICuS}{c}{s} &=
\bigcup_{\substack{0 < s < c \leq 1, \\ c-s \geq 2^{ - 2^{\ipeoICuS} }}}
\KOzxJkVZ{1}{\ipeoICuS}{c}{s} \text{,}
\intertext{and}
\bigcup_{0 < s < c \leq 1} \KOzxJkVZ{\FIqGvTZG{n}}{\ipeoICuS}{c}{<s} &=
\bigcup_{0 < s < c \leq 1} \KOzxJkVZ{1}{\ipeoICuS}{c}{<s}
\text{.}
\intertext{Note that in \dWQdKYxc{HTTPbCwP}
the one-sided error property is preserved.
So we also have for example}
\KOzxJkVZ{\FIqGvTZG{n}}{\ipeoICuS}{1}{<1} &=
\KOzxJkVZ{1}{\ipeoICuS}{1}{<1} \text{.}
\end{align*}
\end{cor}
We don't know any better upper-bound for
\KOzxJkVZ{1}{\ipeoICuS}{c}{s} with $c-s \geq 2^{ - 2^{\ipeoICuS} }$
then the trivial \vxJDyEiW.
It would be interesting to strengthen this bound
or give some non-trivial lower-bound.
We leave this question for future work.
\subsection{More Open Problems}
Here we list some more open problems that
we think may be interesting to work on.
\begin{itemize}
\item What is the power of \lrcGeBqo{k} and
\pUeVeClC{k} with unbounded gap?
Can we at least show some upper-bounds?
\item What is the power of \KOzxJkVZ{1}{1}{1}{1 - 2^{- 2^{\ipeoICuS}}}
or \KOzxJkVZ{1}{1}{1}{<1}?
\qpcpnInM{} the proof system has only one qubit
as its proof but we allow double-exponentially
small or unbounded gap.
Are they the same as \AIJjtsxK?
Note that the known
$ \KOzxJkVZ{\FIqGvTZG{n}}{1}{\frac{2}{3}}{\frac{1}{3}}
= \VGZgApSi $ proofs \cite{Marriott2005,Beigi2011} break
down if the gap is so small.
\end{itemize}
\section*{Acknowledgements}
The author would like to thank Rahul Jain and
Penghui Yao for helpful discussions on the topic.

redpajama_set_name: RedPajamaArXiv


text:
Гузе́ль Гале́евна Сулейма́нова () (25 февраля 1927, Уфа, БАССР, РСФСР, СССР — 14 апреля 1969, там же) — советская башкирская артистка балета. Народная артистка Башкирской АССР (1953). Народная артистка РСФСР (1955). Депутат Верховного Совета БАССР 7-го созыва.

Биография
Гузель Галеевна Сулейманова родилась 25 февраля 1927 года в Уфе в рабочей семье. Отец, Шагали-агай, родом из села Исламбахты современного Ермекеевского района Башкортостана. Мать, Габида Гиляжетдиновна Кудашева, из села Кляшево современного Чишминского района Башкортостана — родины Мустая Карима.

Гузель с 1936 по 1947 годы училась на башкирском отделении Ленинградского хореографического училище (педагоги Н. А. Камкова, М. Ф. Романова).

В перерыве учёбы с 1945 года и в дальнейшем работала в Башкирском государственном театре оперы и балета.

В 1941 году вернулась из Ленинграда в Уфу, где работала в балетной труппе БГТОиБ, танцевала сольные партии в кордебалете и оперных спектаклях. В Уфу был эвакуирован Киевский театр оперы и балета. С Гузель Галеевной здесь стала заниматься артистка Киевского театра балерина Антонина Васильева Вместе они подготовила для Гузель сольную партию подруги Сванильды из «Коппелии».

В 1943 году уехала в Пермь для продолжения обучения. В Пермь было эвакуировано Ленинградское хореографическое училище и Ленинградский театр оперы и балета.

Опять вернулась в Уфу в 1944 году, чтобы принять участие в работе над балетом «Журавлиная песнь», который должен был показан к 25-летию Башкирской автономии. Окончила училище в 1947 году. На выпускном вечере училища танцевала на сцене Кировского театра оперы и балета, исполнив два па-де-де — из «Лебединого озера» П.Чайковского и «Дон Кихота» Л.Минкуса.

На сцене Башкирского театра оперы и балета Гузель Галеевна танцевала партии в классических балетах и в балетах национальной классики: Зайтунгуль («Журавлиная песнь»), Амина, жена Салавата Юлаева («Горный орел»), Галима («Черноликие»).

Гастролировала с театром в СССР и 18 странах мира.

Умерла 14 апреля 1969 года. Похоронена в Уфе.

Роли в спектаклях
Дебют в Башкирском театре оперы и балета в партии Марии в балете «Бахчисарайский фонтан» Бориса Асафьева в 1945 году.

Одетта-Одиллия в «Лебедином озере» Петра Чайковского, Зайтунгуль в балете Льва Степанова и Загира Исмагилова «Журавлиная песнь», Зарифа в «Горной были» Александра Ключарёва, Тао-Хоа в «Красном маке» Рейнгольда Глиэра, Китри в «Дон-Кихоте» Людвига Минкуса, Гульназира в одноимённом балете Наримана Сабитова, партия Галимы в балете «Черноликие» Халика Заимова и Александра Чугаева.

Награды и звания
 Народная артистка Башкирской АССР (1953)
 Народная артистка РСФСР (1955)

Литература
 Саитов С. Танец ликующий. Уфа, 1968.
 Жиленко Н. «О чём этих линий полёт, неужто он тоже не вечен?» //Гран-па башкирского балета. Уфа, 2007.
 Башкирская энциклопедия. Уфа. Изд. Башкирская энциклопедия. 2007.

Память
В Уфе по улице Октябрьской Революции д. 9, где жила Г. Сулейманова установлена мемориальная доска.

Примечания

Ссылки

 http://www.vatandash.ru/index.php?article=1368
 http://www.bashinform.ru/news/437475/

Персоналии:Башкирский театр оперы и балета
Выпускники Академии русского балета имени А. Я. Вагановой
Ученицы Марии Романовой
Депутаты Верховного Совета Башкирской АССР седьмого созыва

redpajama_set_name: RedPajamaWikipedia


ToGo supports our members to advance transportation options in Oregon. That vision includes a transportation network that enhances choice, access and vitality—hallmarks of what makes Oregon a destination for home, work and play.
ToGo members regularly participate in and provide comments to groups such as Oregon Transportation Committee, Public Transportation Advisory Committee, and collaborate with Oregon Department of Transportation Active Transportation Division.
Individuals and organizations interested in the future of Oregon's transportation system are encouraged to join and participate in ToGo.
ToGo is a sponsor of the Oregon Transportation Conference. The Conference features sessions on transportation options coordinated by ToGo and others. Additionally, a luncheon keynote address spotlights transportation options. Members of ToGo have the opportunity to serve as ambassadors while gaining insight into best practices from around the state.
ToGo members are also eligible to apply for scholarships to travel to and attend the quarterly Statewide Transportation Options Meetings, other relevant events and no-cost memberships. Maximum scholarship is $250 per individual per calendar year and $750 per organization per calendar year, given as a reimbursement for documented expenses, limited to transportation, lodging, and event registration.


from the personal name Wiibo, a short form of a compound name formed with wig 'battle', 'fight' as the first element + a second element beginning with b, such as berht 'bright' or bald 'bold'. variant of Weibel.
Where is the Weible family from?
You can see how Weible families moved over time by selecting different census years. The Weible family name was found in the USA, and the UK between 1840 and 1920. The most Weible families were found in the USA in 1880. In 1840 there were 5 Weible families living in Ohio. This was about 56% of all the recorded Weible's in the USA. Ohio had the highest population of Weible families in 1840.
Use census records and voter lists to see where families with the Weible surname lived. Within census records, you can often find information like name of household members, ages, birthplaces, residences, and occupations.
What did your Weible ancestors do for a living?
In 1880, a less common occupation for the Weible family was Barber. Farmer, Laborer and Keeping House were the top 3 reported jobs worked by Weible. The most common Weible occupation in the USA was Farmer. 28% of Weible's were Farmers.
Census records can tell you a lot of little known facts about your Weible ancestors, such as occupation. Occupation can tell you about your ancestor's social and economic status.
What Weible family records will you find?
There are 3,000 census records available for the last name Weible. Like a window into their day-to-day life, Weible census records can tell you where and how your ancestors worked, their level of education, veteran status, and more.
There are 642 immigration records available for the last name Weible. Passenger lists are your ticket to knowing when your ancestors arrived in the USA, and how they made the journey - from the ship name to ports of arrival and departure.
There are 1,000 military records available for the last name Weible. For the veterans among your Weible ancestors, military collections provide insights into where and when they served, and even physical descriptions.
You've only scratched the surface of Weible family history.
What is the average Weible lifespan?
Between 1944 and 2004, in the United States, Weible life expectancy was at its lowest point in 1944, and highest in 1965. The average life expectancy for Weible in 1944 was 35, and 77 in 2004.
An unusually short lifespan might indicate that your Weible ancestors lived in harsh conditions. A short lifespan might also indicate health problems that were once prevalent in your family. The SSDI is a searchable database of more than 70 million names. You can find birthdates, death dates, addresses and more.


text:
Go to the front page
Maritime inquiry 1939 - 1945
D/S Ingerfem
more information about the ship D/S Ingerfem
The information below regarding ships in the Nortraship fleet is a direct transcript of the original source "Sjøforklaringer fra andre verdenskrig (1940 - 1945)". The informasjon is collected from maritime inquiries held during and right after the war. The information may differ from the other quality assured information in Krigsseilerregisteret.
Ca. 59 gr. N 21 gr. V
Torpedert [av tysk ubåt]
Leith - Halifax
Inquiry (in norwegian)
Belfast, Nord-Irland
Konsul Raymond A. Burke
Thereupon appeared as Witness, the sole surviver, Ole Næss ...
"The s/s "INGERFEM" left Loch Ewe, Scotland, on the 24th day of December, 1942, in ballast, bound for Halifax, Nova Scotia, in convoy. After being three days out from Port, we lost the convoy and proceeded for two days alone. On the afternoon of the 29th of December, two British airplanes appeared above us and gave us instructions to the effect that they would return at 10 p.m. the same evening to advise us whether to proceed to Canada or return to Scotland, as the ship's engine was out of repair; this trouble with the engine was the cause of our dropping out of the convoy. Up to 10.30 p.m. the airplanes had not returned, but at that hour a torpedo hit the vessel and she went down within five minutes. The crew took to two lifeboats. I was one of the last to leave the ship, and as I was getting into the lifeboat, I saw the Captain, the 3rd Officer and one of the Norwegian Gunners trying to get another lifeboat launched from the bridge, but before they could do so, the vessel broke and sank. There were eight men i my lifeboat and I would say there were about thirty in the second one, which we lost in the darkness. The eight of us drifted in this lifeboat for three days. On the third day, the 1st day of January, 1943, the lifeboat capsized, but we all were able to get back into it again. The same day the Chief Officer and two of the crew died. After this the lifeboat was practically always full of water and it was difficult to keep afloat. For a further seven days we drifted, and on the seventh day the lifeboat again turned over, but the remaining five of us suceeded in righting the lifeboat again. During that night the other four men died, and I drifted alone for some days until the 11th January, on which day I was picked up five hundred miles west of Scotland, by the s/s "STEEMAC", an American vessel, and landed in Bangor Bay, Northern Ireland, on 13th day of January, 1943 and taken to Ards District Hospital, Newtownards, Co. Down, suffering from severe shock and salt water sores."
The above being the only evidence, the Maritime Declaration was then terminated.
Deck log (in norwegian)
Crew list (40)
We have so far registered
68291 seafarers
30001 Norwegians in Nortraship
27557 foreigners in Nortraship
About Krigsseilerregisteret.no
Development of the register
Endre til norsk
Centre for the History of Seafarers at WarJon Michelet master's degree scholarship

redpajama_set_name: RedPajamaCommonCrawl


We have strong heritage in the technology sector since the early 1990s, when we worked with pioneers such as Sun Microsystems and Apple Computers, through to the present day where our clients include several of Dublin's 'Silicon Docks' residents. This includes local success stories such as Realex Payments and a number of growing international companies which have chosen Ireland as their EMEA headquarters.
Our work includes brand building, business to business public relations, event management and recent specific projects around data centre establishments for three of the world's largest tech multinationals.


What Sidibé offered, and his peers at the time, such as Seydou Keita also of Mali, Mama Casset of Senegal and Joseph Moise Agbodjelou of Benin, was a space where people were afforded agency over their image, rather than being subject to a western lens that projected an exoticism or poverty upon them. The resulting pictures were "Africans for Africans". These photographs are ripostes to the anthropological images of ''natives'' made by Europeans in the late 19th and early 20th centuries. Those photographs, in which the subjects had no say in how they were seen, did much to shape the Western world's idea of Africans. Something changed when Africans began to take photographs of one another: You can see it in the way they look at the camera, in the poses, the attitude. The difference between the images taken by colonialists or white adventurers and those made for the sitter's personal use is especially striking in photographs of women. In the former, women are being looked at against their will, captive to a controlling gaze. In the latter, they look at themselves as in a mirror, an activity that always involves seriousness, levity and an element of wonder.
His photos have been prized on the international art market for years and adorn the walls of leading photo galleries across the world, but 76-year-old Malick Sidibe still resides in a one-room home in Mali, attended to by his wives and children. A national hero, his contribution to his country's historical record has, for many, crafted the image of Mali, and Africa at large.


text:
The Men's Time Trial event at the 2010 South American Games was held at 11:30 on March 17.

Medalists

Results

References
Report

Cycling at the 2010 South American Games
2010 in road cycling


Measure your proficiency in Hebrew through the online language testing services offered by the NYU School of Professional Studies. Choose from 4-point, 12-point, or 16-point options, depending upon your professional or academic needs. Point scoring is equivalent to undergraduate credits at US colleges; credit granted is at the discretion of the institution receiving the results.
This test assesses reading, writing, and listening proficiency in Modern Hebrew.
The 16-point exam in Modern Hebrew is the same as the 12-point exam except for the addition of a 350-word essay on a more complex subject.
This exam is available to those who have achieved a score of at least 8 on the 12-point Modern Hebrew exam and wish to earn 4 additional points.


4k00:15MOSCOW, RUSSIA - CIRCA 2018: Children's clothing store clothes for kids. Dolly movement along racks with autumn winter warm jackets.
hd00:15View of three dimensional knitting machine in a factory of knitted underwear.


Expansive home in Carmel Valley's Seabreeze Farms offers 5 bedrooms up and an optional flex room downstairs. Beautifully upgraded chef's kitchen with granite counters, stainless steel appliances, double ovens & large island with prep sink. The kitchen opens to breakfast area & spacious family room with fireplace. Intimate formal living & dining room with dramatic ceilings, clerestory windows & sweeping spiral staircase. Elegant Versailles travertine flooring & plantation shutters. Walk to top ranked schools.


text:
Best SMS App Replacements For Android (2015)
Best SMS applications for your Android device
Despite growing popularity of chat apps, text messaging is far from dead. Hundreds of millions of SMS's are sent every single day and it's not going to change anytime soon.
To send and receive messages, you need an SMS app. All Android smartphones come with such an application, but chances are it's not the best app in the world. If you're tired of putting up with countless bugs or boring appearance, check out the list I've prepared for you below with some alternatives.
The list includes 6 excellent text messaging apps for Android, which I've cherry picked with your needs and convenience in mind. Each of them offers a different set of features, making them appealing to all sorts of people. Enjoy!
Released by Google and installed on Android 4.4 KitKat by default, Hangouts is an official application for the service known by the same name. It allows you to make voice and video calls and thanks to the recent update, it supports text messaging. The app doesn't offer many features, but provides basic functionality wrapped in an elegant interface. With Hangouts, you can send and receive both SMS and MMS messages.
Living up to its straightforward name, Messenger is a simple texting app designed for speed and beauty. Its gorgeous Material Design interface makes messaging a real pleasure. Beautiful animations and bold colours add a little bit of life to otherwise boring-looking texts.
Messenger is compatible with most Android devices and allows you to send and receive MMS messages as well as assign different colours to favourite contacts.
QKSMS
I bless the day I found QKSMS in the Play Store. It was soon after Android 5.0 was released and I'd been looking for a neat Material Design SMS app for my phone. QKSMS was just what I was looking for by offering a beautiful and colourful interface paired with advanced functionality.
The app can display a pop-up when you receive a text, send group messages, automatically tone-down colours at night, and remove diacritics from your texts to help you save money. QKSMS is a free app, but if you wish to remove ads and unlock further theming options (there are 19 beautiful colours by default), you can upgrade straight from within the app.
Sliding Messaging
Sliding Messaging is probably the most advanced SMS app in the Play Store. It was designed with power users in mind and equipped with a plethora of options. When you download it, you can not only send and receive messages, but also customize the interface and experience to a great extent. The app allows you to change the theme (both UI elements and colours), define font type, size and alignment and set background for conversation view as well as gestures and navigation style.
Sliding Messaging can display a pop-up when a new message arrives, but in-app it's fully editable with two themes and a palette of options to choose from. Additionally, the app allows you to reply, call or mark the message as read, straight from the notification area.
Handcent SMS
Being one of the most downloaded SMS apps in the Store, Handcent SMS brings a lot of features to the table. As well as support for SMS and MMS messaging, it enables group texting, advanced spellcheck, theming, and sharing files. Moreover, it has support for Emoji icons and a built-in Blacklist feature to block numbers you don't want to receive messages from. The app can also schedule tasks and thanks to Handcent's own integrated online chat service, send messages to any mobile platform for free.
chomp SMS
Downloaded by over 10 million users, chomp SMS is an app that once was exclusive to jailbroken iPhone. Now it's available for everyone and offers a range of useful features. It can send and receive texts, block unwanted numbers and SPAM, and schedule messages. The app is also equipped with a number of security controls, for instance passcode lock for conversations and an ability to backup essential data. Plus, chomp SMS has heaps of customization options for notification icons, ringtones, vibrate patterns, font types and sizes and background wallpapers. Support for quick reply box is there as well.
chomp SMS has a younger sibling available in the Play Store. Textra SMS is a less powerful, yet lighter app for older devices.
If you recommend any other SMS apps for Android, be sure to leave them in the comments below and we may add them to the post.
AndroidAndroid AppsApps & SoftwareApps
Get UltraLinx Ad-Free for 30 Days
Best Productivity Apps For Android (2015)
By Jaroslaw
Best Lock Screen Replacement Apps For Android (2015)
Best Gallery Apps For Android (2015)
© 2020 UltraLinx. All Rights Reserved.


The South Routt school district is a rural district with just over 400 students attending its three schools. It is also among a small but growing number of Colorado districts where local, grass-fed beef is now on the school lunch menu.
It started last spring when South Routt parent Jane Colby applied for a $1,500 grant from Colorado Action for Healthy Kids to help cover the cost of the more expensive beef. She won the grant on behalf of the district, and this year, some of the district's burritos, taco salads and spaghetti sauces contain ground beef from cattle raised in grassy fields about 25 miles away.
"We live in this ranching community and I myself like to buy the local beef," Colby said.
She believes local beef raised on grass with no added hormones or antibiotics is healthier than traditional feedlot beef. It's also more expensive. The district pays $3.48 a pound for the ground beef it gets from Yampa Valley Beef every month.
The district pays about $2 a pound for beef from a food service supplier and also receives beef from the USDA's School/Child Nutrition Commodities program.
Even at $3.48 a pound, the district's price is about a dollar less than Yampa Valley Beef's wholesale price of $4.55. Sonja Shoemaker, who owns the company with her husband Wayne, said they agreed to the lower price because they wanted to help the district provide local beef to students.
Although there's no exact tally of school districts that use local beef in their cafeterias, the number seems to be growing, said Jeremy West, nutrition service director for Weld County District 6 and chairman of the Colorado Farm to School Task Force. He estimated that a dozen districts in the state use some local grass-fed beef in student meals.
Weld District 6, which is in the second year of a move toward majority scratch cooking, is currently in the bid process for beef patties from cows raised with no added antibiotics or hormones and at least partially on grass. West said if a viable bid comes through, local beef hamburgers will debut in February in the high school cafeterias, where some weeks feature a "make-your-own" burger bar.
"We want a better hamburger to serve in that format," West said.
If the switch is successful, West hopes to implement the same change for burgers served in middle and elementary schools, and ultimately switch to local beef for all beef-based meals served in the district.
It's unclear whether the discovery last spring that some school ground beef contained ground-up meat scraps treated with ammonium hydroxide has prompted districts to join the local beef movement. Colby, the parent who spearheaded the local beef effort in South Routt, said she applied for the grant before the "pink slime" episode.
West said while the uproar didn't affect Weld District 6, it may have sparked a greater interest in local beef in other districts.
As an early adopter of local beef, Colorado Springs District 11 also escaped the "pink slime" controversy. The 28,000-student district began a gradual switch from government commodity beef in 2007, focusing first on hamburger patties served at the district's high schools.
Since 2010, all beef served in the district comes from Ranch Foods Direct, a meat-packing facility and retail market based in Colorado Springs with a cattle ranch in western Kansas. The beef comes from cattle partially raised on grass with no added hormones or antibiotics.
"We immediately had success with the fresh flavor, and the texture of the beef was so much better," said Rick Hughes, director of food and nutrition services for District 11.
In neighboring Falcon School District 49, Nutrition Services Director Monica Deines-Henderson switched to bulk ground beef from Ranch Foods Direct three years ago.
"I'm a firm believer in keeping food as natural as possible for the students," she said.
In keeping with department's "simple food" slogan, the district aims to use fresh, minimally processed ingredients that have no added preservatives, dyes, growth hormones or antibiotics.
Switching to grass-fed local beef doesn't come without challenges for school food service departments. In addition to tight budgets, there may be limited kitchen facilities or a lack of staff training on handling and cooking raw meat.
In the South Routt school district, the local beef grant was simply not enough to cover more than 20 percent of the district's 500-pound monthly order. Susan Hart, the district's food services director, said she still uses USDA commodity beef as well as pre-cooked hamburger patties with soy filler.
Like most food service directors, Hart believes hamburgers are an ideal use of local beef because the meat's higher quality is more obvious than when it's incorporated into dishes like chili or spaghetti sauce. She hopes the local beef program will continue next year with a few refinements.
"I would really like to spend a little more and have them process it into burgers," said Hart.
Rick Hughes, food and nutrition services director in District 11, agrees that higher quality beef costs more but believes it's still affordable for any district. The key is taking a hard look at the budget, he said. For example, Hughes and his team eliminated some of the paper products used on cafeteria trays after discovering they added 3-5 cents to the cost of each meal.
Finding a high-quality beef producer is also a challenge in some districts.
Safe food-handling techniques are also an issue for districts introducing raw beef products, particular hamburger patties. Hughes said that is one of the reasons District 11 introduced local beef gradually.
"It was scary for us at first," he said.
Today, the district has at least one employee in all 65 serving locations certified by the ServSafe Food Safety program created by the National Restaurant Association. West said the same is true for all 31 kitchens in Weld County 6.
"It's a matter of staff education," said West.
This entry was posted in General Advocacy, Pink Slime and tagged Callicrate Beef, Colorado Farm to School Task Force, D11 School District, Jeremy West, Ranch Foods Direct, Rick Hughes, Yampa Valley Beef. Bookmark the permalink.


Cllr Tony Walsh said the committee has determined the extent of services available within the county.
The committee comprising councillors Ger Carthy, Willie Fitzharris, Tom Forde, Davy Hynes, Robert Ireton, Willie Kavanagh, Johnny Mythen, Frank Staples and Tony Walsh concluded that a report needs to be commissioned to uncover 'the state of the adult and child mental health services in Co Wexford'.
Cllr Walsh said Arden House, which is replacing Slaney House in Wexford for child and adult mental health services, will not open now until September.
Calling for the centre to be full staffed, Cllr Walsh said Wexford County Council should work in collaboration with other bodies to build resilience among Wexford teenagers and children.
'It would be a great investment which would reduce the high level of costs which are running into the millions at the moment,' he said.
Cllr Hynes called for programmes to be initiated to help build resilience among teenagers 'to avoid some of the tragedies we are seeing'.
Cllr Marie Doyle congratulated the councillors on the report, adding that on a daily basis suicidal people are being turned away from Wexford General Hospital. 'They are being discharged and that is putting enormous pressure on their families,' she said.
He said people suffering from mental health issues come up against problems when it comes to accessing local authority housing. 'People are getting dislodged and displaced within the system. It stinks at the moment,' he said, before adding that more tragedies could happen in the county because of the lack of services; which have been sought for 15 years. Chairman Cllr Keith Doyle suggested that a deputation of councillors meet with the minister to debate their requests to improve the well-being of Wexford people.


Hotel Kabadoni is an ideal place for those who appreciate comfort, coziness and care.
The interior of Hotel Kabadoni is a mixture of art nouveau, ancient Georgian and eastern motifs. Eastern elements and mirrors supplement the hand-painted lobby of the hotel. A variety of colors characteristic of the East is balanced by minimalist furniture in the art nouveau style. The neutral color of the walls is brightened up by the works of famous designers using simple, clean and modern shapes, as well as by colorful Georgian rugs and carpets.
There are 21 rooms in the hotel. Guests and visitors may enjoy a wide range of Georgian and European dishes prepared by our chefs at Kabadoni Restaurant, which is also distinguished for its outdoor terrace and unobstructed view of the Alazani Valley and the Caucasus Mountains.


text:
Q: Should I use Java 8 Streams Api to combine two Collections? I have this situation where it seems that the Java 8 Streams API would be helpful, but I'm not fully sure how it could be.
From two Collections with distinct element types, I want to build a third collection whose elements are all the possible Pairs of elements from both collections. Basically:
The two distinct element types...
public class A {}
public class B {}

A "pair" of As and Bs.
public class Pair {
   private A a;
   private B b;

   public Pair(A a, B b){
     this a = a;
     this b = b;
   }
}

The "combination" made using old-style java.util.Collection API:
 public Collection<Pair> combine(Collection<A> as, Collection<B> bs){
    Collection<Pair> pairs = new ArrayList();
    foreach(A a: as){
      foreach(B b: bs){
          Pair pair = new Pair(a,b);
          pairs.add(pair);
      }
    }
    return pairs;
 }

The ordering in the resulting pairs collection is not important. So, every instance of Pair could be created and added to the resulting collection in parallel. How could I achieve this?
The best I could figure out by myself was to use the Streams version of foreach:
as.foreach(
  a -> {
    bs.foreach(
      b -> {
          Pair pair = new Pair(a,b);
          pairs.add(pair);
      }
  }
);

This example was made trivial for the sake of simplification. The class Pair is an example of processing two elements into a third one (that is, a java.util.function.BiFunction), and adding them to a Collection is just an example of a mutable reduction.
Is there a more elegant way to do that? Or preferable, in a more profitable way in regards to efficiency? Something like
BiFunction<A,B,Pair> combinator = Pair::new; //or any other function f(a,b)=c;

Stream<Pair> pairStream =
  Streams.unknownElegantMethod(as.stream(), bs.stream(), combinator);

A: If you're open to using a third-party library, you could use Eclipse Collections Sets.cartesianProduct().  This would require that your a's and b's are both Sets.  Eclipse Collections has a Pair type built-in, so you wouldn't need to create it.
public class A {}
public class B {}

public List<Pair<A, B>> combine(Set<A> as, Set<B> bs)
{
    return Sets.cartesianProduct(as, bs).toList();
}

If your a's and b's are not Sets, then you could use a CollectionAdapter flatCollect and collect, which are equivalent to flatMap and map on Stream.
public Collection<Pair<A, B>> combine(Collection<A> as, Collection<B> bs)
{
    MutableCollection<B> adaptB = CollectionAdapter.adapt(bs);
    return CollectionAdapter.adapt(as)
            .flatCollect(a -> adaptB.asLazy().collect(b -> Tuples.pair(a, b)));
}

Another possible option using Stream would be to define your own Collector for cartesianProduct.  This is more complex than the other Stream solution, and would only be useful if you used cartesianProduct a few times in your code.
List<Pair<A, B>> pairs = as.stream().collect(cartesianProduct(bs));

public static <T1, T2> Collector<T1, ?, List<Pair<T1, T2>>>
    cartesianProduct(Collection<T2> other)
{
    return Collector.of(
            ArrayList::new,
            (list, a) -> list.addAll(
                other.stream().map(b -> new Pair(a, b))).collect(Collectors.toList())),
            (list1, list2) ->
            {
                list1.addAll(list2);
                return list1;
            },
            Collector.Characteristics.UNORDERED
    );
}

Note: I am a committer for Eclipse Collections.

A: I hope I don't have any silly typos, but basically what you can do is :
List<Pair> list = as
                  .stream()
                  .flatMap(a -> bs.stream().map (b -> new Pair(a,b)))
                  .collect (Collectors.toList());

*

*First you create a Stream<A> from as.

*For each a instance
2.1 Create a Stream<B> of bs
2.2 Map each b to a pair of (a,b)

*Flatten all the pairs to a single Stream.

*Finally I collected them to a List, though you can choose other collections.

redpajama_set_name: RedPajamaStackExchange